文章目录

三木老师的题解写的很棒

E. Permutation Game

题意

题意：给我们一个串，初始的时候全都是红色，如果先手能把序列变成递增的，后手如果可以变成递减的，那么对应的人就胜出，要不然的话就是平局。

每一个人可以进行三个操作，第一个是把红色染成蓝色，每次只能染一个。第二个是可以对蓝色的位置进行重排。第三个是跳过。

思路

思路：我们发现，对于任何一个序列的话我们必须把要染色的部分全部蓝色。我们才能全部排序排好。但是如果只差一个的话，那么不管是先手还是后手，那么他们的选择肯定是跳过。那么这种情况的话就是平局。

对于先手来说的话，不须要染色的部分就是a[i]=i的部分，然后需要染色部分就是其他的部分。那么对于后手来说的话，a[i]=n-i+1的位置就是他不需要染色的位置。那么这样的话我们就可以统计一下上述两种情况的个数。然后剩下不是上述两种情况的情况看做第三种情况。我们假设第一种情况的个数是cnt1,第二种情况的个数是cnt2，然后第三种情况的个数是cnt3。首先先手如果想赢得话就必须是 c n t 2 + c n t 3 < = c n t 1 cnt2+cnt3<=cnt1 cnt2+cnt3<=cnt1，但是后手想要赢的话我们就是 c n t 1 + c n t 3 < c n t 2 cnt1+cnt3<cnt2 cnt1+cnt3<cnt2这里是不能想等的，因为先手会比后手相对早走一步，那么这样的话相等的情况下我们此时先手肯定也满足条件，那么就可以直接胜利。

AC代码

#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 1e6 + 10;int a[N];void solve(){int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];int cnt1 = 0, cnt2 = 0, cnt = 0;for (int i = 1; i <= n; i++){if (a[i] == i)cnt1++;if (a[i] == n - i + 1)cnt2++;if (a[i] != i && a[i] != n - i + 1)cnt++;}if (cnt2 + cnt <= cnt1)cout << "First" << endl;else if (cnt1 + cnt < cnt2)cout << "Second" << endl;elsecout << "Tie" << endl;}int main(){ios::sync_with_stdio(false);cin.tie(0);int T;cin >> T;while (T--){solve();}return 0;}