首页 > 代码库 > UESTC 1712 七夜雪寂,一世人心

UESTC 1712 七夜雪寂,一世人心

题意:变形的nim游戏,多堆石子,每次只能拿走S集合中的数

题解:简单SG函数,一开始写错了。。。

#include <bits/stdc++.h>#define maxn 10010using namespace std;int sg[maxn], k, s[maxn], dir[maxn];void getsg(int t){    for(int i=0;i<k;i++){        if(t>=s[i]){            dir[sg[t-s[i]]] = 1;        }    }    int i = 0;    while(1){        if(dir[i] == 0){            sg[t] = i;            break;        }        i++;    }}int main(){    int m, n, a;    cin>>k;    for(int i=0;i<k;i++) cin>>s[i];    memset(sg, -1, sizeof(sg));    sg[0] = 0;    for(int i=0;i<=12;i++) {            memset(dir, 0, sizeof(dir));            getsg(i);    }    cin>>m;    while(m--){        cin>>n;        int ans = 0;        for(int i=0;i<n;i++) cin>>a,ans ^= sg[a];        printf("%s\n", (ans == 0)?"lose!":"win!");        //cout<<ans<<endl;    }    return 0;}

 

UESTC 1712 七夜雪寂,一世人心