bzoj1998[Hnoi2010] Fsk物品调度

本文主要是介绍bzoj1998[Hnoi2010] Fsk物品调度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj1998
题目大意：
有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最小的。这样你得到了所有盒子的最终位置，现在你每次可以把某个盒子移动到空位上，移动后原盒子所在的位置成为空位。请问把所有的盒子移动到目的位置所需的最少步数。

题解：
这算构造?+置换
啊pos搞的我一脸懵比啊。
先讲我会的置换~~(有什么用没学置换的都会)~~
假设pos求好了，就可以分成很多个互不相交的循环。对于一个长度大于1为cnt的循环，若含空格，那么使其达成目标的步数就是cnt-1；若不含，就要把空格换过来，达成目标后再换回去，即需要cnt+1步。

然后就是pos怎么构造了。大重点，不会这个就等于不会这题QAQ
观察posi=(ci+yi+d*xi) mod n这个式子，可以发现，若yi不变的话，xi的改变就相当于不断+d+d，在mod n下显然会成环。那么就相当于把n化成很多个环(一个yi就一个环)。
因为题目要在yi最小的条件下要xi最少，所以可以从0开始**枚举**yi。看看yi这个环里还有没有位置空着，有的话就找个最小的x来让i填。没有的话yi++，即跳到下个环里，重复以上步骤。
并查集找的就是环里还能填的。若最终找出来的也被找过了(即不是空的)就说明这个环被填完了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define maxn 100010bool vis[maxn],pd[maxn];
int fa[maxn],pos[maxn];LL c[maxn];
int ffind(int x){return (x==fa[x])?x:fa[x]=ffind(fa[x]);}
void merge(int x,int y)
{int fx=ffind(x),fy=ffind(y);fa[fx]=fy;
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int T,n,s,d,i,ans,cnt;LL q,p,mod;scanf("%d",&T);while (T--){scanf("%d%d%lld%lld%lld%d",&n,&s,&q,&p,&mod,&d);d%=n;c[0]=0;ans=0;for (i=0;i<n;i++){if (i) c[i]=(c[i-1]*q+p)%mod;fa[i]=i,vis[i]=0;pd[i]=0;}pos[0]=s;pd[s]=1;fa[s]=(s+d)%n;for (i=1;i<n;i++){int y=0,t=ffind((c[i]+y)%n);while (pd[t]){y++;t=ffind((c[i]+y)%n);}pos[i]=t;pd[t]=true;merge(t,(t+d)%n);}for (i=0;i<n;i++) if (!vis[i]){cnt=0;int x=i;bool zero=false;while (!vis[x]){cnt++;if (x==0) zero=true;vis[x]=true;x=pos[x];}if (cnt<=1) continue;if (zero) ans+=cnt-1;else ans+=cnt+1;}// for (i=1;i<n;i++) printf("%d ",pos[i]);printf("%d\n",ans);}return 0;
}