Game HDU - 3389 阶梯博弈,找出规律即可

按照题目意思,选取几个点,最后得出的图如下:
Game HDU - 3389 阶梯博弈,找出规律即可
图片来源于此

  • 根据上图的规律,发现没有出度的点是 1 , 3 , 4 1,3,4 1,3,4,换言之最后所有的石子都会归类到 1 , 3 , 4 1,3,4 1,3,4 这三个堆上,由此可得出这属于阶梯博弈。阶梯博弈的性质可以近似当成最后结果中,有些许堆的石子是无法被移出的,无论该堆的数量多少。
  • 根据阶梯博弈的性质,可以把 1 , 3 , 4 1,3,4 1,3,4 当成是阶梯博弈中的0号点,即偶数堆,其余的 m o d mod mod 6 ! = 1 , 3 , 4 !=1,3,4 !=1,3,4 的则是奇数堆。将奇数堆的个数进行 ⊕ \oplus ⊕ 即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uii;
typedef pair<int, ll> pii;
template<typename T>
inline void rd(T& x)
{
	int tmp = 1; char c = getchar(); x = 0;
	while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); }
	while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
	x *= tmp;
}
const int N = 2e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int n, m, k;
bool a[6] = { 1,0,1,0,0,1 };
int main() {
#ifdef _DEBUG
	FILE* _INPUT = freopen("input.txt", "r", stdin);
	//	FILE* _OUTPUT = freopen("output.txt", "w", stdout);
#endif // !_DEBUG
	int cas = 0, T = 0;
	rd(T);
	while (T--) {
		//	while (~scanf("%d", &n)) {
		int n; rd(n);
		int ans = 0;
		for (int i = 1; i <= n; ++i) {
			int x; rd(x);
			if (a[i % 6]) ans ^= x;
		}
		printf("Case %d: ", ++cas);
		if (ans) puts("Alice");
		else puts("Bob");
	}
	return 0;
}
上一篇:【雷达通信】距离多普勒(RD)、CS、RM算法的机载雷达成像matlab源码


下一篇:计算机组成原理实验:静态随机存储器实验