题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5330
题意：有n堆卡片，每张卡片上面都有一个数字（1~10），每次操作选择一堆卡片，取走最上面（0~k）张，一堆至少要留一张，然后再取这堆卡片当前堆顶卡片上面的数字张数。谁不能取就输了。
思路：组合游戏博弈，直接暴力计算出每一堆的sg函数即可。
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <iostream> #include <algorithm> #include <stack> #include <map> #include <set> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;i++) #define Rrep(i,j,k) for (int i=j;i>=k;i--) #define Clean(x,y) memset(x,y,sizeof(x)) #define LL long long #define ULL unsigned long long #define inf 0x7fffffff #define mod 100000007 const int maxn = 1009; int p,k; int a[maxn]; int cal(int n) { int sg[maxn]; int temp[50]; Clean(sg,0); rep(i,1,n) { Clean(temp,false); rep(j,0,k) if ( i > j && i - j >= a[i-j] ) temp[ sg[i-j-a[i-j]] ] = true; int j = 0; while(temp[j]) j++; sg[i] = j; } return sg[n]; } void solve() { int m; int ans = 0; rep(i,1,p) { scanf("%d",&m); rep(j,1,m) scanf("%d",&a[j]); ans ^= cal(m); } puts(ans?"Alice can win.":"Bob will win."); } int main() { while( cin>>p>>k ) { solve(); } return 0; }
