Problem - E - Codeforces
两个玩家正在玩一个游戏。他们有一个整数1，2，...，n的排列组合（排列组合是一个数组，其中从1到n的每个元素正好出现一次）。这个排列组合没有按升序或降序排序（即排列组合没有[1,2,...,n]或[n,n-1,...,1]的形式）。
最初，排列组合的所有元素都被染成红色。玩家轮流进行。在他们的回合中，玩家可以做三个动作之一。
重新排列组合的元素，使所有红色元素保持它们的位置（注意，蓝色元素可以相互交换，但这不是必须的）。
将一个红色元素的颜色改为蓝色。
跳过这一轮。
如果排列组合以升序排序（即变成[1,2,...,n]），则第一个玩家获胜。如果排列顺序为降序（即变成[n,n-1,...,1]），则第二个玩家获胜。如果游戏持续了100500个回合，没有人获胜，则以平局结束。
你的任务是确定如果双方都以最佳方式进行游戏，游戏的结果是什么。
输入
第一行包含一个整数t（1≤t≤105）--测试案例的数量。
每个测试案例的第一行包含一个整数n(3≤n≤5⋅105)--排列组合的大小。
第二行包含n个整数p1,p2,...,pn--排列组合本身。排列组合p不按升序或降序排序。
所有测试案例的n之和不超过5⋅105。
输出
对于每个测试案例，如果第一个玩家获胜，则打印 "第一"，如果第二个玩家获胜，则打印 "第二"，如果结果是平局，则打印 "平局"。
例子
inputCopy
4
4
1 2 4 3
3
2 3 1
5
3 4 5 2 1
6
1 5 6 3 2 4
outputCopy
第一个
捆绑
第二个
捆绑
注意
让我们看看在第一个例子中第一个玩家是如何获胜的。
他们应该在前两个回合中把元素3和4涂成蓝色，然后他们可以把蓝色元素重新排序，使排列组合成为[1,2,3,4]。第二位棋手既不能干扰这个策略，也不能更快获胜。
题解:
如果我们是玩家,我们应该怎么赢得游戏
假如我们是玩家1,
我们应该把所有原本元素不是按1 ~ n排列的位置涂上蓝色后,排序
如果我们是玩家2
我们应该把所有原本元素不是按照n~1排列的位置涂上蓝色后,排序
既然都想赢,那么肯定不会涂已经在应在的位置,
假如我是玩家1,肯定要优先涂数在降序排列的情况,这些对于玩家1是必须要涂的,不涂的话,另一个人肯定不会帮他涂啊,因为对于另一个人来说,这个位置已经排好序了(对于玩家2同理)
还有一种情况是,一个数他既不在升序排列的位置,也不在降序排列的位置,这种情况,两个人肯定,都想让对面涂,这种情况是非必要情况,因为即使我不涂,对面不涂的话,一样赢不了
结合以上情况,如何才能赢
肯定是我已经把必须的和不必需的涂完后,另一个人,还没有把必须涂的涂完,这样我才能赢
如果两个人都没有这种情况,说明一定是平局,
#include<iostream>#include<algorithm>#include<string>#include<queue>#include<vector>#include<map>#include<cstring>#include<cmath>using namespace std;#define int long longvoid solve(){int n;cin >> n;int x = 0,y = 0,z = 0;for(int i = 1;i <= n;i++){int p;cin >> p;if(p == i&&p!= n -i +1){x++;}else if(p != i&&p == n -i+1){y++;}else if(p!=i&&p!=n - i+1){z++;}}if(y+z <= x){cout << "First\n";}else if(z + x < y){cout <<"Second\n";}else{cout << "Tie\n";}}//3 8 4signed main(){//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);int t = 1;cin >> t;while(t--){solve();} }
