S-Nim

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2031 字
多组数据。每组先给出允许取走的石子数集合S，
一本通
练习
正文

/*
原题：T1669「一本通 6.7 练习 4」S-Nim
题意：多组数据。每组先给出允许取走的石子数集合 S，再给出 m 个局面，
每个局面有 n 堆石子；对每个局面判断先手必胜(W)还是必败(L)，输出为一行 m 个字符。
k=0 表示输入结束。
思路：先按允许集合递推出单堆石子数 x 的 SG 值：sg(x)=mex{sg(x-s) | s∈S, x-s≥0}。
每个局面是若干堆的和，按 SG 定理把所有堆的 sg 异或起来，非 0 则必胜。
复杂度：时间 O(maxA·|S| + 总堆数)，空间 O(maxA)
易错点：1) 输入格式是 k 与 k 个数可能在同一行，用 cin 顺序读取即可，不要按行解析；
2) SG 只需算到当前数据里最大堆的大小，多组数据要分别重新计算；
3) 输出是每个数据组一整行字符串，中间不能有空格。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(true){
        int k;
        cin>>k;
        if(k==0){
            break;
        }
        vector<long long> s(k);
        for(int i=0;i<k;i++){
            cin>>s[i];
        }
        sort(s.begin(),s.end());
        s.erase(unique(s.begin(),s.end()),s.end());
        int m;
        cin>>m;
        vector<vector<long long>> pos(m);
        long long maxA=0;
        for(int i=0;i<m;i++){
            int n;
            cin>>n;
            pos[i].resize(n);
            for(int j=0;j<n;j++){
                cin>>pos[i][j];
                if(pos[i][j]>maxA){
                    maxA=pos[i][j];
                }
            }
        }
        int mA=(int)maxA+1;
        vector<int> sg(mA,0);
        vector<long long> nxt;
        for(int x=1;x<mA;x++){
            nxt.clear();
            for(long long t:s){
                if(t>x){
                    break;
                }
                nxt.push_back(sg[x-t]);
            }
            sort(nxt.begin(),nxt.end());
            nxt.erase(unique(nxt.begin(),nxt.end()),nxt.end());
            int g=0;
            for(long long v:nxt){
                if(v==g){
                    g++;
                }else if(v>g){
                    break;
                }
            }
            sg[x]=g;
        }
        string out;
        for(int i=0;i<m;i++){
            long long xo=0;
            for(long long v:pos[i]){
                xo^=sg[(int)v];
            }
            out.push_back(xo!=0?'W':'L');
        }
        cout<<out<<"\n";
    }
    return 0;
}
S-Nim

正文

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