CF-293A Weird Game 题解

题目大意

输入两串长度为2*n的0,1序列，一串是Y的，一串是A的。Y先手，A后手，每人可以任意选一个位置，选了之后两人都不能再选这个位置，比较他们的选择的串的大小。每人都是最优选择。

解题思路

很明显的博弈题目。。但是WA了我好几发。

（确实博弈相当苦手

分四种情况

1、1–1，这个肯定是优先选的，这样自己能选一个1，又能让对方少一个1.

2、1–0，这个除了1–1Y会优先选择，可以让Y多一个1.

3、0–1，这个除了1–1A会优先选择，可以让A多一个1.

4、0–0，这个肯定是最后选的。

把2记为ans1，3记为ans2。

如果1–1为奇数的话，就相当于第二种情况多加了一个，因为Y是先手，会优先选择这个。也就是ans1++。

答案情况也分为四种

1、ans1>ans2 这个情况，Y的1的数量大于A的1的数量，Y获胜。

2、ans1==ans2 这个情况，Y的1的数量等于A的1的数量，平局。

3、ans1==ans2-1 这个情况，A多了一个0–1，因为Y为先手，可以取掉这个，使Y和A相等，平局。（这个情况卡了我好久啊啊）

4、ans1<ans2-1 这个情况，Y的1数量小于A的数量，且差值大于1，故A获胜。

（博弈是真的难。。感觉自己智商不够。。太难想了

完整代码

#include <iostream>
using namespace std;

const int N = 2e6 + 5;
char ch1[N], ch2[N];

int main() {
	int n;
	cin >> n >> ch1 >> ch2;
	int ans1, ans2, cnt;
	ans1 = ans2 = cnt = 0;
	for (int i = 0; i < 2 * n; i++) {
		if (ch1[i] == '1' && ch2[i] == '0')	ans1++;
		if (ch1[i] == '0' && ch2[i] == '1')	ans2++;
		if (ch1[i] == '1' && ch2[i] == '1')	cnt++;
	}
	if (cnt % 2 != 0)	ans1 ++;
	if (ans1 > ans2)	cout << "First";
	else if (ans2 > ans1 + 1)	cout << "Second";
	else  cout << "Draw";
	cout << endl;
}