UVA1482 Playing With Stones 题目分析
分析题目性质
这是一道博弈论题目，没有比较明显的结论后我们一般采用打表 \(SG\) 函数，然后找规律。
思路
经过上述，我们不难得到打表 \(SG\) 的代码（由于原本要到 \(10^{18}\)，但数组存不下，这里只能考虑取样调查）：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stdlib.h>
#define N 105
#define int long long
using namespace std;
int sg[114514],T,a[N],n;
bool vis[114514];
signed main(){
sg[1] = 0;
for (int i = 2;i <= 15;i ++) {
memset(vis,0,sizeof vis);
for (int j = 1;j * 2 <= i;j ++)
vis[sg[i - j]] = 1;
for (int j = 0;;j ++)
if (!vis[j]) {
sg[i] = j;
break;
}
cout << sg[i] << ' ';
}
return 0;
}
程序的输出如下：
1 0 2 1 3 0 4 2 5 1 6 3 7 0
把 \(SG(1)=0\) 加进来就是在前面多了一个 \(0.\)
我们似乎发现了一些规律：
- 对于 \(x\) 为偶数，那么它的 \(SG(x)=\frac{x}2.\)
把偶数项删掉，得到：
0 1 0 2 1 3 0
我们发现这和原来的 \(SG\) 前 \(\frac{len}{2}\) 个是一样的（假设 \(len\) 为原本长度）。
于是又得到了：
- 当 \(x\) 为奇数时，那么它的 \(SG(x)=SG(\lfloor\frac{x}{2}\rfloor).\)
这个过程的时间复杂度为 \(\mathcal{O}(\log x)\) 的。
那么我们不难用以下程序实现，时间复杂度 \(\mathcal{O}(n\log a_i)\)：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stdlib.h>
#define N 105
#define int long long
using namespace std;
int T,n;
int sg(int x) {
if (x & 1) return sg(x / 2);
else return x / 2;
}
signed main(){
cin >> T;
for (;T--;) {
cin >> n;
int v = 0;
for (int i = 1,x;i <= n;i ++) {
cin >> x;
v ^= sg(x);
}
if (v) puts("YES");
else puts("NO");
}
return 0;
}