移棋子游戏

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1311 字

一个有向图上放K枚棋子，两人轮流把一枚棋子沿

一本通
例

正文

/*
原题：T1665「一本通 6.7 例 3」移棋子游戏
题意：一个有向图上放 K 枚棋子，两人轮流把一枚棋子沿一条出边移到相邻点，
无法移动者输。先手胜输出 win，否则输出 lose。
思路：每个棋子是一个独立的公平组合游戏局面，用 SG 函数刻画：
sg(u)=mex{sg(v) | 存在边 u->v}，出度为 0 的点 sg=0。
整局是这些局面的和，按 SG 定理把 K 枚棋子所在点的 sg 异或起来，
非 0 则先手胜。图保证可按拓扑序推导，用带记忆化的 DFS 从汇点往回算。
复杂度：时间 O(N+M)，空间 O(N+M)
易错点：1) 要算的是每个点的 SG 值并把它们异或，不是简单判断能否到达终点；
2) mex 需要对后继集合去重后从小到大取第一个没出现的非负整数；
3) 图是有向的，建边时注意方向别反。
*/
#include <bits/stdc++.h>
using namespace std;
int N,M,K;
vector<vector<int>> adj;
vector<int> sg;
vector<int> tmpMark;
int getSg(int u){
    if(sg[u]!=-1){
        return sg[u];
    }
    vector<int> nxt;
    for(int v:adj[u]){
        nxt.push_back(getSg(v));
    }
    sort(nxt.begin(),nxt.end());
    nxt.erase(unique(nxt.begin(),nxt.end()),nxt.end());
    int g=0;
    for(int v:nxt){
        if(v==g){
            g++;
        }else if(v>g){
            break;
        }
    }
    sg[u]=g;
    return g;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>M>>K;
    adj.assign(N+1,vector<int>());
    for(int i=0;i<M;i++){
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
    }
    sg.assign(N+1,-1);
    int xo=0;
    for(int i=0;i<K;i++){
        int p;
        cin>>p;
        xo^=getSg(p);
    }
    if(xo!=0){
        cout<<"win\n";
    }else{
        cout<<"lose\n";
    }
    return 0;
}

移棋子游戏

正文

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