题目大意
额，写来写去，我还是直接说抽象之后的题目大意吧：
有一个 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，先手必胜，否则先手必败
参考代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm> using namespace std; const int N=; int sg[N][][];
struct data {
int id, val;
bool operator < (const data &T) const {
return id<T.id;
}
} A[N]; int GET_SG(int len, int x, int y) {
if(sg[len][x][y]!=-) return sg[len][x][y]; if(len==) return sg[len][x][y]=sg[len][y][x]=;
if(x>y) swap(x, y);
if(len== && x== && y==) return sg[len][x][y]=sg[len][y][x]=;
if(len==) return sg[len][x][y]=sg[len][y][x]=; bool vs[N];
memset(vs, , sizeof vs);
for(int len1=; len1<len; len1++) {
int len2=len--len1;
if(len1==) {
if(x==) {
vs[GET_SG(len2, , y)]=;
vs[GET_SG(len2, , y)]=;
}
else vs[GET_SG(len2, x, y)]=;
}
else if(len2==) {
if(y==) {
vs[GET_SG(len1, x, )]=;
vs[GET_SG(len1, x, )]=;
}
else vs[GET_SG(len1, x, y)]=;
}
else {
vs[GET_SG(len1, x, )^GET_SG(len2, , y)]=;
vs[GET_SG(len1, x, )^GET_SG(len2, , y)]=;
}
}
for(int i=; i<N; i++) if(!vs[i]) return sg[len][x][y]=sg[len][y][x]=i;
} int main() {
memset(sg, -, sizeof sg);
for(int i=; i<=; i++)
for(int j=; j<; j++)
for(int k=; k<; k++) if(sg[i][j][k]==-) GET_SG(i, j, k);
for(int r, n; scanf("%d%d", &r, &n)!=EOF; ) {
for(int i=; i<=n; i++) scanf("%d%d", &A[i].id, &A[i].val);
A[].id=, A[].val=, A[n+].id=r+, A[n+].val=;
n+=;
sort(A, A+n);
int sum=;
for(int i=; i<n; i++) sum^=sg[A[i].id-A[i-].id-][A[i-].val][A[i].val];
if(sum) printf("WIN\n");
else printf("LOSE\n");
}
return ;
}
C. More Reclamation
题目链接 & AC 通道
MemSQL start[c]up Round 2 - online version C. More Reclamation