QuXiao

每天进步一点点!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 0 文章 :: 27 评论 :: 0 Trackbacks
    一开始看还以为是一道博弈的题目,再仔细看才发现并不是博弈,也不是很难。大致意思是:有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;
}


posted on 2007-12-07 21:41 quxiao 阅读(705) 评论(4)  编辑 收藏 引用 所属分类: ACM

评论

# re: PKU2975 Nim 2008-05-15 08:51 肖宪华
照你的代码写的,怎么我的就提交不了呢?
求助,代码如下
#include<stdio.h>
int main()
{
int n,i,k;
long long int stone[1001],t,p;
while(1)
{
scanf("%d",&n);
if(n==0) break;
for(i=0,t=0;i<n;i++)
{
scanf("%lld",&stone[i]);
t^=stone[i];
}
k=0;
if(t!=0)
{
for(i=0;i<n;i++)
{
p=t^stone[i];
if(stone[i]>t)
k++;
}
}
printf("%d\n",k);
}
return 0;
}


  回复  更多评论
  

# re: PKU2975 Nim 2008-05-15 09:01 肖宪华
怎么代码传上去,格式乱了呢,我在传遍吧,因为是照你写的,注释我没写了,见谅。呵呵
#include<stdio.h>
int main()
{
int n,i,k;
long long int stone[1001],t,p;
while(1)
{
scanf("%d",&n);
if(n==0) break;
for(i=0,t=0;i<n;i++)
{
scanf("%lld",&stone[i]);
t^=stone[i];
}
k=0;
if(t!=0)
{
for(i=0;i<n;i++)
{
p=t^stone[i];
if(stone[i]>t)
k++;
}
}
printf("%d\n",k);
}
return 0;
}
  回复  更多评论
  

# re: PKU2975 Nim 2008-05-16 09:38 肖宪华
这么没人提点下啊????  回复  更多评论
  

# re: PKU2975 Nim 2009-07-14 17:23 WinterLegend
@肖宪华
你代码打错了吧 !
你的 p 是干嘛用的。。。。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理