bzoj 3671: [Noi2014]随机数生成器【模拟+贪心】

降智好题

前面随机部分按照题意模拟，然后字典序贪心，也就是记录每个值的位置从1~nm依次看能不能取，能取的话更新行的取值范围（它上面的行一定取的列小于等于这个数取的列，下面行大于等于）

#include<iostream>

#include<cstdio>

using namespace std;

const int N=5005;

int n,m,q,len,p[N*N],id[N*N],l[N],r[N];

long long x,a,b,c,d;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int main()

{

    x=read(),a=read(),b=read(),c=read(),d=read(),n=read(),m=read(),q=read(),len=n*m;

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

		p[i]=i;

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

		x=(a*x%d*x+b*x+c)%d,swap(p[i],p[x%(i+1)]);

    while(q--)

	{

		int x=read(),y=read();

		swap(p[x-1],p[y-1]);

	}

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

		id[p[i]]=i;

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

		l[i]=0,r[i]=n-1;

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

        if(l[id[i]%m]<=id[i]/m&&r[id[i]%m]>=id[i]/m)

        {

            printf("%d ",i+1);

            for(int j=id[i]%m+1;j<m;j++)

				l[j]=max(l[j],id[i]/m);

            for(int j=0;j<id[i]%m;j++)

				r[j]=min(r[j],id[i]/m);

        }

    return 0;

}

巴特西

bzoj 3671: [Noi2014]随机数生成器【模拟+贪心】

最新文章

热门文章