题意：一共有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;
}
题意：给定一个长为 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;
}