题目链接: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;
}