【BZOJ3671】【NOI2014】随机数据生成器（贪心）

时间：2022-09-29 09:25:30

【BZOJ3671】【NOI2014】随机数据生成器（贪心）

题面

BZOJ

题解

前面的模拟

真的就是语文阅读理解题目

理解清楚题目意思

然后就会发现要求的就是一个贪心

从小往大枚举，检查当前数能不能选

如果能选

就会限制其他行的左右能够到达的范围

暴力修改一下

然后就很愉快的\(AC\)了

这题别的不卡

卡空间，卡格式

我也是醉了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

inline int read()

{

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

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

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

	return x*t;

}

int X[5000*5000+10],T[5000*5000+10];

int l[5001],r[5001];

int A,B,C,D,N,M,Q;

int main()

{

	X[0]=read();A=read();B=read();C=read();D=read();

	N=read();M=read();Q=read();

	int tt=N*M;

	for(int i=1;i<=tt;++i)X[i]=(1ll*A*X[i-1]%D*X[i-1]%D+1ll*B*X[i-1]%D+C)%D;

	for(int i=1;i<=tt;++i)T[i]=i;

	for(int i=1;i<=tt;++i)swap(T[i],T[X[i]%i+1]);

	for(int i=1;i<=Q;++i)swap(T[read()],T[read()]);

	for(int i=1;i<=tt;++i)X[T[i]]=i;

	for(int i=1;i<=N;++i)l[i]=1,r[i]=M;

	int tot;

	for(int i=1,j,x,y;i<=tt;++i)

	{

		x=(X[i]+M-1)/M;y=X[i]%M;if(!y)y+=M;

		if(l[x]<=y&&y<=r[x])

		{

			if(i!=1)putchar(' ');

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

			if(tot==N+M-1)break;

			for(j=1;j<x;++j)r[j]=min(r[j],y);

			for(j=x+1;j<=N;++j)l[j]=max(l[j],y);

		}

	}

	return 0;

}

相关文章