HDU 3389 Game (博弈)
题意:有n个盒子,从1到n排成一排,每个盒子里有一些卡片,每次一个玩家可以进行一个操作,从一个非空的盒子B中取出一些卡片放到盒子A中,A,B要满足 (A < B && (A + B) %2== 1 && (A+B)%3==0),不能操作的人输。
解题思路:
这题刚开始想没什么思路,无法将题目转换成常见的博弈问题,不过认真想想很容易发现 (A+B) = 6k + 3 (k >= 0),于是对于两个盒子A,B可行的转移也可以想出来, B%6 == 0的盒子可以转移到B%6 == 3的盒子里, B%6==1的盒子可以转移到B%6==2的盒子...最后发现这样子:
0 -> 3 -> 0 -> 3
2 -> 1 -> 2 -> 1
5 -> 4 -> 5 -> 4
最后的1, 3, 4盒子都是不能继续转移的盒子,找出这样子一个转移公式貌似还是不大好做。首先对于每一个转移公式都是互不影响的,对于第一个转移公式我们可以发现如果当前决策者处于不利形势,他想要挽回形式而移动
x%6==3的盒子到x%6==0的盒子是完全没用的,因为对手总是可以继续把你转移的盒子再转移回x%6==3的盒子里使得你还是处于同样的劣势,所以在这里影响结果的只有x%6==0的盒子,最终是要把x%6==0的盒子里的移动到3这个盒子里,问题似乎就转换成了普通的NIM取石子游戏。。。sg值就是和NIM游戏一样为盒子里的卡片数!对于其他两个转移公式同样如此!
/* ********************************************** Author : JayYe Created Time: 2013-11-1 15:56:17 File Name : JayYe.cpp *********************************************** */ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int main() { int t, n, x, cas = 1; scanf("%d", &t); while(t--) { scanf("%d", &n); int ans = 0; for(int i = 1;i <= n; i++) { scanf("%d", &x); if(i % 6 == 0 || i % 6 == 2 || i % 6 == 5) // 影响结果的只有取余6为0, 2, 5的盒子 ans ^= x; } printf("Case %d: ", cas++); if(ans) puts("Alice"); else puts("Bob"); } return 0; }
补充:软件开发 , C++ ,