自选题解原创题brick break game

1、题Brick Break Game解题江苏省常州高级中学February 24, 201111题目描述很久很久很久很久很久以前, 有一个有趣的每一块的长度都是1,2,3,4 的一个整数。这个是这样的, 地上有一些砖块, 保证每次你有两种操作, 拿走 n 个长度为 n 的砖块, 或者把一个长度大于 1 的砖块分为两个长度大于等于 0 的砖块。如果某个玩家无法操作, 就算这位玩家输。现在给出你一些局面, 判断这个是先手必胜还是后手必胜。230% 数据题目中 30% 数据满足： a + 2b + 3c + 4d 10。于是可以直接 搜索。对于当前操作的人，如果发现无法进行操作，返回 0，代表这位玩家

2、输了。否则枚举每一种操作，获得后继状态的值，如果发现有一个 0，则可以立刻返回这个状态是必胜态；如果全是 1，则返回这个状态是必败态。370% 数据题目中 70% 数据满足： maxa, b, c, d 14。发现有了这个条件之后，总得可能的状态数是 144 4!，无论是空间还是时间都可以承受。很快就可以得到一个动态规划的思路：fabcd 表示长度为 1,2,3,4 的砖块分别有a,b,c,d 块，这个状态是否必胜。然后来看看转移， (a, b, c, d) 可以转移到这些状态：(1) (a 1, b, c, d), a 1(2) (a, b 2, c, d), b 2(3) (a, b, c

3、 3, d), c 3(4) (a, b, c, d 4), d 4(5) (a + 2, b 1, c, d), b 1(6) (a + 1, b + 1, c 1, d), c 1(7) (a + 1, b, c + 1, d 1), d 1(8) (a, b + 2, c, d 1), d 1转移是常数级别的，所以动态规划可以解决 70% 的数据。4100% 数据题目中 100% 数据满足： a, b, c, d 1010000。显然引入 r 和 s 两个变量： r = (a + c) mod 2， s = (b + d) mod 3。定理 1 这个先手必胜当且仅当 r = s。2下面看

4、一下证明：首先对于一个必败状态 r = s，所有转移都会导致 r = s，也就是都是必胜状态。其次对于必胜状态 (a, b, c, d)， s r 只可能是 -1, 2, 2 ：对于 s r = 1，有两种方法使得 r = s：(1) 和 (6)对于 s r 1，有两种方法使得 r = s：(5) 和 (8)对于 s r = 2，有两种方法使得 r = s：(2) 和 (7)而且可以证明对于任何一种情况，不可能出现两种 move 方式都不可行。因此，证明了任何一个必胜状态都可以通向一个必败状态。于是上面的定理成立。只要简单统计出 (a + c) mod 2 和 (b + d) mod 3 的值

5、，最后比较一下就可以了。5代码#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #includeusing namespatd;#define ME(s) memset(s),0, sizeof(s)#define MM(s,a) memset(s),(

6、a),sizeof(s)#define MCP(s,a) memcpy(s), (a), sizeof(s) #define LL long long#define LD long double#definI pair3#define #define #define #define #define #define #define #definePDD pair mkp(a,b) make_pair(a),(b) yx secondsqr(a) (a)*(a)lowbit(x) (x)&(-(x) two(x) (1(x)contaask,x) (mask)&two(x)!=0)#defineOFFLINEJUDGE#ifdef OFFLINEJUDGEFILE *fin=freopen(bbg.in,r,stdin); FILE *fout=freopen(bbg.out,w,stdout); #elseFILE *fin=stdin; FILE *fout=stdout; #endifchar A11111,B11111,C11111,D11111;MOD(char *s,m)ret=0, len=strlen(s); for(i=0;ilen;i+)ret=(ret*10+si-0)%m;return ret；run()scanf(%s%s%s%s,A,B,C,D