题目大意
额，写来写去，我还是直接说抽象之后的题目大意吧：
有一个 r*2 的矩形，两个人轮流的在矩形上面减去一个 1*1 的小正方形，要求在减的过程中，不能使矩形“断开”，也就是说，如果一个人减去了 (i, 1) 这个矩形，那么，(i-1, 2), (i+1, 2), (i, 2) 这三个小正方形不能再被减去了，因为一旦减去它们中的一个，整个矩形就会被“剪断”
现在给你一个 r 和 n (1 ≤ r ≤ 100, 0 ≤ n ≤ r)，表示有一个 r*2 矩形，已经有了 n 个位置被减去了，再给 n 个位置的坐标，题目保证开始的状态矩形不会被剪断.
现在问，对于当前的状态，先手是否必胜
做法分析
这题是博弈已经没得说了，而且，很明显是游戏的和的问题，必然是爆 sg 函数了
先来看看怎么表示状态：sg[len][x][y] 表示，有一个长度为 len 的矩形，它的 len*2 个小正方形都在，最左边的一个小正方形只能按照 x 的方式剪掉，最右边的一个小正方形只能按照 y 的方式剪掉，其中：x=1 或者 y=1 表示剪掉的是第一排的矩形，x=2 或者 y=2 表示剪掉的是第二排的矩形，x=0 或者 y=0 表示没有限制，即：可以剪掉第一排的也可以剪掉第二排的
那么，当 len=0 的时候，必然有 sg[0][x][y]=0，其中 0≤x≤2, 0≤y≤2
当 len=1 的时候，必然有 sg[1][1][2]=sg[1][2][1]=0， sg[1][1][1]=sg[1][2][2]=sg[1][0][x]=sg[1][x][0]=1，其中 0≤x≤2
根据状态的定义，当前状态的下一个子状态也很好确定，先记忆化搜索将 sg 函数暴力出来
然后，根据输入的矩形，将举行分解成若干个子矩形，每个子矩形都应该尽量大，这样，每个子矩形必然属于上面提到的的一个状态之一
现在的游戏就变成了很多个游戏的和了，求出这些子游戏的 sg 值的异或和 sum，如果 sum!=0，先手必胜，否则先手必败
参考代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int N=105; 10 11 int sg[N][3][3]; 12 struct data { 13 int id, val; 14 bool operator < (const data &T) const { 15 return id<T.id; 16 } 17 } A[N]; 18 19 int GET_SG(int len, int x, int y) { 20 if(sg[len][x][y]!=-1) return sg[len][x][y]; 21 22 if(len==0) return sg[len][x][y]=sg[len][y][x]=0; 23 if(x>y) swap(x, y); 24 if(len==1 && x==1 && y==2) return sg[len][x][y]=sg[len][y][x]=0; 25 if(len==1) return sg[len][x][y]=sg[len][y][x]=1; 26 27 bool vs[N]; 28 memset(vs, 0, sizeof vs); 29 for(int len1=0; len1<len; len1++) { 30 int len2=len-1-len1; 31 if(len1==0) { 32 if(x==0) { 33 vs[GET_SG(len2, 1, y)]=1; 34 vs[GET_SG(len2, 2, y)]=1; 35 } 36 else vs[GET_SG(len2, x, y)]=1; 37 } 38 else if(len2==0) { 39 if(y==0) { 40 vs[GET_SG(len1, x, 1)]=1; 41 vs[GET_SG(len1, x, 2)]=1; 42 } 43 else vs[GET_SG(len1, x, y)]=1; 44 } 45 else { 46 vs[GET_SG(len1, x, 1)^GET_SG(len2, 1, y)]=1; 47 vs[GET_SG(len1, x, 2)^GET_SG(len2, 2, y)]=1; 48 } 49 } 50 for(int i=0; i<N; i++) if(!vs[i]) return sg[len][x][y]=sg[len][y][x]=i; 51 } 52 53 int main() { 54 memset(sg, -1, sizeof sg); 55 for(int i=0; i<=100; i++) 56 for(int j=0; j<3; j++) 57 for(int k=0; k<3; k++) if(sg[i][j][k]==-1) GET_SG(i, j, k); 58 for(int r, n; scanf("%d%d", &r, &n)!=EOF; ) { 59 for(int i=1; i<=n; i++) scanf("%d%d", &A[i].id, &A[i].val); 60 A[0].id=0, A[0].val=0, A[n+1].id=r+1, A[n+1].val=0; 61 n+=2; 62 sort(A, A+n); 63 int sum=0; 64 for(int i=1; i<n; i++) sum^=sg[A[i].id-A[i-1].id-1][A[i-1].val][A[i].val]; 65 if(sum) printf("WIN "); 66 else printf("LOSE "); 67 } 68 return 0; 69 }
题目链接 & AC 通道
MemSQL start[c]up Round 2 - online version C. More Reclamation