移棋子游戏

其实就是典型的有向图游戏, 求出所有起点的SG值并求异或和。 只不过这道题只有一张图， 但是图上有k个起点

puts(res ? "win" : "lose"); 这一句可以拿来装13

用 set 容器来实现求SG值 要掌握 set.insert() 和 set.count() 函数

#include <iostream>
#include <cstring>
#include <set>
using namespace std;

const int NN = 2010, MM = 6010;
int h[NN], e[MM], ne[MM], idx;   // 使用邻接表存图，可以快速得到一个点的出边（出点）
int N, M, K, res;
int f[NN];   // 把每个点的SG值存下来，实现记忆化搜索

int add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int find(int x){
    if (f[x] != -1) return f[x];     // 记忆化的本质
    set<int> S;
    for (int i = h[x]; i != -1; i = ne[i]){
        int j = e[i];
        S.insert(find(j));
    } 
    for (int i = 0; ; i ++){
        if (!S.count(i)) return f[x] = i;
    }
}

int main(){
    memset(h, -1, sizeof(h));
    memset(f, -1, sizeof(f));
    int a, b, k;
    cin >> N >> M >> K;
    while (M --){
        cin >> a >> b;
        add(a, b);
    }
    while (K --){
        cin >> k;
        res ^= find(k);
    }
    puts(res ? "win" : "lose");

    return 0;
}