Codeforces 1404 D. Game of Pairs

Codeforces 1404 D.Game of Pairs

给定\(2n\)个数\(1,2,...,2n\)，A 和 B 将进行交互，规则如下：

A 需要将元素分成 n 组 \(\mathbf{pair}\)（二元组）

B 从每组 \(\mathbf{pair}\)中选择一个元素，如果权值和是 \(2n\) 的倍数，那么 B 胜，否则 A 胜。

你需要选择 A/B 中的一者扮演角色，并取得胜利。

\(n\le 5\times 10^5\).

老子懒得讲了，你们TMD对着代码自己发愣去吧。

由于可以自选角色，所以我们分别考虑两个角色的必胜情况。

考虑A，我们首先发现如下性质：

由于\(\sum\limits_{i=1}^n=\frac{n\times(n-1)}{2}\)，所以当\(n\)是偶数时，\(\sum_{i=1}^n\)一定不是\(n\)的倍数。

于是针对n为偶数的情况我们可以很容易地构造出无解的方案：将\(i\)和\(i+n(i\in[1,n])\)放进一组，那么无论B怎么选，最后的总和一定是形如\(\frac{n\times(n-1)}{2}+kn\)的某个数，这个式子的后一项一定是n的倍数，而前一项一定不是n的倍数，所以A必胜。

那么我们继续考虑n为奇数的情况。

然而遗憾的是，这种情况下，B是存在必胜策略的...

考虑B，我们重新审视A中发现的性质：

由于\(\sum\limits_{i=1}^{n}=\frac{n\times(n-1)}{2}\)，所以当n是奇数是，\(\sum_{i=1}^{n}\)一定是n的倍数。

然后如何取这个方法实在是抽象，难以描述，所以

非常抱歉，这篇文章从这里开始又咕了。

code:

#include<bits/stdc++.h>

using namespace std;

const int maxn=500005;

int n,fa[maxn<<1],siz[maxn<<1];

int tp[maxn<<1],xorv[maxn<<1],used[maxn<<1];

int Q[maxn],topc;

bool vis[maxn<<1];

inline int read(){

    int res=0,f_f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') f_f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+(ch-'0'),ch=getchar();

    return res*f_f;

}

inline int get_fa(int x){

    return x==fa[x]?x:fa[x]=get_fa(fa[x]);

}

inline void merge_fa(int x,int y){

    siz[get_fa(x)]+=siz[get_fa(y)];

    fa[get_fa(y)]=get_fa(x);

}

inline void dfs(int u){

    vis[u]=true;

    int v=xorv[tp[u]]^u;

    v=(v>n)?v-n:v+n;

    if(vis[v]) return;

    merge_fa(u,v),dfs(v);

}

int main(){

    n=read();

    if(n%2==0){

        printf("First\n");

        cout.flush();

        for (int i=1;i<=(n<<1);i++){

            if(i^(n<<1)) printf("%d ",(i-1)%n+1);

            else printf("%d\n",(i-1)%n+1);

            cout.flush();

        }

    }

    else{

        printf("Second\n");

        cout.flush();

        for (int i=1;i<=(n<<1);i++) tp[i]=read(),xorv[tp[i]]^=i;

        for (int i=1;i<=(n<<1);i++) fa[i]=i;

        for (int i=n+1;i<=(n<<1);i++) siz[i]=1;

        for (int i=1;i<=(n<<1);i++){

            if(vis[i]) continue;

            dfs(i);

        }

        int ans=(n+1)/2&1;

        for (int i=1;i<=(n<<1);i++){

            if(i^get_fa(i)) continue;

            int v=get_fa(xorv[tp[i]]^i);

            if(v>i) continue;

            used[i]=1,ans^=(siz[i]&1);

        }

        if(ans){

            for (int i=1;i<=(n<<1);i++){

                if(!used[i]) continue;

                int v=get_fa(xorv[tp[i]]^i);

                if((siz[v]^siz[i])&1){

                    used[i]=0,used[v]=1;

                    break;

                }

            }

        }

        for (int i=1;i<=(n<<1);i++){

            if(used[get_fa(i)]) Q[++topc]=i;

        }

        for (int i=1;i<=topc;i++){

            if(i^topc) printf("%d ",Q[i]);

            else printf("%d\n",Q[i]);

        }

    }

    return 0;

}

巴特西

Codeforces 1404 D. Game of Pairs

Codeforces 1404 D.Game of Pairs

老子懒得讲了，你们TMD对着代码自己发愣去吧。

非常抱歉，这篇文章从这里开始又咕了。

最新文章

热门文章