必胜态与必败态 先手必胜 = “存在”一个后继局面是后手必败。 先手必败 = “对于所有”后继局面，都是后手必胜。 SG 函数 对于多个独立的游戏，可以分别计算它们的 SG 函数值，再求 Nim 和（即异或和）； 对于单个游戏，每个状态的 SG 函数值都是它的所有后继状态的 SG 函数值的 \text{mex} 值； 特别地，终止状态（即没有后继状态的状态）的 SG 函数值为 \text{mex} \varnothing =0。 题单 P17128 [ICPC 2025 Shanghai R] AGI 如果同时存在两个相同的数，那先手如果取走其中一个，后手肯定会把另一个取走。我们考虑找出所有这样的数对，让先手取走数对其中一个数，并对剩下的数进行处理。 如果剩下的数的数量不少于 4 个，那么先手必败，因为任何能取胜的策略都能被后手破坏。 如果剩下的数的数量为 2 个，则判断这两个数中有没有数异或上先手目前的数为 0。 若数量为 0，则判断先手手上的数是否为 0。 代码： C++ #include using namespace std; const int N=2e5+5; int T,n; int a[N],tag[N]; void solve(){ fill(tag,tag+(n mp; int now=0,sum=0,y=0; scanf("%d",&n); for(int i=1;i>T; while(T--) solve(); return 0; } `#include using namespace std; const int N=2e5+5; int T,n; int a[N],tag[N]; void solve(){ fill(tag,tag+(n1)+1,0); mapint,int> mp; int now=0,sum=0,y=0; scanf("%d",&n); for(int i=1;i(n1);i++){ scanf("%d",a+i); if(mp[a[i]]!=0) now^=a[i],tag[mp[a[i]]]=1,tag[i]=1,mp[a[i]]=0; else mp[a[i]]=i; } for(int i=1;i(n1);i++){ if(!tag[i]){ sum++; if((now^a[i])==0) y=1; } } if(!sum){ if(now) printf("Bot\n"); else printf("Menji\n"); } else if(sum==2) { if(!y) printf("Bot\n"); else printf("Menji\n"); } else printf("Bot\n"); } signed main(){ cin>>T; while(T--) solve(); return 0; }` AT_arc168_b [ARC168B] Arbitrary Nim 不难发现，对于一个堆的 SG 函数应该是 SG(x)=x \mod (k+1)， 先排除掉那些石子个数相等的两个堆，因为无论怎么取模它们异或的贡献还是 0。 如果剩余堆的异或值不为 0，说明我们不需要取模，也就是说 k 可以取无穷大，则输出 -1。 若没有剩余的堆，那说明先手必败，输出 0。 否则，我们输出剩余堆石子数最大值减 1，这样只有最大值变成了 0，其余值不变，异或值自然不会是 0。 代码： C++ #include using namespace std; int n,mx,sum; set s; int main(){ cin>>n; for(int i=1,x;i `#include using namespace std; int n,mx,sum; setint> s; int main(){ cin>>n; for(int i=1,x;in;i++){ scanf("%d",&x); sum^=x; if(s.find(x)!=s.end()) s.erase(x); else s.insert(x); } if(sum) cout"-1"; else if(s.empty()) cout"0"; else couts.end()-1; } ` CF388C Fox and Card Game 分两种情况讨论。 对于一个偶数堆，先发起取这个堆的肯定是有一个较大的值靠近自己，那对方就会为了先发起的人拿不到这个值而去取另一边的值，所以最终的状态肯定是双方各取两边。 对于一个奇数堆，原理还是一样的，但是先手会多拿到最中间的那个值。 所以对于偶数堆，直接计算答案；对于奇数堆，我们按照堆中间的值从大到小排序，两人交替地取中间的值即可。 代码： C++ #include using namespace std; const int N=1005; int n,idx,ans1,ans2; struct node{ int mid,l,r; bool operatorb.mid; } }a[N]; int main(){ cin>>n; for(int i=1;i>s; if(s&1){ idx++; for(int j=1,x;j>x; if(j>x; if(j `#include using namespace std; const int N=1005; int n,idx,ans1,ans2; struct node{ int mid,l,r; bool operatorconst node b)const{ return mid>b.mid; } }a[N]; int main(){ cin>>n; for(int i=1;in;i++){ int s; cin>>s; if(s&1){ idx++; for(int j=1,x;js;j++){ cin>>x; if(js/2) a[idx].l+=x; else if(j==s/2+1) a[idx].mid=x; else a[idx].r+=x; } } else{ for(int j=1,x;js;j++){ cin>>x; if(js/2) ans1+=x; else ans2+=x; } } } sort(a+1,a+1+idx); for(int i=1;iidx;i++){ if(i&1) ans1+=a[i].l+a[i].mid,ans2+=a[i].r; else ans1+=a[i].l,ans2+=a[i].mid+a[i].r; } coutans1" "ans2; return 0; }` CF1704F Colouring Game 不难发现，对于先手 Alice，肯定优先删除 RB，其次才考虑 RW；对于 Bob 也是如此。 所以，问题的关键就在于字符串中的颜色交替段，毕竟把颜色交替段取完后答案就是唯一的了。 因为每次删除 RB，两个颜色数量之差是不会变的，那就能先想到一个特判：如果两个颜色数量不等，一定是数量多的那个人赢。 否则我们来考虑计算颜色交替段的 SG 函数。 枚举颜色交替段的大小 i 与删除的位置 j，有： SGi=mexj=1ji{SGj−1⊕︎SGi−j−1}SG_i=\text{mex}_{j=1}^{j 这个计算是 O(n^2) 的，显然对于此题不优。 这时我们打个表： C++ #include using namespace std; int sg[1005],tag[1005]; signed main(){ freopen("sg.out","w",stdout); sg[2]=1; cout `#include using namespace std; int sg[1005],tag[1005]; signed main(){ freopen("sg.out","w",stdout); sg[2]=1; cout"0\n1\n"; for(int i=3;i1005;i++){ memset(tag,0,sizeof tag); for(int j=1;ji;j++) tag[sg[j-1]^sg[i-j-1]]=1; for(int j=0;j1005;j++) if(tag[j]==0){ sg[i]=j; break; } coutsg[i]"\n"; } return 0; }` 得到 sg.out 如下（为了美观，每 34 个元素换一次行，省略其余项）： C++ 0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 3 0 1 1 3 0 2 1 1 0 4 5 2 7 4 0 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 2 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 ... `0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 3 0 1 1 3 0 2 1 1 0 4 5 2 7 4 0 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 2 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4 ...` 就会惊喜地发现，除了前 68 项以外，后面的项都是以 34 为周期，那就可以只计算前 102 项了；并且值域是 10 以内的，所以求 \text{mex} 时也可以把枚举的范围缩小。 代码： C++ #include using namespace std; int T,n; int sg[105],tag[105]; char s[500005]; void get_sg(){ sg[2]=1; for(int i=3;i>T; while(T--){ int sr=0,sb=0,l=1,ans=0; cin>>n; for(int i=1;i>s[i]; if(s[i]=='R') sr++; else sb++; } if(sr!=sb){ coutsb?"Alice\n":"Bob\n"); continue; } for(int i=2;i `#include using namespace std; int T,n; int sg[105],tag[105]; char s[500005]; void get_sg(){ sg[2]=1; for(int i=3;i102;i++){ memset(tag,0,sizeof tag); for(int j=1;ji;j++) tag[sg[j-1]^sg[i-j-1]]=1; for(int j=0;j10;j++) if(tag[j]==0){ sg[i]=j; break; } } } int SG(int x){ if(x68) return sg[x]; else return sg[(x%34?x%34:34)+68]; } int main(){ get_sg(); cin>>T; while(T--){ int sr=0,sb=0,l=1,ans=0; cin>>n; for(int i=1;in;i++){ cin>>s[i]; if(s[i]=='R') sr++; else sb++; } if(sr!=sb){ cout(sr>sb?"Alice\n":"Bob\n"); continue; } for(int i=2;in;i++){ if(s[i]==s[i-1]) ans^=SG(l),l=1; else l++; } ans^=SG(l); cout(ans?"Alice\n":"Bob\n"); } return 0; }`
ZR 集训 Day17 - 博弈论
笔记