题解：P12079 [OOI 2025] Card Flip

diqiuyi · 2025-04-09 15:23:04 · 题解

注意到谁能抢到最后一个能翻面（即 a 最大的）的卡片，谁就赢了，因为是否翻转这张卡片带来的是相反的结果，必然有一种可能使得当前的决策者获胜。

我们记这张卡片为 x。

考虑什么样的卡片能影响 x 的归属，发现是满足 a_i<a_x\land b_i>a_x 且 a_i 最大的 i。也就是说谁抢到 i 谁就能获胜。

注意到这个找卡片的过程可以递归，那么只要一直找到新的 x，最后判断它将被谁拿到即可（显然这是固定的，不会被决策影响）。

具体实现上可以先按 a 从小到大排序，每次暴力往前找即可，时间复杂度为 O(n\log n)，桶排可以做到 O(n)。

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define uint unsigned int
#define pii pair<int,int>
#define io ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) 
using namespace std;
inline int read(){
    int x=0;bool f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return f?x:-x;
}
int n,m;
pii p[500005];
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) p[i].first=read();
    for(int i=1;i<=n;i++) p[i].second=read();
    sort(p+1,p+n+1);
    int now=n;
    while(1){
        int i;
        for(i=now-1;i;i--)
            if(p[i].second<p[now].first)
                break;
        if(!i) break;
        now=i;
    }
    bool flg=1;
    for(int i=1;i<now;i++)
        flg^=(p[i].second>p[now].first);
    for(int c;m--;)
        c=read(),flg^=(c<p[now].first);
    cout<<(flg?"First\n":"Second\n");
    return 0;
}