CodeForces 1194D 1-2-K Game

发布于 2019-07-15  498 次阅读


题目链接: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;
}

终有一日, 仰望星空