题目
https://vjudge.net/problem/HDU-3389
题意
1-N带编号的盒子,当编号满足A>B && A非空 && (A + B) % 3 == 0 && (A + B) % 2 == 1则可以从A中取任意卡片到B中,谁不能取了谁就输。
思路
阶梯博弈
阶梯博弈等效为奇数号阶梯的尼姆博弈。
假设我们是先手。我们按照尼姆博弈的原则进行第一次移动。如果对方移动奇数号阶梯的石子,我们继续按照尼姆博弈的原则移动。如果对方移动的是偶数号阶梯的石子,及对方将偶数号阶梯的石子移动到了奇数号(对奇数号产生了影响)我们就接着将对方移动到奇数号的石子再向下移动一个台阶,移动到偶数号。这就意味着在偶数号的棋子对我们的博弈是没有影响的。
这个题所有的对于原始阶梯博弈来说 i%6=0,2,5相当于偶数 i%6=1,3,4相当于奇数
0,2,5一步只能移动到1,3,4 1,3,4除了1,3,4一步只能移动到0,2,5
代码
#include <bits/stdc++.h>using namespace std;
const int maxn = 1e6+100;int main()
{int T;scanf("%d",&T);int ca= 1;while(T--){int n;scanf("%d",&n);int ans = 0;for(int i = 1;i <= n;i++){int x;scanf("%d",&x);if(i%6==0||i%6==2||i%6==5){ans ^= x;}}printf("Case %d: ",ca++);if(ans ) printf("Alice\n");else printf("Bob\n");}return 0;
}