列表

详情

NC234425. 小红的食尸鬼

描述

小红得知炉石传说里有一个卡牌叫“蹒跚的食尸鬼”，想出了这样一个问题：
已知食尸鬼攻击力为1，血量为3，另外有一个亡语：死亡时对场上所有随从（不分敌我）造成1点伤害（死亡立即触发）。
目前敌方场上有一个1攻，无穷大血量的随从。
小红有以下3种操作：
S：在自己的场上下一个1攻3血的食尸鬼。
A：命令每个食尸鬼进攻敌方随从。（顺序可以自己决定，命令结束后一定要保证剩余在场上的食尸鬼全部进行过进攻）。
H：使用法术：火山药水。对场上所有随从（不分敌我）造成2点伤害。
ps:一个随从进攻一个随从，会使两个随从的血量都会扣取对方随从的攻击力的值，当一个随从的血量小于1点时，随从就会死亡。
小红拿到了一个字符串，有很多次询问。
询问有两种类型
当时 小红想知道在空场初始状态下，执行[l,r]连续子串最多可以对敌方随从造成多少伤害？
当时 小红将这个字符串的一个字符修改成他想要的字符。

输入描述

第一行输入两个正整数  和  ，代表操作指令集长度和询问次数。
第二行输入一个长度为 的、只包含'S'、'A'、'H'三种字符的字符串。
接下来的  行，每行首先输入一个正整数。
当时 随后输入两个正整数代表查询区间的字符串最多可以对敌方随从造成多少伤害。
当时 随后输入一个正整数和一个字符代表将字符串的第个字符修改成。
(,)

输出描述

对于每一个的情况 输出一行整数，代表对地方随从造成的总伤害。

示例1

输入: 

10 3
SSASHSSSAA
1 1 3
1 3 4
1 4 10

输出: 

2
0
11

说明:

第一个询问 SSA 我们会下2个3血食尸鬼，然后全部进行1次攻击，造成2点伤害，剩下2个2血食尸鬼。
第二个询问 AS 首先进行1次进攻，但是场上没有食尸鬼，随后下1个3血食尸鬼。造成0点伤害。
第三个询问 SHSSSAA 首先下1个3血食尸鬼，然后火山魔法造成2点伤害，剩下1个1血食尸鬼，随后下3个3血食尸鬼。
进行1次攻击 首先3血食尸鬼进行1次攻击，造成3点伤害，随后1血食尸鬼进行1次攻击，造成1点伤害同时自身死亡，对全场造成1点伤害，本次攻击总计造成5点伤害，同时剩下3只1血食尸鬼。
下1次攻击 任意1只食尸鬼进行1次攻击，随后全场死亡，本次攻击总计造成4点伤害。
本次询问总计造成11点伤害，可以自行验正，这样造成的伤害是最大的。

示例2

输入: 

5 3
SAHSA
1 1 5
2 2 S
1 1 3

输出: 

5
2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 647ms, 内存消耗: 156016K, 提交时间: 2022-11-13 17:36:24 

