ZR 集训 Day17 – 博弈论

ooliver 发布于 16 小时前 147 次阅读 OI

AI 摘要

先手必胜？后手翻盘？博弈的胜负，往往藏在一行异或和里。必胜态与必败态的递归定义，SG 函数的 mex 魔法，让复杂游戏化为简洁 Nim 和。更惊喜的是，打表竟发现周期 34 的规律——胜利的密码，原来就在眼前。

必胜态与必败态

  • 先手必胜 = “存在”一个后继局面是后手必败。
  • 先手必败 = “对于所有”后继局面，都是后手必胜。

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<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int T,n;
int a[N],tag[N];

void solve(){
    fill(tag,tag+(n<<1)+1,0);
    map<int,int> mp;
    int now=0,sum=0,y=0;
    scanf("%d",&n);
    for(int i=1;i<=(n<<1);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<=(n<<1);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<bits/stdc++.h>
using namespace std;

int n,mx,sum;
set<int> s;

int main(){
    cin>>n;
    for(int i=1,x;i<=n;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 cout<<*--s.end()-1; 
}

CF388C Fox and Card Game

分两种情况讨论。

对于一个偶数堆，先发起取这个堆的肯定是有一个较大的值靠近自己，那对方就会为了先发起的人拿不到这个值而去取另一边的值，所以最终的状态肯定是双方各取两边。

对于一个奇数堆，原理还是一样的，但是先手会多拿到最中间的那个值。

所以对于偶数堆，直接计算答案；对于奇数堆，我们按照堆中间的值从大到小排序，两人交替地取中间的值即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=1005;
int n,idx,ans1,ans2;
struct node{
    int mid,l,r;
    bool operator<(const node b)const{
        return mid>b.mid;
    }
}a[N];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int s;
        cin>>s;
        if(s&1){
            idx++;
            for(int j=1,x;j<=s;j++){
                cin>>x;
                if(j<=s/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;j<=s;j++){
                cin>>x;
                if(j<=s/2) ans1+=x;
                else ans2+=x;
            } 
        }
    }
    sort(a+1,a+1+idx);
    for(int i=1;i<=idx;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;
    }
    cout<<ans1<<" "<<ans2;
    return 0;
}

CF1704F Colouring Game

不难发现，对于先手 Alice，肯定优先删除 RB，其次才考虑 RW；对于 Bob 也是如此。

所以，问题的关键就在于字符串中的颜色交替段，毕竟把颜色交替段取完后答案就是唯一的了。

因为每次删除 RB，两个颜色数量之差是不会变的，那就能先想到一个特判：如果两个颜色数量不等，一定是数量多的那个人赢。

否则我们来考虑计算颜色交替段的 SG 函数。

枚举颜色交替段的大小 $i$ 与删除的位置 $j$，有：

SGi=mexj=1j<i{SGj−1⊕︎SGi−j−1}SG_i=\text{mex}_{j=1}^{j<i} \{SG_{j-1} \oplus SG_{i-j-1}\}

这个计算是 $O(n^2)$ 的，显然对于此题不优。

这时我们打个表：

C++
#include<bits/stdc++.h>
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;i<=1005;i++){
        memset(tag,0,sizeof tag);
        for(int j=1;j<i;j++) tag[sg[j-1]^sg[i-j-1]]=1;
        for(int j=0;j<1005;j++) if(tag[j]==0){
            sg[i]=j;
            break;
        }
        cout<<sg[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 
...

就会惊喜地发现，除了前 68 项以外，后面的项都是以 34 为周期，那就可以只计算前 102 项了；并且值域是 10 以内的，所以求 $\text{mex}$ 时也可以把枚举的范围缩小。

代码：

C++
#include<bits/stdc++.h>
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<=102;i++){
        memset(tag,0,sizeof tag);
        for(int j=1;j<i;j++) tag[sg[j-1]^sg[i-j-1]]=1;
        for(int j=0;j<10;j++) if(tag[j]==0){
            sg[i]=j;
            break;
        }
    }
}

int SG(int x){
    if(x<=68) 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;i<=n;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;i<=n;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;
}