取石子游戏

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1987 字
N堆石子，每次只能取给定的M种数量之一。若先
一本通
练习
正文

/*
原题：T1666「一本通 6.7 练习 1」取石子游戏
题意：N 堆石子，每次只能取给定的 M 种数量之一。若先手必胜，输出 YES 并给出一步走法
（先取第几堆、再取多少个，均字典序最小），否则输出 NO。
思路：先按允许集合递推出单堆石子数的 SG 值，把所有堆的 SG 异或起来。
总异或为 0 则必败；否则要找一步把它变成 0：对第 i 堆，需要把它的 sg 变成
total^sg[i]（这样全部异或即为 0），在某个允许取值 b 满足 sg(a[i]-b)==该值时即可。
按堆号从小到大、取的数量从小到大枚举，第一个满足的就是要求的答案。
复杂度：时间 O(N·maxA·M)，空间 O(maxA)
易错点：1) 允许取值的合集要先排序去重再算 SG；
2) 寻找走法时要求新状态 sg 恰好等于 total^sg[i]，且必须真的能取走（a[i]-b>=0）；
3) 输出格式：YES 独占一行，第二行两个数用空格隔开。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>>N;
    vector<long long> a(N+1);
    long long maxA=0;
    for(int i=1;i<=N;i++){
        cin>>a[i];
        if(a[i]>maxA){
            maxA=a[i];
        }
    }
    int M;
    cin>>M;
    vector<long long> b(M);
    for(int i=0;i<M;i++){
        cin>>b[i];
    }
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    int mA=(int)maxA+1;
    vector<int> sg(mA,0);
    vector<long long> nxtBuf;
    for(int x=1;x<mA;x++){
        // 收集所有后继单堆的 sg，排序去重后取最小未出现的非负整数
        nxtBuf.clear();
        for(long long t:b){
            if(t>x){
                break;
            }
            nxtBuf.push_back(sg[x-t]);
        }
        sort(nxtBuf.begin(),nxtBuf.end());
        nxtBuf.erase(unique(nxtBuf.begin(),nxtBuf.end()),nxtBuf.end());
        int g=0;
        for(long long v:nxtBuf){
            if(v==g){
                g++;
            }else if(v>g){
                break;
            }
        }
        sg[x]=g;
    }
    long long total=0;
    for(int i=1;i<=N;i++){
        total^=sg[(int)a[i]];
    }
    if(total==0){
        cout<<"NO\n";
        return 0;
    }
    cout<<"YES\n";
    for(int i=1;i<=N;i++){
        long long need=total^sg[(int)a[i]];
        for(long long t:b){
            if(t>a[i]){
                break;
            }
            if(sg[(int)(a[i]-t)]==need){
                cout<<i<<" "<<t<<"\n";
                return 0;
            }
        }
    }
    return 0;
}
取石子游戏

正文

一本通·提高篇的其它内容
