Codeforces Round #429 (Div. 2) B. Godsend

落日映苍穹つ 2024-03-30 12:48 53阅读 0赞

[Problem - B - Codeforces][]

题意：

给定一个数列，先手可以remove一段区间和为奇数的区间，后手可以remove一段区间和为偶数的区间，问你赢家是谁？

思路：

博弈题按状态的思想去思考问题

假设我是先手

先去确定它的必胜态和必败态

我的必胜态就是所有加起来和为奇数

对方的必胜态就是所有加起来是偶数

那么我们怎么去推导必败态？

我的必败态不管做什么决策，都只能指向**对方的**必胜态

也就是说，**一个未知的状态**，不论怎么拿，所有加起来都是偶数

众所周知，偶数-偶数=偶数

因此这个未知的状态就是：全部都是偶数，没有奇数

因此，没有奇数，就是我的必败态

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10,mod=1e9+7;
    int n,sum=0;
    int a[mxn];
    void solve(){
    	sum=0;
    	cin>>n;
    	int ok=0;
    	for(int i=1;i<=n;i++){
    		cin>>a[i],sum+=a[i];
    		if(a[i]%2==1) ok=1;
    	}
    	if(sum%2==1) cout<<"First"<<'\n';
    	else{
    		if(ok) cout<<"First"<<'\n';
    		else cout<<"Second"<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

**总结：**

**博弈题按状态去思考问题**

**先去确定我的必胜态和必败态**

**然后再去根据特性：**

**我的必败态不管做什么决策，都只能指向对方的必胜态**

**去确定我的必败态是啥就行**

**对方的必胜态是已知的**

**一个特性需要留意一下：**

**奇数个奇数相加是奇数**

**偶数个奇数相加是偶数**

**这里很像异或**

**奇数个1异或是1**

**偶数个1异或是0**

[Problem - B - Codeforces]: https://codeforces.com/contest/841/problem/B

发表评论取消回复

表情：

评论列表（有 0 条评论，53人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #651 (Div. 2) B. GCD Problem

[Problem - 1617B - Codeforces][] 题意：给定一个n，让你构造a,b,c，满足 a+b+c=n，且gcd(a,b)=c 思路：设 c

爱被打了一巴掌/ 2024年03月31日 13:41/ 0 赞/ 63 阅读

相关 Codeforces Round #429 (Div. 2) B. Godsend

[Problem - B - Codeforces][] 题意：给定一个数列，先手可以remove一段区间和为奇数的区间，后手可以remove一段区间和为偶数的区间，问你

落日映苍穹つ/ 2024年03月30日 12:48/ 0 赞/ 54 阅读

相关 Codeforces Round #572 (Div. 2)B

B. Number Circle 题目链接：[http://codeforces.com/contest/1189/problem/B][http_codeforces.

小灰灰/ 2023年08月17日 15:40/ 0 赞/ 133 阅读

相关 Codeforces Round #620 (Div. 2)：B. Longest Palindrome

Discription Returning back to problem solving, Gildong is now studying about palindrom

「爱情、让人受尽委屈。」/ 2023年07月06日 06:23/ 0 赞/ 8 阅读

相关 Codeforces Round #688 (Div. 2) A，B

A Cancel the Trains [传送门][Link 1] 题目大意有 100 个从下向上的火车道，100 个从左向右的火车道，如图所示 ![车

╰半夏微凉°/ 2022年12月26日 11:16/ 0 赞/ 128 阅读

相关 Codeforces Round #663 (Div. 2) B题

[题目链接][Link 1] include <cstdio> include <iostream> using namespace std

àì夳堔傛蜴生んèń/ 2022年11月26日 07:38/ 0 赞/ 159 阅读

相关 Codeforces Round #743 (Div. 2) B. Swaps 思维

题目地址[Codeforces Round \743 (Div. 2) B. Swaps][Codeforces Round _743 _Div. 2_ B. Swaps]

深碍√TFBOYSˉ_/ 2022年09月14日 06:27/ 0 赞/ 169 阅读

相关 Codeforces Round #551 (Div. 2) （A,B,C）

一开始做出来两道题，提交第三题一直wa,就在这个时候A题突然被人hack了，啊啊啊~我是猪吗？！A题也能错！刚刚看A题的时候，才发现怎么代码里还有一个n--，什么鬼？！一定

太过爱你忘了你带给我的痛/ 2022年02月20日 15:09/ 0 赞/ 203 阅读

相关 Codeforces Round #541 (Div. 2) B.Draw!

链接：https://codeforces.com/contest/1131/problem/B 题意：给n次足球比分，求存在平局的机会。思路：结构体

今天药忘吃喽~/ 2021年12月23日 11:29/ 0 赞/ 234 阅读

相关 Codeforces Round #568 (Div. 2)B

B. Email from Polycarp 题目链接：[http://codeforces.com/contest/1185/problem/B][http_codef

Myth丶恋晨/ 2021年12月03日 22:43/ 0 赞/ 234 阅读