「BZOJ1299」[LLH邀请赛] 巧克力棒
Description
TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒，或是将一根取出的巧克力棒吃掉正整数长度。TBL先手两人轮流，无法操作的人输。 他们以最佳策略一共进行了10轮（每次一盒）。你能预测胜负吗？
Input
输入数据共20行。 第2i-1行一个正整数Ni，表示第i轮巧克力棒的数目。 第2i行Ni个正整数Li,j，表示第i轮巧克力棒的长度。
Output
输出数据共10行。 每行输出“YES”或“NO”，表示TBL是否会赢。如果胜则输出”NO”,否则输出”YES”
Sample Input
3
11 10 15
5
13 6 7 15 3
2
15 12
3
9 7 4
2
15 12
4
15 12 11 15
3
2 14 15
3
3 16 6
4
1 4 10 3
5
8 7 7 5 12
11 10 15
5
13 6 7 15 3
2
15 12
3
9 7 4
2
15 12
4
15 12 11 15
3
2 14 15
3
3 16 6
4
1 4 10 3
5
8 7 7 5 12
Sample Output
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
HINT
20%的分数，N<=5，L<=100。
40%的分数，N<=7。 50%的分数，L<=5,000。
100%的分数，N<=14，L<=1,000,000,000。
题解
先从n根巧克力棒中取出m(m>0)根，使得这m根巧克力棒的xor和为0（也就是把nim游戏的必败状态留给对方），同时使得剩下的n-m根巧克力棒无论怎么取，xor和都不为0。（实际上m就是巧克力棒的xor和为0的最长子序列）。
这么一来，对手就面临一个必败状态的nim游戏。如果他从n-m根中取新的巧克力棒，实际上就是新建一个xor和不为0的nim游戏，这时轮到己方操作只要将这个新的nim游戏取到xor和为0即可。（也就是让对方再次面临所有nim游戏均为必败状态的局面）。
寻找是否有Xor和=0的巧克力棒子序列，直接DFS无压力。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int n,sg[2001],a[2001]; bool found; int dfs(int x,int used,int now) { if(x==n+1) { if(!now&&used>0)found=1; return 0; } dfs(x+1,used,now); dfs(x+1,used+1,now^a[x]); } int main() { for(int t=1;t<=10;t++) { memset(sg,-1,sizeof(sg)); found=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dfs(1,0,0); if(found)puts("NO"); else puts("YES"); } return 0; } |
计数器 9872433
OI 课件=>
OI 课件=>
胜利输出NO我服了