dreamangel
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  14 随笔 :: 0 文章 :: 0 评论 :: 0 Trackbacks
foj 1534 阿甘的珠宝
http://acm.fzu.edu.cn/problem.php?pid=1534
Nim游戏改进型，SG函数x%3（x为某一堆的石子数量）
首先统计各堆石子%3的结果，
（1）如果%3以后全部为1，则把最后的胜负情况当作第n+1堆石头，把n+1堆石头数分别%3后异或，当结果为0时必败，反之必胜。
（2）如果%3以后全部为1或者0，处理的方式参照（1），因为所有%3为0的情况都可以设法保证用偶数次取完，%为0的堆数对胜负不产生影响。
（3）余下的情况下，即%3以后全部为1或者2的情况，只要统计1和2的情况的个数是不是都是偶数，如果是偶数，则必败，反之必胜。
#include <iostream>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        int i,x,sum=0,f,k1=0,k2=0,flag;
        for(i=0;i<n;i++){
            cin>>x;
            x%=3;
            if(x==1)
                k1++;
            else if(x==2)
                k2++;
            sum = sum^x;
        }
        cin>>f;
        if(k1==n || k2==0)
            flag = sum^f;
        else if(k1%2==0 && k2%2==0)
            flag = 0;
        else
            flag = 1;
        if(flag==1)
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}
posted on 2010-09-03 10:27 飞翔天使 阅读(268) 评论(0)  编辑 收藏 引用 所属分类: ACM

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