经典的 Nim 博弈,数组相当于一堆石子,每个数对应一堆石子,石子相当于这个数字的质因子数。
然后,判别所有数字的因子数是否为 0。 如果为 0 是一个必输局面,否则就是必胜局面。 要从必胜局面里面选择一个 move,只需要令局面变成必输局面,也就是使得总异或等于 0。
那么假设初始异或为 x,我只需要找到第一个数 a[i],使得 a[i] – (a[i]^x) > 0 即可,那么我们就可以从第 i 堆里面取走 a[i] – (a[i]^x) 个质因子,从而使得 a[i] 变成了 a[i]^x,相当于总异或值异或了一个 x,使得总异或变成 0,而将一个必输局面交给了 Bob。
上面很啰嗦,总而言之,如果是 Alice,找到第一个 a[i] 使得 a[i] – (a[i]^x) > 0 就是最后的策略数字。
参考 Wikipedia: http://en.wikipedia.org/wiki/Nim
这道题算法不难,但是数据量有撑得非常大,没法用 python 过,只好用 c++。
// 3493552 2013-12-21 17:18:23 Accepted 3529 C++ 2680 564 呆滞的慢板
// 经典 Nim
#include <cstdio>
#include <cstring>
const int MXP = 2236;
bool b[MXP] = {};
int p[331], a[100000], np = 0, i, j, n, t = 0;
int f(int x) {
int ans = 0;
for(int k = 0; k < np; ++k) {
while(x % p[k] == 0) {
x /= p[k];
ans += 1;
}
if(x == 1) return ans;
}
return x == 1 ? ans : ans + 1;
}
int main() {
for(i = 2; i < MXP; ++i) {
if(!b[i]) {
p[np++] = i;
for(j = i*i; j < MXP; j+=i) b[j] = true;
}
}
while(scanf("%d", &n) != EOF) {
int ans = 0;
for(i = 0; i < n; ++i) {
scanf("%d", a+i);
ans ^= (a[i] = f(a[i]));
}
if(ans) {
for(i = 0; i < n; ++i) {
if((ans^a[i]) <= a[i]) {
printf("Test #%d: Alice %d\n", ++t, i+1);
break;
}
}
}
else printf("Test #%d: Bob\n", ++t);
}
}
【转载请附】愿以此功德,回向 >>
原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3529.html【zoj 3529 – A Game Between Alice and Bob】