bzoj 1998: [Hnoi2010]Fsk物品调度 （置换+并查集）

1998: [Hnoi2010]Fsk物品调度

Time Limit: 10 Sec   Memory Limit: 259 MB Submit: 444   Solved: 212 [ Submit][ Status][ Discuss]

Description

现在找工作不容易，Lostmonkey费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有n个位置，从0到n-1依次编号，一开始0号位置空，其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。 规则由5个数描述，q，p，m，d，s，s表示空位的最终位置。首先生成一个序列c，c0=0，ci+1=(ci*q+p) mod m。接下来从第一个盒子开始依次生成每个盒子的最终位置posi，posi=(ci+d*xi+yi) mod n，xi,yi是为了让第i个盒子不与之前的盒子位置相同的由你设定的非负整数，且posi还不能为s。如果有多个xi，yi满足要求，你需要选择yi最小的，当yi相同时选择xi最小的。 这样你得到了所有盒子的最终位置，现在你每次可以把某个盒子移动到空位上，移动后原盒子所在的位置成为空位。请问把所有的盒子移动到目的位置所需的最少步数。

Input

第一行包含一个整数t，表示数据组数。接下来t行，每行6个数，n，s，q，p，m，d意义如上所述。 对于30%的数据n<=100，对于100%的数据t<=20,n<=100000,s<n。其余所有数字均为不超过100000的正整数。 <="" div="" style="font-family: arial, verdana, helvetica, sans-serif;">

Output

对于每组数据输出一个数占一行，表示最少移动步数。

Sample Input

1 8 3 5 2 7 4

Sample Output

6

HINT

说明：第1个到第7个盒子的最终位置依次是：2 5 6 4 1 0 7 计算过程可能超过整型范围。

Source

[ Submit][ Status][ Discuss]  HOME  Back

题解：并查集+置换

这道题的重点应该是pos数组的构造，因为我们要在y最小的情况下再满足x最小，有一种很暴力的方法，就是y从0开始枚举，然后判断在(c[i]+y)%n的意义下有没有可行的x，不断+d的过程实际会形成一个或者多个环，我们其实就是要判断包含这个点的环中是否还有没有用过的元素。每次必然不能一个一个的在环上跳，所以如果一个元素入选，那么我们就用并查集将当前权x与x+d并到一起。

然后剩下的就是置换的锅了，对于这道题来说，如果轮换中只有1个元素，那么直接不用动。如果轮换中包含空位置，那么可以用len-1将其搞成正常的顺序，如果不包含空位置我们首先要把空位置引入，用完了再换回去，需要len+1步操作。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 200003 #define LL long long using namespace std; LL fa[N],c[N],pos[N],T,n,m,p,q,d,s,mark[N],use[N]; LL find(int x) { if (fa[x]==x) return x; fa[x]=find(fa[x]); return fa[x]; } int main() { freopen("a.in","r",stdin); scanf("%d",&T); while (T--) { scanf("%lld%lld%lld%lld%lld%lld",&n,&s,&q,&p,&m,&d); c[0]=0; for (int i=1;i<n;i++) c[i]=(c[i-1]*q+p)%m; //for (int i=1;i<=n;i++) cout<<c[i]<<" "; //cout<<endl; memset(mark,0,sizeof(mark)); mark[s]=1; for (int i=0;i<=n*2;i++) fa[i]=i; fa[s]=(s+d)%n; pos[0]=s; for (int i=1;i<n;i++) { LL y=0; int t=find((c[i]+y)%n); while (mark[t]) { y++; t=find((c[i]+y)%n); } pos[i]=t; mark[t]=1; int r1=find(t); int r2=find((t+d)%n); fa[r1]=r2; } //for (int i=0;i<n;i++) cout<<pos[i]<<" "; //cout<<endl; LL ans=0; memset(use,0,sizeof(use)); for (int i=0;i<n;i++) if (!use[i]) { int j=i; int len=0; bool pd=true; while (!use[j]) { if (j==0) pd=false; len++; use[j]=1; j=pos[j]; } if (len==1) continue; if (!pd) len--; else len++; //cout<<len<<endl; ans=ans+len; } printf("%lld\n",ans); } }