题目链接:http://codeforces.com/problemset/problem/841/B
题目大意:给你一个长度为n的数组,然后两个人玩游戏,第一个人只能拿走和为奇数的一段数,第二个人只能拿走和为偶数的一段数。每一次取完数组剩下的数然后就合并起来。问双方都用最好的策略,是谁赢。
思路:

    对于刚开始还没取的时候,如果数组所有的数都是偶数,只有这种情况第二个人才能赢。
    首先将问题简单化,用1表示奇数,用0表示偶数。因为偶数加偶数是偶数,奇数加奇数时偶数,偶数加奇数时奇数。
    对于刚开始,如果这串数组的所有数和是奇数,那么直接就是第一个人全部取完获胜。
    如果数组的所有数和是偶数,那么只有两种情况:
    1.所有的数都是偶数
    2.至少存在n对奇数
    对于第1种情况,那么就是第二个人全部取完获胜。
    如果对于第2种情况,那么肯定还是第一个人获胜。证明也很简单,任意选取一对奇数,用两个1来表示,其他的数用A、B、C来表示,可以表示为A1B1C。
    然后也有两种情况:
    1.ABC全为偶数
    2.ABC有一对是奇数(也是两种情况,AB为奇数,或者AC为奇数)
    **然后图片是对应的取法,不管哪种情况,都可以拆分成两部分奇数,然后第一就稳赢**
    ![然后图片是对应的取法,不管哪种情况,都要拆分成两部分奇数](https://img-blog.csdn.net/20180406020245356?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bvcl91bmFfY2FiemU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)
    然后,综上所述,只有,全部是偶数的话,第二个人才能赢。
    
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1000005;
int num[maxn];
int main()
{
    int n,flag;
    while(cin>>n)
    {
        flag=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&num[i]); 
            if(num[i]&1)
            {
                flag=1;    
            } 
        }
        if(flag) cout<<"First"<<endl;
        else cout<<"Second"<<endl;
    }
    return 0;
}
Last modification:September 19th, 2019 at 12:33 am
如果觉得我的文章对你有用,请随意赞赏