uoj6 随机数生成器

发表于 | 更新于

Link

Solution

先计算得到数列 根据字典序最小，肯定要先贪心地取最小的 取了一个数字之后，会增加一个限制条件：路径必须在它的左上方和右下方 所以不停地取合法的，并不停地把条件取交集，直到取满为止

Tips

字典序可以优先考虑贪心(SDOI的最小字典序割)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::swap;
using std::find;
using std::merge;
using std::sort;

const int MAXN=5000+1;
int T[MAXN*MAXN],ref[MAXN*MAXN],Ans[MAXN<<1],lbd[MAXN],rbd[MAXN];
struct Random
{
	ll seed;int a,b,c,d;
	Random(ll seed,int a,int b,int c,int d):seed(seed),a(a),b(b),c(c),d(d){}
	int next() {return seed=(seed*(seed*a+b)+c)%d;}
};
int main()
{
	int x,a,b,c,d,n,m,q,sz;
	get(x),get(a),get(b),get(c),get(d),get(n),get(m),get(q);
	Random random(x,a,b,c,d);
	sz=n*m;
	for(int i=1;i<=sz;++i) T[i]=i;
	for(int i=1;i<=sz;++i) swap(T[i],T[random.next()%i+1]);
	for(int i=1;i<=q;++i) 
	{
		int u,v;get(u),get(v);
		swap(T[u],T[v]);
	}
	for(int i=1;i<=sz;++i) ref[T[i]]=i;
	for(int i=1;i<=n;++i) rbd[i]=m,lbd[i]=1;
	int ac=0,goal=n+m-1;
	for(int i=1;i<=sz && ac!=goal;++i)
	{
		int pos=ref[i],x=(pos-1)/m+1,y=(pos-1)%m+1;
		if(lbd[x]<=y && y<=rbd[x])
		{
			Ans[++ac]=i;
			for(int row=1;row<x;++row) chkmn(rbd[row],y);
			for(int row=x+1;row<=n;++row) chkmx(lbd[row],y);
		}
	}
	for(int i=1;i<=ac;++i) put(Ans[i]),putchar(i==ac?'\n':' ');
	return 0;
}