文章目录
题意思路AC代码三木老师的题解写的很棒
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;}