CF1772E Permutation Game 题解
Moya_Rao
·
·
题解
题目大意
给定一个长度为 n 的排列 p，保证 p 一开始不为升序或降序。p 中的每个位置都可以染色，最开始所有位置都是红色。
小 A 和小 B 轮流玩游戏，小 A 第一回合，接着是小 B，以此类推。
每个回合，当前玩家可以：
- 选择一个红色的位置并将其染成蓝色；
- 随意排列所有蓝色位置的数字，注意红色位置的数字不能动；
- 跳过这一回合，什么也不执行。
当数列呈升序时，小 A 获胜；当数列呈降序时，小 B 获胜；如果重复 100^{500} 回合后仍没有呈升序或降序，则视为平局。
请你输出这场游戏的胜负情况，当然了，两人都会采取最优策略。具体来说，如果小 A 获胜则输出 First，如果小 B 获胜则输出 Second，平局就输出 Tie。
注意本题有 T 组数据。
# 思路
既然两人都会采取最优策略，那他们肯定不会将所有都染成蓝色，因为这相当于直接给对手胜利的机会。因此，他们各自肯定只会将对于自己来说位置错误的数染成蓝色。
那么对于每一个数，分三种情况：
1. 仅对于小 A 来说位置正确；
2. 仅对于小 B 来说位置正确；
3. 对于小 A 和小 B 来说位置都不正确。
我们不考虑都正确的情况，因为这个位置肯定不会被染成蓝色，是吧。
好的，那我们分别用变量 $a,b,c$ 来记录这三种情况。
接下来就很简单啦，我们只要判断一下谁需要染成蓝色的数更少啦，当然我们可以判断不用染色的，也是一个意思。不过要记得，小 A 是先手，支持等于，但是小 B 不支持哦。
这样就很简单啦，分类讨论一下即可：
- 当 $a \le b + c$ 时，小 A 获胜；
- 当 $b > a + c$ 时，小 B 获胜；
- 若以上两种均不满足，平局。
对应判断一下然后输出即可。注意多测清空哟。
代码编起来可简单了，只有 $20$ 行，要不还是自己写吧！
# 代码
虽然本题代码很简洁，但我还是放出来，给大家参考参考。嘿，不用担心，包是对的，不信的话看这个[提交记录](https://codeforces.com/contest/1772/submission/315709594)。注意咯，代码可以看，但是不要抄哦！
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int T,n,p[N],a,b,c;
int main(){
cin>>T;
while(T--){
cin>>n;a=0,b=0,c=0;
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=1;i<=n;i++){
if(p[i]==i)a++;
if(p[i]==n-i+1)b++;
if(p[i]!=i&&p[i]!=n-i+1)c++;
}
if(a>=b+c)cout<<"First\n";
else if(b>a+c)cout<<"Second\n";
else cout<<"Tie\n";
}
return 0;
}
```
如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，万分感谢！