题解：P3207 [HNOI2010] 物品调度

· · 题解

听说 noip 前写题解可以增加 rp 咕咕？

感觉是道并查集维护连通性的好题。题解采用引导式，因为自己弄了很久才明白，希望尽量解释详细，所以比较长。思路大体上和其他题解差不多，但是补充了更多细节。

:::::info[ x 和 y 序列怎么确定？] 首先要明确：x_i 和 y_i 不是让你任意选择的，在序列 c 确定时 x 和 y 序列是唯一的。先考虑 y_i 尽量小，再考虑 x_i 尽量小，有空位就占用。

注意到 c_i 和 y_i 固定时，x_i 每增加 1，最终位置就增加 d 然后再放到取模意义下。设 c_i + y_i = x，则可以抽象为 x 有一条出边 (x + d) \bmod n。每个 x 都有一条出边，一条入边，所以这些边形成若干个环。x_i 增加 1 相当于在环上沿边跳一步。

找空位时先从 (c_i+y_i) \bmod n 所在的环上找，看环上有没有空位，如果没有空位就增加 y_i，如果有空位则在环上找到能使 x_i 的最小的空位。

显然有一种暴力做法是先枚举 y_i，再枚举 x_i。但是这样太慢了。能不能加速呢？

::::info[加速] 枚举太慢了，因为很多已经被占的位置都会被枚举到。为了跳过这些位置，可以使用并查集维护连通性。这里就是维护一个环上的已被占有的连续段，这样可以在枚举 x_i 的时候跳过连续段。总共枚举 x_i 只用了 O(n) 次。

但是枚举 y_i 还是很慢啊？如果环长为 1，时间就被卡飞了。

:::info[再加速] 已满的环的也可以用并查集维护连续段。具体的，维护的连续段内的任意元素所在的环内都满了。称其为环间并查集。之前那个成为环内并查集。

多个点属于一个环没关系，如果是添加到某一个点的时候，这个环满了，我们在环间并查集标记了这个点，但是这个环里其他点也要在环间并查集标记，这是处理的一个细节。我的程序中采用其他点先不标记，等到后面再处理到这个环时，如果满了但还没有标记，就顺手标记了再往下搜。 ::: :::: :::::

到这里，我们确定了 x 序列和 y 序列，从而确定了所有盒子的最终位置 pos。这是第一步，下一步我们要确定怎么移动盒子。

:::warning[一个错误的想法：每次把目标位置在当前空位的盒子移过去] 反例：n=5，s=1，编号 1 到 4 的盒子最终位置为 2,0,4,3，你会发现按这种办法则编号 3 和 4 的盒子无法归位。 :::

:::info[如何移动] 这里有个小 trick，把 0 位置上看做有一个虚盒子（实际不存在），它的目标位置为 s。盒子移到空位转换为和 0 号盒子交换位置。原问题变成了一个置换问题。

现在每个初始位置和目标位置都能一一对应了。现在把初始位置编号向对应的目标位置编号连一条边，就会发现每个编号入度 1，出度 1，形成了若干个环。注意这一步的环和上一步确定 pos_i 时的环没有任何关系。不要弄混了。

对于包含 0 节点的环，每次把目标位置在当前空位的盒子移过去，也就是顺着环移动，移动次数为 (环长-1)。

对于不包含 0 节点的环，因为交换必须借助 0 号箱子，所以先用一次交换把 0 节点换进来，再和上面那种情况一样方法操作即可。最后用一次交换把 0 节点换出去。移动次数为 (环长+1)，比上面那种情况多了头尾两次交换。

当然对于自环需要特判。自环不需要任何交换。 :::

完成了，下面是代码。感觉细节挺多。

:::success[代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
int fa[100010],fac[100010],c[100010],pos[100010],vis[100010];
int n,s,q,p,m,d;
int root(int x){//环内并查集，维护x位置是否被占
    if(fa[x] == x)return x;
    fa[x] = root(fa[x]);
    return fa[x];
}
int rootc(int x){//环间并查集，维护x所在环是否已满
    if(fac[x] == x)return x;
    fac[x] = rootc(fac[x]);
    return fac[x];
}
void init(){
    for(int i = 0; i <= n; i++)fa[i] = fac[i] = c[i] = pos[i] = vis[i] = 0;
}
void solve(){
    scanf("%lld%lld%lld%lld%lld%lld",&n,&s,&q,&p,&m,&d);
    for(int i = 0; i < n; i++){
        if(i == 0)c[i] = 0;
        else c[i] = (c[i - 1] * q + p) % m;
        pos[i] = -1;
    }
    c[0] = s % n;//反正是第一个考虑，都是空位，直接把它记为s，它肯定会占用s位置
    //但是不能在其他i之前赋值，因为会影响后面的c[i]
    for(int i = 0; i <= n + 5; i++)fa[i] = fac[i] = i;
    for(int i = 0; i < n; i++){
        //j = (c[i] + y) % n,k = (c[i] + yi + xi * d) % n
        int j = c[i] % n;//m不一定小于n，即c[i]不一定小于n，记得取模
        while(rootc(j) != j || root(j) == n){//j所在环已经跑完，直接跳过
            if(rootc(j) == j)fac[j] = rootc((j + 1) % n);
            //这里连边是因为如果j所在的环已经满了，
            //但是最后一个被占的点为环上另一点k，
            //那么k在环间并查集标记了而j没有标记，
            //这里需要补标记
            j = rootc(j);
        }
        int k = j;//x_min=0
        while(root(k) != k)k = root(k);//找到j所在环的空位置
        pos[i] = k;
        if(k != root((k + d) % n)){
            fa[k] = root((k + d) % n);
        }else{
            fac[j] = rootc((j + 1) % n),fa[k] = n;
        //再跳一步就从环上连续段的尾调到头了，说明这个环满了
        }
    }
    //注意概念上置换形成的环与处理pos时每次跳d单位的环不同
    int ans = 0;
    for(int i = 1; i < n; i++){
        if(vis[i] || pos[i] == i)continue;//i所在环已经处理或者自环情况就不用再处理了
        int now = i,fl = 0,cnt = 0;
        while(!vis[now]){
            vis[now] = 1,cnt++;
            if(now == s)fl = 1;
            now = pos[now];
        }
        if(fl)ans += cnt - 1;
        else ans += cnt + 1;
    }
    printf("%lld\n",ans);
}
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--){
        init(),solve();
    }
    return 0;
}

:::