6
12
2016
0

【NOI2014】【思路题】随机数生成器

题意:

利用二次多项式递推算法得到一个非负整数随机数列

通过对递增排列进行交换得到一个1~K随机排列

将得到的排列填入N*M的棋盘内,从左上角走到右下角,经过路径上的数字从小到大排序,求可以得到的字典序最小的路径序列。

N,M<=5000,交换次数Q<=50000,时限5s,内存限制256MB

分析:

排列生成直接暴力!我还以为是像SDOI那道随机数生成器一样是数论题呢。

不需要开二维数组,直接对序列进行处理即可。但空间是卡着过去的,可以开short int。

预处理出1~n的位置:二进制存储!二进制前16位储存行,后16位储存列(2^16足够),提取时直接位运算分别得到行列数即可(pv=posvalue,该值的位置)

	F(i,1,n) F(j,1,m) pv[mp[i][j]]=i<<16|j;
	F(i,1,m*n){
		int x=pv[i]>>16;
		int y=pv[i]&65535;
        }

从小到大枚举数字1~n*m,贪心填入(每次都将填入当前位置允许的最小数字)。由于行走方向只可以向右或向下,将当前填入的数字的左下角和右上角标记为无法填入数字,具体实现 将每行合法区间的左右端点修改即可,填数的复杂度是O(n^2)的!

一般区间覆盖的题目会想到线段树,但这道题线段树维护暴力修改操作是O(n^2logn)的。靠大脑吧少年!

代码学习了POPOQQQ大爷的~

int seed,A,B,C,D;
const int N=5000+10;
int n,m,q,T[N*N],l[N],r[N];
int mp[N][N],pv[N*N];
bool flag;
int Rand(){return seed=(A*seed*seed+B*seed+C)%D;}//return时仍赋值
void kill(int x,int y)
{
	F(i,1,x-1) r[i]=min(r[i],y);
	F(i,x+1,n) l[i]=max(l[i],y);
}
Ryan main()
{
	#ifndef ONLINE_JUDGE
//	freopen("random.in","r",stdin); 
	#endif
	scanf("%d%d%d%d%d",&seed,&A,&B,&C,&D);
	scanf("%d%d%d",&n,&m,&q);flag=0;
	F(i,1,n) l[i]=1,r[i]=m;
	F(i,1,m*n) T[i]=i,swap(T[i],T[Rand()%i+1]);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		swap(T[x],T[y]); 
	}
	int k=0;
	F(i,1,n) F(j,1,m) mp[i][j]=T[++k];
	F(i,1,n) F(j,1,m) pv[mp[i][j]]=i<<16|j;
	F(i,1,m*n){
		int x=pv[i]>>16;
		int y=pv[i]&65535;
		if(l[x]<=y&&y<=r[x]){
			if(flag) putchar(' ');
			flag=1;
			printf("%d",i);
			kill(x,y);		
		}
	}
	return 0;	
}

UPD:等等,似乎get到了一种生成随机排列的方法!?

int Rand()
{
	return seed=(A*seed*seed+B*seed+C)%D;
}//return时赋值

for(int i=1;i<=n;i++)
	P[i]=i,swap(P[i],P[Rand()%i+1]);
Category: 树套树 | Tags: 位运算 枚举 区间问题 | Read Count: 281

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com