HDU 2509 Be the Winner(博弈论入门题)_c语言be the winner-程序员宅基地

技术标签: 模板题  # 数学博y论  博弈论  

Be the Winner

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3471    Accepted Submission(s): 1940


Problem Description
Let's consider m apples divided into n groups. Each group contains no more than 100 apples, arranged in a line. You can take any number of consecutive apples at one time.
For example "@@@" can be turned into "@@" or "@" or "@ @"(two piles). two people get apples one after another and the one who takes the last is 
the loser. Fra wants to know in which situations he can win by playing strategies (that is, no matter what action the rival takes, fra will win).
 

Input
You will be given several cases. Each test case begins with a single number n (1 <= n <= 100), followed by a line with n numbers, the number of apples in each pile. There is a blank line between cases.
 

Output
If a winning strategies can be found, print a single line with "Yes", otherwise print "No".
 

Sample Input
  
  
   
2 2 2 1 3
 

Sample Output
  
  
   
No Yes
 

Source
 
题目分析:这是一个nim博弈,具体请见博客:http://blog.csdn.net/acm_cxlove/article/details/7854530

掌握以上规律后,就可以很轻松的做出来了


代码如下:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;int cun[105];int x;
int main(){
    scanf("%d",&x);
    while(x--){
    scanf("%d",&n);
    memset(cun,0,sizeof(cun));
    int res=0;
    for(int i=0;i<n;i++){
    scanf("%d",&cun[i]);
    if(cun[i]>1)res++;
    }
    bool flag=false;
    if(res==1&&n>1){
       flag=true;
    }
    else if(res==0)
    {
        if(n%2==0)flag=true;
    }
    else {
        int ji=cun[0];
        for(int i=1;i<n;i++)
            ji=ji^cun[i];
        if(ji!=0)flag=true;
    }
    if(flag)printf("John\n");
    else printf("Brother\n");
}
return 0;
}




版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lwgkzl/article/details/55003696

智能推荐

python编码问题之encode、decode、codecs模块_python中encode在什么模块-程序员宅基地

文章浏览阅读2.1k次。原文链接先说说编解码问题编码转换时,通常需要以unicode作为中间编码,即先将其他编码的字符串解码(decode)成unicode,再从unicode编码(encode)成另一种编码。 Eg:str1.decode('gb2312') #将gb2312编码的字符串转换成unicode编码str2.encode('gb2312') #将unicode编码..._python中encode在什么模块

Java数据流-程序员宅基地

文章浏览阅读949次,点赞21次,收藏15次。本文介绍了Java中的数据输入流(DataInputStream)和数据输出流(DataOutputStream)的使用方法。

ie浏览器无法兼容的问题汇总_ie 浏览器 newdate-程序员宅基地

文章浏览阅读111次。ie无法兼容_ie 浏览器 newdate

想用K8s,还得先会Docker吗?其实完全没必要-程序员宅基地

文章浏览阅读239次。这篇文章把 Docker 和 K8s 的关系给大家做了一个解答,希望还在迟疑自己现有的知识储备能不能直接学 K8s 的,赶紧行动起来,K8s 是典型的入门有点难,后面越用越香。

ADI中文手册获取方法_adi 如何查看数据手册-程序员宅基地

文章浏览阅读561次。ADI中文手册获取方法_adi 如何查看数据手册

React 分页-程序员宅基地

文章浏览阅读1k次,点赞4次,收藏3次。React 获取接口数据实现分页效果以拼多多接口为例实现思路加载前 加载动画加载后 判断有内容的时候 无内容的时候用到的知识点1、动画效果(用在加载前,加载之后就隐藏或关闭,用开关效果即可)2、axios请求3、map渲染页面4、分页插件(antd)代码实现import React, { Component } from 'react';//引入axiosimport axios from 'axios';//引入antd插件import { Pagination }_react 分页

随便推点

关于使用CryPtopp库进行RSA签名与验签的一些说明_cryptopp 签名-程序员宅基地

文章浏览阅读449次,点赞9次,收藏7次。这个变量与验签过程中的SignatureVerificationFilter::PUT_MESSAGE这个宏是对应的,SignatureVerificationFilter::PUT_MESSAGE,如果在签名过程中putMessage设置为true,则在验签过程中需要添加SignatureVerificationFilter::PUT_MESSAGE。项目中使用到了CryPtopp库进行RSA签名与验签,但是在使用过程中反复提示无效的数字签名。否则就会出现文章开头出现的数字签名无效。_cryptopp 签名

新闻稿的写作格式_新闻稿时间应该放在什么位置-程序员宅基地

文章浏览阅读848次。新闻稿是新闻从业者经常使用的一种文体,它的格式与内容都有着一定的规范。本文将从新闻稿的格式和范文两个方面进行介绍,以帮助读者更好地了解新闻稿的写作_新闻稿时间应该放在什么位置

Java中的转换器设计模式_java转换器模式-程序员宅基地

文章浏览阅读1.7k次。Java中的转换器设计模式 在这篇文章中,我们将讨论 Java / J2EE项目中最常用的 Converter Design Pattern。由于Java8 功能不仅提供了相应类型之间的通用双向转换方式,而且还提供了转换相同类型对象集合的常用方法,从而将样板代码减少到绝对最小值。我们使用Java8 功能编写了..._java转换器模式

应用k8s入门-程序员宅基地

文章浏览阅读150次。1,kubectl run创建pods[root@master ~]# kubectl run nginx-deploy --image=nginx:1.14-alpine --port=80 --replicas=1[root@master ~]# kubectl get podsNAME READY STATUS REST...

PAT菜鸡进化史_乙级_1003_1003 pat乙级 最优-程序员宅基地

文章浏览阅读128次。PAT菜鸡进化史_乙级_1003“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。得到“答案正确”的条件是: 1. 字符串中必须仅有 P、 A、 T这三种字符,不可以包含其它字符; 2. 任意形如 xPATx 的字符串都可以获得“答案正确”,其中 x 或者是空字符串,或..._1003 pat乙级 最优

CH340与Android串口通信_340串口小板 安卓给安卓发指令-程序员宅基地

文章浏览阅读5.6k次。CH340与Android串口通信为何要将CH340的ATD+Eclipse上的安卓工程移植到AndroidStudio移植的具体步骤CH340串口通信驱动函数通信过程中重难点还存在的问题为何要将CH340的ATD+Eclipse上的安卓工程移植到AndroidStudio为了在这个工程基础上进行改动,验证串口的数据和配置串口的参数,我首先在Eclipse上配置了安卓开发环境,注意在配置环境是..._340串口小板 安卓给安卓发指令