题解：P3207 [HNOI2010] 物品调度

· · 题解

P3207 [HNOI2010] 物品调度

题意

题面有点令人犯恶心，先理清楚：

首先有个需要你生成的数组 c，生成所需变量是用题目给你的：p、q 和 m。

生成规则是：c_0=0，c_{i+1}=(c_i \times q + p) mod m。

每个盒子还有一个最终位置为pos_i，pos_i=(c_i+d \times x_i+y_i) mod n。注意，这个 x_i 和 y_i 你是不知道的，要你自己生成。满足首先 y 的字典序要最小，其次是 x 的字典序也要小。

每次移动可以将某一个盒子移到空位上，问把所有的盒子移动到最终位置所需的最少步数。

解法

其实比较容易可以发现，增加 x 会使得整个序列在操作的时候变成一个环，环与环之间的关系又要由 y 来决定。此时就可以使用并查集进行优化，把使用了的位置连向空位。

求答案的时候就需要判断一下这个置换环内有没有空格，如果有空格就是环内元素个数减 1，否则加 1。什么意思呢？如下图：

注意的点

有一些小细节可以根据代码理解。

code

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
bool vis[N];
int T,n,s,p,q,m,d,ans,a[N],c[N],fa[N],pos[N];
int find(int x){return fa[x]==x?x:(fa[x]=find(fa[x]));}
signed main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld%lld%lld%lld%lld",&n,&s,&p,&q,&m,&d);
        for(int i=0;i<n;i++) a[i]=0,fa[i]=i,vis[i]=0;
        vis[pos[0]=s]=1,ans=c[0]=0,fa[s]=(s+d)%n;
        for(int i=1;i<n;i++) c[i]=(c[i-1]*p+q)%m;
        for(int i=1;i<n;i++){
            int y=0;
            while(vis[find((y+c[i])%n)]) y++;
            pos[i]=find((y+c[i])%n);
            vis[pos[i]]=1,fa[pos[i]]=find((pos[i]+d)%n);
        }
        for(int i=0;i<n;i++) if(!a[i]&&pos[i]!=i){
            bool pd=0;
            int p=i,cnt=0;
            while(!a[p]){
                if(!p) pd=1;
                a[p]=1,p=pos[p],cnt++;
            }
            ans+=cnt+(pd?-1:1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}