博弈论
我们假设A是先手,B是后手
对于两人来说,最优策略就是先把不在正序(or逆序)正确位置的数染上色,乘对方还没有染完,就交换
总共有三种情况:
- A需要染,B不需要染 \(\Longrightarrow\) a
- B需要染,A不需要染 \(\Longrightarrow\) b
- A和B都需要染 \(\Longrightarrow\) c
b \(>=\) a+c,则A赢(A是先手,所以可以取等)
a \(>\) b+c,则B赢
其他情况都是平局
AC代码如下:
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
typedef long long ll;
void solve()
{
int n;
int a=0, b=0, c=0;
cin >> n;
for(int i=1; i<=n; i++)
{
int x;
cin >> x;
if(x != i && x == n-i+1) a++;
if(x != n-i+1 && x == i) b++;
if(x != i && x != n-i+1) c++;
}
if(a == b && c!=0) puts("Tie");
else if(a > b)
{
if(a > b+c) puts("Second");
else puts("Tie");
}
else
{
if(b >= a+c) puts("First");
else puts("Tie");
}
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
标签:puts,int,839,CF,else,Game,&&,Longrightarrow,Tie
From: https://www.cnblogs.com/zhouzhihao/p/17093051.html