[ARC105E] Keep Graph Disconnected 题解

· · 题解

赛时冲了两个多小时没冲出来，想得断断续续，导致没想到如何处理奇偶。

思路

根据限制条件一，可以知道最后的图一定是两个连通块，其中一块包含 1，另一块包含 n。因为此时再想连边就必须连通两个块，使其不合法了。

每次操作都是新增一条边，那么到最后的边数是多少呢？假设其中一个连通块有 k 个点，另一个则有 n-k 个点。两个连通块间肯定不会连边，因此这些没连的边就有 k(n-k) 条。如果没有限制，那么 n 个点之间就会互相连边，共有 \frac{n(n-1)}{2} 条边。再减去题目上已经给出的边，两个连通块内就一共会有会有 \frac{n(n-1)}{2} - m - k(n-k) 条边。

这时我们再来思考，先手获胜的条件是什么？谁不能操作就输了，因此先手想赢必须要刚好把需要放的边放完，也就是在上述式子值为奇时，先手获胜。观察发现，除了 k 是变量，其他条件我们都已知，也就是前面一部分的奇偶我们是知道的，因此根据后面的奇偶分讨即可。

以 n 的奇偶性分析。

  1. 当 1 号点所在连通块与 n 号点所在连通块奇偶性不相同时，又因为 n 为偶数，因此剩下的点个数一定是奇数个，也就是一定会有奇数个奇数连通块。先手可以根据自己的需求将一个奇数连到 1 号或 n 号，改变它的奇偶性，让两个块都变成自己需要的奇/偶。这样奇数块个数变成偶数，先手变为后手，于是现在的后手就可以“跟在”现在的先手后面，先手连哪个块后手就跟着连，两个奇数相加又变成偶数，对块的奇偶不产生影响。因此，先手必胜。

  2. 当 1 号点所在连通块与 n 号点所在连通块奇偶性相同时，不管是奇是偶，加起来都是偶数，因此剩下的块之和也为偶数。这就意味着剩下的块中会有偶数个个数为奇数有点绕的块。

    若当前 1 号块的奇偶性已经和先手需要的奇偶性相同，那么先手就可以每次把余下的奇数块两两连接配成偶数块，如果后手想用奇数块搞事情把 1 号或 n 号块奇偶性打乱，那先手就跟一手将其变回来，跟不了了也没关系，还有另一个块供先手使用，因此先手必胜。

    若不相同，那么后手采取此策略即可反制先手，让他失败。因此后手必胜。

至此，题目就做完了。代码好写，但是思维难度挺高，可以再仔细琢磨琢磨。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,a[200005],b[200005];
int n,m,fa[200005];
ll sz[200005];
bool f;
int root(int x){
    if(x==fa[x])return x;
    return fa[x]=root(fa[x]);
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;//并查集求连通块大小
    for(int i=1;i<=m;++i){
        cin>>a[i]>>b[i];
        int ra=root(a[i]),rb=root(b[i]);
        if(ra!=rb){
            sz[ra]+=sz[rb];
            fa[rb]=ra;
        }
    }
    int rn=root(n),r1=root(1);
    if(rn==r1){//如果开局就不合法那么后手赢
        cout<<"Second"<<endl;
        return;
    }
    ll now=(ll)n*(ll)(n-1)/2-m;//式子的前一坨
    if(n&1){//奇数只与now的奇偶有关
        if(now&1)cout<<"First"<<endl;
        else cout<<"Second"<<endl;
    }
    else{
        if(now&1){
            if(sz[r1]%2!=sz[rn]%2)cout<<"First"<<endl;//1，n两个连通块奇偶性不一样先手必胜
            else{
                if(sz[r1]&1)cout<<"Second"<<endl;//看先手需要的奇偶性
                else cout<<"First"<<endl;
            }
        }
        else{
            if(sz[r1]%2!=sz[rn]%2)cout<<"First"<<endl;
            else{
                if(sz[r1]&1)cout<<"First"<<endl;
                else cout<<"Second"<<endl;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)solve();
    return 0;
}