/*
わんわん……わんだほーいっ☆
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
struct State{
	int t;
	int d;
	int w[3];
	int mv;
	int c[3];
};
State operator + (const State& a,const State& b)
{
	State c;
	c.t=b.t;
	c.d=a.d+b.d;
	c.mv=min(3,a.mv+b.mv);
	for(int i=0;i<3;++i)
	{
		c.w[i]=a.w[i];
		c.d+=b.w[i]*a.c[i];
		if(i>=a.mv)	c.w[i]+=b.w[i-a.mv];
	}
	for(int i=0;i<3;++i)
	{
		c.c[i]=b.c[i];
		if(i>=b.mv)	c.c[i-b.mv]+=a.c[i];
		else	c.d+=a.c[i];
	}
	return c;
}
struct node{
	State st[11];
	node(){for(int i=0;i<11;++i)	st[i]={i,0,{0,0,0},0,{0,0,0}};}
}S,A,H,tr[400005];
inline node alter(char c){return c=='S'?S:(c=='A'?A:H);}
node operator + (const node& a,const node& b)
{
	node c;
	for(int i=0;i<11;++i)	c.st[i]=a.st[i]+b.st[a.st[i].t];
	return c;
}
int n,q;
char s[100005];
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define Mm int mid=(l+r)>>1
void build(int l,int r,int now)
{
	if(l==r)	return tr[now]=alter(s[l]),void();
	Mm;
	build(l,mid,lc(now)),build(mid+1,r,rc(now));
	tr[now]=tr[lc(now)]+tr[rc(now)];
}
void modify(int l,int r,int now,int p)
{
	if(l==r)	return tr[now]=alter(s[l]),void();
	Mm;
	if(p<=mid)	modify(l,mid,lc(now),p);
	else	modify(mid+1,r,rc(now),p);
	tr[now]=tr[lc(now)]+tr[rc(now)];
}
node query(int l,int r,int now,int x,int y)
{
	if(x<=l && r<=y)	return tr[now];
	Mm;
	if(x<=mid && mid<y)	return query(l,mid,lc(now),x,y)+query(mid+1,r,rc(now),x,y);
	if(x<=mid)	return query(l,mid,lc(now),x,y);
	if(mid<y)	return query(mid+1,r,rc(now),x,y);
	return node();
}
// 0.  a1 >= 2
// 1.  a1 = 1, a2 >= 1
// 2.  a1 = 1, a2 = 0, a3 >= 2
// 3.  a1 = 1, a2 = 0, a3 = 1
// 4.  a1 = 1, a2 = 0, a3 = 0
// 5.  a1 = 0, a2 >= 2
// 6.  a1 = 0, a2 = 1, a3 >= 1
// 7.  a1 = 0, a2 = 1, a3 = 0
// 8.  a1 = 0, a2 = 0, a3 >= 2
// 9.  a1 = 0, a2 = 0, a3 = 1
// 10. a1 = a2 = a3 = 0
int main(){
//	freopen("ghoul.in","r",stdin);
	S.st[0]={0,0,{0,0,0},0,{0,0,1}}; A.st[0]={10,1,{0,1,1},3,{0,0,0}}; H.st[0]={10,2,{0,0,0},3,{0,0,0}}; 
	S.st[1]={1,0,{0,0,0},0,{0,0,1}}; A.st[1]={10,1,{0,1,1},3,{0,0,0}}; H.st[1]={10,2,{0,0,0},3,{0,0,0}}; 
	S.st[2]={2,0,{0,0,0},0,{0,0,1}}; A.st[2]={0,1,{0,1,1},2,{0,0,0}};  H.st[2]={10,2,{0,0,0},3,{0,0,0}}; 
	S.st[3]={2,0,{0,0,0},0,{0,0,1}}; A.st[3]={4,1,{0,1,1},2,{0,0,0}};  H.st[3]={10,2,{0,0,0},3,{0,0,0}}; 
	S.st[4]={3,0,{0,0,0},0,{0,0,1}}; A.st[4]={10,1,{0,1,1},2,{0,0,0}}; H.st[4]={10,2,{0,0,0},3,{0,0,0}}; 
	S.st[5]={5,0,{0,0,0},0,{0,0,1}}; A.st[5]={0,0,{0,1,1},1,{0,0,0}};  H.st[5]={10,2,{0,0,0},3,{0,0,0}}; 
	S.st[6]={6,0,{0,0,0},0,{0,0,1}}; A.st[6]={1,0,{0,1,1},1,{0,0,0}};  H.st[6]={10,2,{0,0,0},3,{0,0,0}}; 
	S.st[7]={6,0,{0,0,0},0,{0,0,1}}; A.st[7]={4,0,{0,1,1},1,{0,0,0}};  H.st[7]={10,2,{0,0,0},3,{0,0,0}}; 
	S.st[8]={8,0,{0,0,0},0,{0,0,1}}; A.st[8]={5,0,{0,1,1},1,{0,0,0}};  H.st[8]={0,2,{0,0,0},2,{0,0,0}}; 
	S.st[9]={8,0,{0,0,0},0,{0,0,1}}; A.st[9]={7,0,{0,1,1},1,{0,0,0}};  H.st[9]={4,2,{0,0,0},2,{0,0,0}}; 
	S.st[10]={9,0,{0,0,0},0,{0,0,1}};A.st[10]={10,0,{0,1,1},1,{0,0,0}};H.st[10]={10,2,{0,0,0},2,{0,0,0}};
	scanf("%d %d",&n,&q);
	scanf("%s",s+1);
	build(1,n,1);
	while(q-->0)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int l,r;
			scanf("%d %d",&l,&r);
			printf("%d\n",query(1,n,1,l,r).st[10].d);
		}
		else
		{
			int p;
			char c[2];
			scanf("%d %s",&p,c);
			s[p]=*c;
			modify(1,n,1,p);
		}
	}
	return 0;
}

上一题

© 2024 nowcoder.com