您的位置: 首页  >  IT文章  >  题解 洛谷 P3207 【[HNOI2010]物品调度】

题解 洛谷 P3207 【[HNOI2010]物品调度】

分类: IT文章 • 2022-09-10 00:34:24

考虑题目所给出的式子：(pos_i=(c_i+dx_i+y_i) mod n)，当 (y_i) 一定时，随着 (x_i) 的增大，得到的值会出现循环，即形成环。不难发现对于 (x_i,y_i) 的不同取值，(c_i+y_i) 可以看作对应一个环和该环的起始位置，(x_i) 对应到该环最终到达的位置。

因为要先保证 (y_i) 最小，再保证 (x_i) 最小，暴力的想法就是先枚举 (y_i)，再枚举 (x_i)，即先枚举是哪一个环，再枚举该环上的位置，判断是否该位置已经被占用，若没被占用就让当前的 (i) 占用，若被占用就继续枚举。

发现可以用并查集来优化这两个枚举的过程，当一个环内的位置都被占用后，将其用并查集指向下一个环，当一个位置被占用后，将其用并查集指向下一个位置。这样的话，通过并查集就能快速的找到环和其对应的位置。

确定完 (pos) 后，考虑如何计算最少步数。考虑到 (pos) 为原序列的一个置换，将 (i) 向 (pos_i) 连边后，发现形成的图为若干个环，因此该置换是由若干个轮换组成的。考虑每一个轮换，当一个轮换中包含空位 (0) 时，其对答案的贡献为轮换长度减一，因为除了空位 (0) 以为，每个位置都要进行相应的移动，当一个轮换中不包含空位 (0) 时，其对答案的贡献为轮换长度加一，因为其还需将空位 (0) 移动进来和移动出去。

#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int T,n,s,q,p,m,d,ans,tot;
int bel[maxn],c[maxn],pos[maxn];
bool vis[maxn];
struct node
{
    int fa[maxn];
    int find(int x)
    {
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
}A,B;
void add(int x)
{
    int a=A.find(x),b=A.find((x+d)%n);
    if(a!=b) A.fa[a]=b;
    else B.fa[B.find(bel[x])]=B.find((bel[x]+1)%tot);
}
void clear()
{
    ans=tot=0;
    memset(bel,-1,sizeof(bel));
    memset(vis,0,sizeof(vis));
}
int main()
{
    read(T);
    while(T--)
    {
        clear(),read(n),read(s),read(q),read(p),read(m),read(d);
        for(int i=1;i<n;++i) c[i]=((ll)c[i-1]*q+p)%m;
        for(int i=0;i<n;++i)
        {
            if(bel[i]!=-1) continue;
            int x=i;
            while(bel[x]==-1) bel[x]=tot,x=(x+d)%n;
            tot++;
        }
        for(int i=0;i<n;++i) A.fa[i]=i,c[i]%=n;;
        for(int i=0;i<tot;++i) B.fa[i]=i;
        add(s),pos[0]=s;
        for(int i=1;i<n;++i)
        {
            int p1=B.find(bel[c[i]]),p2=A.find((c[i]+(p1-bel[c[i]]+tot)%tot)%n);
            pos[i]=p2,add(p2);
        }
        for(int i=0;i<n;++i)
        {
            if(vis[i]||i==pos[i]) continue;
            int x=i,len=0;
            while(!vis[x]) vis[x]=true,x=pos[x],len++;
            ans+=i?len+1:len-1;
        }
        printf("%d
",ans);
    }
    return 0;
}

相关推荐