[OOI 2025] Card Flip

Tairitempest · 2025-04-13 16:35:26 · 题解

[OOI 2025] Card Flip

卡片没有固定的顺序，因此我们可以先把卡片排序。

我们看看只有单面卡片会发生什么。

如果只有单面卡片是很好做的，判断一下奇偶性就可以判断谁会赢了。

现在让我们加入一张双面卡片。

当这个游戏只有一张双面卡片的时候，我们假设某个人最终可以拿到了双面卡片。

当这个双面卡片右侧剩下的单面卡片数量可以使先手胜利时，那么就可以翻转这张卡片；否则就可以直接取走这张卡片，那么拿到这张双面卡的人一定可以取得胜利。

现在让我们加入更多的双面卡片。

显然根据前面的推断，拿到最后一张双面卡的人一定可以取得胜利。

让我们考虑一下拿到最后一张双面卡需要什么条件。如果能够拿到倒数第二张双面卡，考虑这个双面卡能不能改变局势——而这取决于它的反面大小是否大于下一张有效的双面卡正面大小。如果是的，那么它被翻过以后就会被放到下一张有效的双面卡后面，也就是说相当于一张单面卡，可以无视；否则它就是一张有效的双面卡。拿到了一张有效的双面卡意味着必定得到胜利。

这么判断下来，可以从后往前，根据后面的双面卡，推出会先被拿的有效的双面卡。

最后判断一下第一张被拿的有效的双面卡前面有几个卡牌会被取就可以了。第一个拿到有效的双面卡的人一定可以取得胜利。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct db{
    ll a,b;
} d[500010];
ll n,m,c[500010],lst,ans;
bool comp(db a,db b){
    return a.a<b.a;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>d[i].a;
    for(int i=1;i<=n;i++) cin>>d[i].b;
    for(int i=1;i<=m;i++) cin>>c[i];
    sort(d+1,d+n+1,comp);
    lst=n;
    for(int i=n-1;i>=1;i--)
        if(d[i].b<d[lst].a) lst=i;
    for(int i=1;i<=m;i++) if(c[i]<d[lst].a) ans++;
    if((ans+lst)%2) cout<<"First"<<endl;
    else cout<<"Second"<<endl;
    return 0;
}