[CF1646F] Playing Around the Table 的题解

题目大意

有 \(n\) 种牌，一种 \(n\) 张，一共 \(n\) 个玩家，一人 \(n\) 个。每个人一次将一张牌对给下家，求构造方案使可以在 \(n\cdot (n-1)\) 次操作之内使第 \(i\) 个人拥有 \(n\) 张 \(i\)。

数据范围满足，\(1\le n\le 100\)。

思路

因为直接构造出题目要求的情况会出现如果一个人提前完成了牌的收集，那么在接下来的操作中他的牌会被打乱，并不足够优秀。

考虑先构造出每一个人都拥有 \(1\) 到 \(n\) 号牌的方案，在使用 \(\dfrac{n\cdot(n-1)}{2}\) 的交换次数交换为题目要求的方案。

现在问题转化为了怎么构造出每一个人都拥有 \(1\) 到 \(n\) 号牌的方案。

如果没有构造出上述的情况，那么一定有一个人拥有重复的牌，将这个牌传给下家。如果这个人手中的牌都没有重复，那么可以它可以将上家传给他的牌传给下家，这样就可以保证手中现在的情况不被破坏。

只考虑值为 \(1\) 的牌需要被往前送多少次。把牌看作 \(1\) ，人看作 \(−1\) ，那么必然存在一个循环移位使得前缀和非负。于是不难发现，在这个循环移位下，每张牌只会往前走，不会从第 \(n\) 个人回到第 \(1\) 个人。

所以这个操作是可以在 \(\dfrac{n\cdot(n-1)}{2}\) 次操作之内完成的。

#include<iostream>
using namespace std;
const int N=105;
int n,a[N][N],ans[N];
int ck(){
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]>1){
        // cout<<"i="<<i<<" j="<<j<<'\n';
        return i;
    }
    return 0;
}
signed main(){
    cin>>n;
    for(int i=1,x;i<=n;i++) for(int j=1;j<=n;j++) cin>>x,a[i][x]++;
    cout<<(n-1)*n<<'\n';
    for(int num=1;num<=(n-1)*n/2;num++){
        int p=ck(),f=1;
        // cout<<"p="<<p<<'\n';
        if(!p){
            for(int i=1;i<=n;i++) cout<<1<<' ';
            cout<<'\n';continue;
        }
        // for(int i=1;i<=n;i++){
        //     for(int j=1;j<=n;j++){
        //         cerr<<a[i][j]<<' ';
        //     }
        //     cerr<<'\n';
        // }
        // cout<<p<<'\n';
        for(int i=p;i!=p||f;i=i%n+1,f=0){
            for(int j=1;j<=n;j++){
                if(a[i][j]>1){
                    a[i][j]--;
                    a[i%n+1][j]++;
                    ans[i]=j;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<' ';
        }
        cout<<'\n';
    }
    
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            for(int k=1;k<=n;k++){
                cout<<(i+k-j-1)%n+1<<' ';
            }
            cout<<'\n';
        }
    }
    return 0;
}