C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

NYOJ 137 取石子(三)解题报告

Posted on 2012-01-15 17:46 C小加 阅读(1540) 评论(0)  编辑 收藏 引用 所属分类: 解题报告
不愧是楼教主的男人八题之一,我想了很久都没有头绪,最后只能百度了。度娘说,N是偶数且每个数出现偶数次的状态为必败态。我尝试了一下,不管后手如何取,只要留给先手不是必败态,那么先手总能有一种取法使状态变为必败态,而当处于必败态时无论如何取都肯定能转化成非必败态。这样每次都转化成必败态给对手,就肯定能取胜。
知道思想后,代码就很简单了。


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[103];
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        int b;
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        {
            scanf("%d",&b);
            a[b]++;
        }
        int f=0;
        if(n%2!=0)
        {printf("Win\n");continue;}
        for(int i=0;i<=100;i++)
        {
            if(a[i]%2!=0)
            {
                f=1;
                break;
            }
        }
        if(f) printf("Win\n");
        else printf("Lose\n");
    }

    return 0;
}

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