2023牛客多校7.21补题

D-The Game of Eating

题意：一共有m道菜，n个人轮流点一道菜，一共点k道。第i个人对第j道菜的喜爱程度\(A_{i,j}\)对所有人公开，一个人点了菜所有人都可以吃到。每个人都希望最大化自己的喜爱程度之和，求最终的点菜集合。

分析：很容易想到每个人点菜时都点当前剩下的菜中自己最喜爱的，但是这样有一个问题，比如说倒数第2个人点菜，此时他知道他最喜爱的菜也是最后一个人最喜爱的菜，也就是说他知道如果他不点这道菜，那么最后一个人点菜时一定会点这道菜，因此倒数第2个人可以点他第二喜欢的菜，这样子来最大化他自己的喜爱程度之和。这个过程其实就是倒序贪心的过程，因此从最后一个人开始点菜，每个人点菜时还是都点当前剩下的菜中自己最喜爱的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=2e3+5;
const int M=4e5+5;
const int mod=998244353;
const int inf=1e9;
struct node{
	int val,id;
}a[N][N];
bool cmp(node x,node y){
	return x.val>y.val;
}
int vis[N],last[N],ans[N];
int main(){
	int T=read();
	while(T--){
		int n=read(),m=read(),k=read();
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				a[i][j].val=read();
				a[i][j].id=j;
			}
			sort(a[i]+1,a[i]+m+1,cmp);
		}
		memset(vis,0,sizeof(vis));
		memset(last,0,sizeof(last));
		int tot=0;
		for(int i=k;i>=1;--i){
			int now=i%n;
			if(now==0)now=n;
			for(int j=last[now]+1;j<=m;++j){
				if(vis[a[now][j].id])continue;
				vis[a[now][j].id]=1;
				ans[++tot]=a[now][j].id;
				last[now]=j;
				break;
			}
		}
		sort(ans+1,ans+tot+1);
		for(int i=1;i<=tot;++i){
			cout<<ans[i]<<" ";
		}cout<<endl;
	}
	return 0;
}

H-0 and 1 in BIT

题意：给定一个长为 n 的只含 A, B 两种字符的字符串，给定 Q 次询问 \((l,r,x)\) 表示二进制字符串 x 经过字符串 \([l,r]\) 这段区间后变成什么，其中A操作表示反转该二进制字符串（0, 1 互换），B操作将该二进制字符串视为数字计算 x = x + 1（溢出的位舍弃）。

分析：B操作是x=x+1,而A操作相当于求二进制串的反码，而原码(x)取反再+1是补码(-x)，因此反码就是补码-1，因此A操作就是x=-x-1。然后对于一段只含A,B的字符串\([l,r]\)，首先如果整个区间有奇数个A，那么x最后会变成-x(乘奇数个-1)，否则不变；然后每一个A和B对x的影响(是+1还是-1)都取决于其后A的个数的奇偶性，例如当前A后面有奇数个A则其贡献为+1，当前A后面有偶数个A则其贡献为-1，当前B后面有奇数个A则其贡献为-1，当前B后面有偶数个A则其贡献为+1。因此对于一段区间\([l,r]\),x会变成什么和x的01构成无关，也就是说我们可以预处理出\([l,r]\)对x的影响。

通过前缀和数组cnt[i]预处理出区间\([1,i]\)中字符'A'的个数，还是前缀和数组f[i]预处理出区间\([1,i]\)对x的影响是多少(一定是加减某一个常数，也就是把每一个+1或者-1汇总)。那么\([l,r]\)中字符'A'的个数就是\(cnt[r]-cnt[l-1]\)，而\([l,r]\)对x的影响则要分两种情况讨论，如果\(cnt[r]-cnt[l-1]\)是偶数，则为\(f[r]-f[l-1]\)，则\(x->x+f[r]-f[l-1]\)；如果\(cnt[r]-cnt[l-1]\)是奇数，则为\(f[r]+f[l-1]\)，则\(x->-x+f[r]+f[l-1]\)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=2e5+5;
const int M=4e5+5;
const int mod=998244353;
const int inf=1e9;
char s[N],c[N];
ll base[65];
int cnt[N],f[N];
int main(){
	int n=read(),q=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;++i){
		if(s[i]=='A')cnt[i]=cnt[i-1]+1;
		else cnt[i]=cnt[i-1];
	}
	for(int i=1;i<=n;++i){
		if(s[i]=='A')f[i]=f[i-1]*(-1)-1;
		else f[i]=f[i-1]+1;
	}
	base[0]=1;
	for(int i=1;i<=60;++i)base[i]=base[i-1]*2ll;
	ll ans=0;
	while(q--){
		int l=read(),r=read();
		int lreal=min((ans^(1ll*l))%n+1,(ans^(1ll*r))%n+1);
		int rreal=max((ans^(1ll*l))%n+1,(ans^(1ll*r))%n+1);
		l=lreal;r=rreal;
		scanf("%s",c+1);
		int len=strlen(c+1);
		ll mo=1ll<<len;
		ll x=0;
		for(int i=len;i>=1;--i){
			int now=c[i]-'0';
			x=x+1ll*now*base[len-i];
		}
		int acnt=cnt[r]-cnt[l-1];
		if(acnt%2==0){
			ans=x+f[r]-f[l-1];
		}
		else{
			ans=-x+f[r]+f[l-1];
		}
		ans=(ans%mo+mo)%mo;
		for(int i=1;i<=len;++i){
			if(ans&(1ll<<(len-i)))cout<<"1";
			else cout<<"0";
		}
		cout<<endl;
	}
	return 0;
}