[博弈论]移棋子游戏

本文主要是介绍[博弈论]移棋子游戏，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://www.acwing.com/problem/content/1321/

思路：
求所有棋子的sg异或之和，
记忆化搜索
得到当前结点后继的这些点的sg值之和，放到set里面(哈希表也可以)
然后找到最小的不属于集合的自然数就是当前结点的sg值

#include<bits/stdc++.h>
using namespace std;
const int N = 2010,M = 6010;

int n,m,k;
int f[N];
int h[N],ne[M],e[M],idx;

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

int sg(int u){
    if(f[u] != -1) return f[u];
    set<int> se;
    for(int i=h[u];~i;i=ne[i]){
        int v = e[i];
        se.insert(sg(v));
    }
    for(int i=0;;i++)
        if(se.count(i) == 0){
            return f[u] = i;
        }
}

int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    memset(f,-1,sizeof f);
    int res = 0;
    for(int i=0;i<k;i++){
        int x;
        scanf("%d",&x);
        res ^= sg(x);
    }
    if(res) puts("win");
    else puts("lose");
    
    return 0;
}

这篇关于[博弈论]移棋子游戏的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！