题目大意
有趣的取石子游戏即将开始。 有 (n) 堆石头，编号为 (0,1,2，...，n-1)。两个人轮流挑石头。
在每个回合中，每个人选择三堆编号为 (i,j,k) 的石头（ (i<jle k) 且堆 (i) 中至少留下一块石头）。 然后，这个人从堆 (i) 中取出一块石头，再将一块石头分别加入堆 (j) 和堆 (k) 中。如果他不能按照规则挑选石头就会失败。David 第一个选择石头，他希望赢得比赛。你能写一个程序来帮助他吗？
堆数 (n) 不超过 (23)。每堆中的石块数量不超过 (1000) 。 假设两人非常聪明，他们将遵循最优策略来挑选石头。
思路
首先我们可以发现每个石子都是单独的，于是我们可以对于每一个石子进行考虑，于是我们转换一下问题：
现在我们有很多个石子，每个石子可以有一个位置，每一次可以把一个石子移动到后面其他两个位置。
然后我们就发现答案其实只跟每堆石子的奇偶性相关（每堆里面每个石子都是相同的，异或 (2) 次相当于没有）
然后我们就可以用 sg 函数解决这个问题：
[sg(i)= ext{mex}{sg(j)oplus sg(k)}
]
然后时间复杂度就是 (Theta(n^3))。
( exttt{Code})
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 105
int n,a[MAXN],SG[MAXN];
bool vis[MAXN];
void Getsg ()
{
SG[n] = 0;
for (Int i = n - 1;i;-- i)
{
memset (vis,0,sizeof (vis));
for (Int j = i + 1;j <= n;++ j)
for (Int k = j;k <= n;++ k)
vis[SG[j] ^ SG[k]] = 1;
SG[i] = 0;while (vis[SG[i]]) SG[i] ++;
}
}
int read ()
{
int x = 0;char c = getchar();int f = 1;
while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}
while (c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + c - '0';c = getchar();}
return x * f;
}
void write (int x)
{
if (x < 0){x = -x;putchar ('-');}
if (x > 9) write (x / 10);
putchar (x % 10 + '0');
}
signed main()
{
int kase = 0;
while (scanf ("%d",&n) && n)
{
for (Int i = 1;i <= n;++ i) a[i] = read ();
Getsg ();
int ans = 0,flag = 0;
for (Int i = 1;i <= n;++ i) if (a[i] & 1) ans ^= SG[i];
printf ("Game %d: ",++ kase);
for (Int i = 1;i <= n - 1;++ i)
{
if (!a[i]) continue;
for (Int j = i + 1;j <= n;++ j)
for (Int k = j;k <= n;++ k)
if ((ans ^ SG[i] ^ SG[j] ^ SG[k]) == 0)
if (!flag) flag = 1,write (i - 1),putchar (' '),write (j - 1),putchar (' '),write (k - 1),putchar ('
');
}
if (!flag) puts ("-1 -1 -1");
}
return 0;
}