题解：CF1619F Let's Play the Hat?

· · 题解

STL set + 简单数学计算

本题貌似没什么难点？

本题貌似没什么难点？

根据样例意识到其实对于大桌和小桌玩的次数是需要自己计算出来的，这算是需要解线性方程了吗？考虑 exgcd？

其实不需要，因为大桌和小桌的容纳人数有很明显的关系，显然可以利用取余关系解决，根据题意大桌容纳 \lceil \dfrac{n}{m} \rceil 个人，小桌容纳 \lfloor \dfrac{n}{m} \rfloor 个人，显然大桌容纳人的个数要么和小桌相等，要么比小桌多一。

因为题目数据保证了 n \ge 2m，即满足不难想到 n \bmod m 的结果就是大桌的个数，因为对于余数中的每个 1 都划分成一个大桌。

由于一次游戏中大桌玩的次数和小桌玩的次数是确定的，而且根据题意不难想到只需要保证玩过大桌的人玩过的次数差值不超过 1，很容易想到一个方式就是对于一次游戏中先考虑把在大桌中玩的人的情况全部处理出来，很容易想到一种处理方式就是进行若干轮第 1 \sim n 的玩家循环输出，最后以某个玩家 pos 结尾即可。

#define rep(x,y,z) for(int x=y;x<=z;x++)
int n,m,k;
void solve(){
    cin>>n>>m>>k;
    int idx=1;
    int num=n%m;
    rep(i,1,k){
        set<int> se;
        rep(id,1,n) se.insert(id); 
        rep(j,1,m){
            if(j<=num){ // 大桌
                int cnt=(n+m-1)/m; // 每个大桌能容纳的人数
                cout<<cnt<<" ";
                rep(o,0,cnt-1){
                    int id=(idx+o)%n;
                    if(!id) id=n;
                    cout<<id<<" ";
                    if(se.count(id)) se.erase(id); // 避免在小桌中重复出现
                }
                idx+=cnt;
                idx%=n;
                if(!idx) idx=n;
            }
            else{ // 小桌
                int cnt=n/m; // 每个小桌能容纳的人数
                cout<<cnt<<" ";
                while(cnt--){
                    cout<<*se.begin()<<" ";
                    se.erase(se.begin());
                }
            }
            cout<<endl;
        }
    }
}