HNOI 2010 物品调度并查集置换

题意：

　　题意有点细，暂不概括。请仔细审题。

分析：

　　我们先要把c生成出来。

　　记得颜神讲这道题，首先表明，这道题有两个问题需要处理。

　　第一个是要先定位，第二个是要求最小移动步数。

　　定位时对于每一个物品i，要在不与之前物品冲突的基础上保证y最小，然后x最小。

　　可以想到，如果没有c，当y一定时，枚举x就相当于在一个环上不断向后移动d个位置，可以想到，当枚举到一定程度时，会回到原来的位置。

　　这样呢，为了不冲突，我们就只能利用调整y来摆脱窘境。

　　所以一个思路就出来了，我们从小到大枚举y，对于每个y，我们把满足(ci+d*xi+yi) mod n的位置都不重复地占满，此时就要继续让y变大再寻找空位了。

　　序列c存在的意义是什么？？？我想仅仅是为了使这一步没有数学规律吧……

　　这样呢，我们就确定了一个终序列，此时就需要拿出置换相关的知识，来求最小步数了。

　　因为我们只有一个空位可起到容器的作用，两个实际的物品也不能直接交换，所以容易发现，一个置换要想完成，就必须要完成若干个类似环的操作（相当于空位在环上走）。但是，如果环上没有空位怎么办？？

　　就要分类讨论。

　　首先，如果我们找到的一个环上有空位，那么这个环产生的代价最小是环长-1（因为有个空位）

　　但是如果环上没有空位，那么产生的代价是环长+1（因为要把空位先换过来，产生1的代价，最终要把空位归位或者哪来的环会哪去，又产生1的代价）

　　致此，这道题就差不多做完了。

代码：

 #include<bits/stdc++.h>

 #define ll long long

 using namespace std;

 const int N=;

 bool v[N];ll c[N];int s,d;

 int fa[N],pos[N],t,n,m,p,q;

 int get(int x){

     return fa[x]==x?x:fa[x]=get(fa[x]);

 } int main(){

     scanf("%d",&t);

     while(t){ t--;

         scanf("%d%d%d%d%d%d",&n,&s,&q,&p,&m,&d);

         for(int i=;i<n;i++) fa[i]=i,v[i]=;

         pos[]=s;v[s]=;fa[s]=(s+d)%n;

         for(int i=;i<n;i++) c[i]=(c[i-]*q+p)%m;

         for(int i=;i<n;i++){

             int y=;

             while(v[get((y+c[i])%n)]) y++;

             pos[i]=get((y+c[i])%n);

             v[pos[i]]=;

             fa[pos[i]]=get((pos[i]+d)%n);

         } memset(v,,sizeof(v));int ans=;

         for(int i=;i<n;i++){

             if(v[i]||pos[i]==i) continue;

             int cur=i,l=;bool bs=;

             while(!v[cur]){

                 if(!cur) bs=;l++;

                 v[cur]=;cur=pos[cur];

             } if(bs) ans+=(l-);

             else ans+=(l+);

         } printf("%d\n",ans);

     } return ;

 }

置换

巴特西

HNOI 2010 物品调度并查集置换

题意：

分析：

最新文章

热门文章

巴特西

HNOI 2010 物品调度 并查集 置换

题意：

分析：

最新文章

热门文章

HNOI 2010 物品调度并查集置换