HDU-1850-Being a Good Boy in Spring Festival

浏览数：24 / 时间：2015年06月08日

题目链接：

这个题目不难，不过我开始题目意思理解错了，注意一点，一堆牌最多只能取一次，只能有一种选择，

看代码

低级代码

#include<stdio.h>

int main(void)

{

int m,i,j,s,k;

int a[105];

while(scanf("%d",&m)==1&&m)

{

for(i=0;i<m;i++)

scanf("%d",&a[i]);

k=0;

for(i=0;i<m;i++)

{

s=0;

for(j=0;j<m;j++)

{

if(i==j)

continue;

s=s^a[j];

}

if(a[i]>s)

k++;

}

if(k)

printf("%d\n",k);

else

printf("0\n");

}

return 0;

}

低级代码

#include<stdio.h>

int main(void)
{
int m,i,j,k,s,s1,s2;
int a[105];
while(scanf("%d",&m)==1&&m)
{
s=0;
for(i=0;i<m;i++)
{
scanf("%d",&a[i]);
s=s^a[i];
}
if(s)
{
k=0;
for(i=0;i<m;i++)
{
/*for(j=0;j<m;j++)
{
if(i==j)
continue;
s1=s1^a[j];
}*/
s1=s;
s1=s1^a[i];
for(j=1;j<=a[i];j++)
{
s2=s1;
s2=s2^(a[i]-j);
if(s2==0)
{
k++;
break;
}
}
}
printf("%d\n",k);
}
else
printf("0\n");
}
return 0;
}

看高级代码

思路

经典的博弈题啊，必须弄懂必败点条件。这里是对n堆的牌数去异或，如果值为0则表示必败。题目问我们第一布有哪几种方法胜利。

即就是第一步能够给对手构建多少个必败点。

由于一次只能对一堆排进行操作，假设我操作第i堆牌（a张），抽出x张。

那么其余n-1堆牌的异或值是固定为b.

那么（a - x）^ b == 0 时，对手必败。

到此可能有人像我一样觉得必须历遍所有a求出那个值x满足条件。其实不必要

由上式可知x只有唯一取值

而且一个数与 b 异或等于 0 即表明这个数等于b.

所以反过来我们可以求出b, 令 a - x = b ;

只要b满足 b < a; 即能构造出x使得（a - x）^ b == 0 时，对手必败！

代码

#include<stdio.h>

int main(void)

{

int m,i,j,s,k;

int a[105];

while(scanf("%d",&m)==1&&m)

{

for(i=0;i<m;i++)

scanf("%d",&a[i]);

k=0;

for(i=0;i<m;i++)

{

s=0;

for(j=0;j<m;j++)

{

if(i==j)

continue;

s=s^a[j];

}

if(a[i]>s)

k++;

}

if(k)

printf("%d\n",k);

else

printf("0\n");

}

return 0;

}

代码

#include<stdio.h>
int main(void)
{
int n,a[111];
int i,j,s,s1,k;
while(scanf("%d",&n)==1&&n)
{
s=0;
k=0;
for(i=0;i<n;i++)
{
scanf("%d",a+i);
s=s^a[i];
}
if(s)
{
for(i=0;i<n;i++)
{
s1=s;
s1=s1^a[i];
if(a[i]>s1)
k++;
}
printf("%d\n",k);
}
else
printf("%d\n",k);
}
return 0;
}