CF1747C Swap Game 题解

Fengyiwei1234 · 2023-06-24 13:53:45 · 题解

题目传送门

思路：博弈论

因为 Alice 是先手，所以为了使第一个变成零最快，他一定会让 {a}_{1} 与之后最小的那个进行交换。

所以只需要考虑 {a}_{1} 是否是最小的即可。

如果 {a}_{1} 是最小的，那么 Bob 赢，否则 Alice 赢。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int T,n,a[N];
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        int minn=-1;bool flag=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[1]>a[i])flag=1;
        }
        if(flag)cout<<"Alice"<<endl;
        else cout<<"Bob"<<endl;
    }
    return 0;
}

AC 记录