「BZOJ1998」[HNOI2010] Fsk物品调度

2015年1月31日4,5940

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=””>

Output

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

Sample Input

1
8 3 5 2 7 4

Sample Output

HINT

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

题解

http://blog.163.com/benz_/blog/static/186842030201142352718885/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define mod 30031
#define inf 1000000000
#define rad 100000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T;
int n,s,q,p,m,d,ans;
int fa[100005],a[100005],cir[100005];
ll c[100005];
bool over[100005],vis[100005];
int find(int x)
{
	if(!over[cir[x]])return x==fa[x]?x:fa[x]=find(fa[x]);
	return find(fa[x]=(x+1)%n);
}
void solve()
{
	d%=n;
	ll tmp=0;
	for(int i=1;i<n;i++)
	{
		tmp=(tmp*q+p)%m;
		c[i]=tmp%n;
	}
	for(int i=0;i<n;i++)fa[i]=i,cir[i]=-1;
	for(int i=0;i<n;i++)
		for(int j=i;cir[j]==-1;j=(j+d)%n)
			cir[j]=i;
	if(!d)over[s]=1;
	else fa[s]=(s+d)%n;
	for(int i=1;i<n;i++)
	{
		int pos=find(c[i]),f=find((pos+d)%n);
		a[pos]=i;
		if(pos==f)over[cir[pos]]=1;
		else fa[pos]=f;
	}
	a[s]=0;
    for(int i=0;i<n;i++)
		if(!vis[i])
		{
			int L=0,mark=0;
			for(int k=i;!vis[k];k=a[k])
			{
				L++;
				vis[k]=1;
				if(k==0)mark=1;
			}
			if(L>1)
			{
				if(mark)ans+=L-1;
				else ans+=L+1;
			}
	}
}
int main()
{
	T=read();
	while(T--)
	{
		ans=0;
		memset(over,0,sizeof(over));
		memset(vis,0,sizeof(vis));
		n=read();s=read();q=read();p=read();m=read();d=read();
		solve();
		printf("%d\n",ans);
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define mod 30031

#define inf 1000000000

#define rad 100000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T;

int n,s,q,p,m,d,ans;

int fa[100005],a[100005],cir[100005];

ll c[100005];

bool over[100005],vis[100005];

int find(int x)

{

if(!over[cir[x]])return x==fa[x]?x:fa[x]=find(fa[x]);

return find(fa[x]=(x+1)%n);

}

void solve()

{

d%=n;

ll tmp=0;

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

{

tmp=(tmp*q+p)%m;

c[i]=tmp%n;

}

for(int i=0;i<n;i++)fa[i]=i,cir[i]=-1;

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

for(int j=i;cir[j]==-1;j=(j+d)%n)

cir[j]=i;

if(!d)over[s]=1;

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

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

{

int pos=find(c[i]),f=find((pos+d)%n);

a[pos]=i;

if(pos==f)over[cir[pos]]=1;

else fa[pos]=f;

}

a[s]=0;

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

if(!vis[i])

{

int L=0,mark=0;

for(int k=i;!vis[k];k=a[k])

{

L++;

vis[k]=1;

if(k==0)mark=1;

}

if(L>1)

{

if(mark)ans+=L-1;

else ans+=L+1;

}

int main()

{

T=read();

while(T--)

{

ans=0;

memset(over,0,sizeof(over));

memset(vis,0,sizeof(vis));

n=read();s=read();q=read();p=read();m=read();d=read();

solve();

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

}

return 0;

}

« 「BZOJ1370」[Baltic2003] Gang团伙「codechef」March Challenge 2015 »

hzwer.com _ Home | http://hzwer.com

「BZOJ1998」[HNOI2010] Fsk物品调度

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论