一开始看还以为是一道博弈的题目,再仔细看才发现并不是博弈,也不是很难。大致意思是:有n堆石子,第i堆有Ki个石子,每轮一方可以从任意堆中取出一个或多个石子,所有石子都被取光时,游戏也结束了,那个最后一轮拿走石子的人就是胜利者。问你有多少种方法使对方处于必败的局面。题目并不难,是因为题目中已经告诉你了产生必败局面的条件:如果所有堆的石子数的异或和为0,那么处于此局面的人就必败。
因为每次只能从一个堆中取石子,所以只要对于每个堆i,先求出其他所有堆的异或和temp,再看0~Ki-1与这个异或和再进行异或是否为0,只要为0就得到一种胜利的方法。自己先是想枚举0~Ki-1,与temp进行异或。后来感觉没有必要,只要Ki>temp就可以了,因为若从堆i中取出x个石子,Ki-x异或temp==0 <==> Ki-x==temp,只要Ki>temp,就存在Ki-x==temp。
#include <cstdio>
#define PILE 1001
__int64 stone[PILE], test; //test为所有石子数的异或和
int piles;
bool Input ()
{
scanf("%d", &piles);
if ( piles == 0 )
return false;
int i;
for (i=0; i<piles; i++)
scanf("%I64d", &stone[i]);
return true;
}
void Solve ()
{
int i, ans;
__int64 temp;
test = 0;
ans = 0;
for (i=0; i<piles; i++)
test ^= stone[i];
if ( test != 0 )
{
for (i=0; i<piles; i++)
{
temp = test ^ stone[i]; //再与stone[i]做一次异或,相当于除stone[i]对其他所有堆的石子进行异或
if ( stone[i] > temp )
ans++;
}
}
printf("%d\n", ans);
}
int main ()
{
while ( Input() )
{
Solve();
}
return 0;
}