题目链接:http://codeforces.com/contest/1194/problem/D
题目大意是在标为0到n的n+1个格子中的最右边(指标为n的那一个),上有一个物品,游戏双方每次可以选择该物品左移(指标减小的方向)1格,2格或者\(k\ (k \ge 3)\)格。Alice先手,当有人试图把物品移出0号位置时该人判输。问该游戏谁会胜利。
物品放在0位置时是一个先手必败状态。如果一个位置能走到的位置中有一个是先手必败位置,该位置是先手必胜位置。如果一个位置能走到的位置全部都是先手必胜位置,该位置是一个先手必败位置。
首先,如果假设没有k的存在,每次只能移动1或2格,由于1和2构成了全部的3的非零余数,后手的人总可以使得当前移动的总步数是3的倍数。即如果\( n=0,3,6,\cdots,3k,\cdots \)总是先手必败。当n除3得别的余数时,先手可以通过一步使得剩下的距离为3的倍数,此时先手胜。
同样的道理,如果\( k=3 \),由于构成了4的全部非零余数,因此当$ n%4=0 $时先手必败,否则先手必胜。
当k较大时,此时设 \( k \ge 5 \) ,如果k模3得到了1或者2,实际上和之前的情况没有变化。当k模3等于0时,原本处在 \( k \) 位置的可以通过一步走到0,因此 \( k \)位置变为一个先手必胜位置, \( k+1 \)位置能走到的地方都是先手必胜位置,所以\( k+1 \)位置是一个先手必败位置。此后把\( k+1 \)位置当作0号位置考虑,就能发现先手必败位置的指标是按照$ k+1 $进行分块,块内部的相对于第一个格子的第\( k+1-4,k+1-8,\cdots,k+1-i*k,\cdots,3,0 \)的位置是必败位置。
AC代码
#include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <algorithm> #include <queue> #include <stack> #ifndef ONLINE_JUDGE #define debug(x) cout<<#x<<"=="<<x<<endl #else #define debug(x) ; #endif // ! #ifdef _MSC_VER #define scanf scanf_s #endif // _MSC_VER using namespace std; const int MAXN = 1e9 + 7; const int INF = (int)1e9 + 7; int main() { int T; scanf("%d", &T); while (T--) { int n, k; scanf("%d%d", &n, &k); bool bobwin; if (k == 3) { bobwin = n % 4 == 0; } else if (k % 3 != 0) { bobwin = n % 3 == 0; } else { n %= (k + 1); bobwin = n > k + 1 - 4 ? false : n % 3 == 0; } printf("%s\n", bobwin ? "Bob" : "Alice"); } return 0; }
Comments | NOTHING