[NOI2014&UOJ#6]随机数生成器

这道题不要用C++11,否则luogu上T好几个点 题面见题目传送门 首先,因为N,M5000N,M \leq 5000,所以O(nm) O(nm) 的求TiT_i 的纯模拟算法时限完全没有问题。 接着就是求路径序列了:千万注意要好好读题字典序最小” “从小到大排序”说明什么?要贪心做! 那么我们如何贪心呢? 直观地想到:从小到大考虑能不能走到它。 但是直接判断的话复杂度可是会超时的啊! 假设i在第XiX_i行,YiY_i列。 那么显然: 当i和j都可以走,当Xi<XjX_i < X_jYiYjY_i \leq Y_j,利用这个性质,我们可以简化判断。 假设i选了,则对于所有j,当Xj<XiX_j < X_i,则YjYiY_j \geq Y_i ,反之同理。于是写出代码:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
using namespace std;
int read(){
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9'){
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x){
if(x<0){
putchar('-');
write(-x);
}
else{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int t[25050000],ft[25050000],lj[5050],rj[5050],n,m,q;
void myswap(int &a,int &b){
int t=a;a=b;b=t;
}
int main(){
long long x=read(),a=read(),b=read(),c=read(),d=read();
n=read(),m=read(),q=read();
int nm=n*m;
up(i,1,nm){
x=(x*x*a+x*b+c)%d;
t[i]=i;
myswap(t[i],t[(int)x%i+1]);
}
up(i,1,q){
myswap(t[read()],t[read()]);
}
up(i,1,nm){
ft[t[i]]=i;
}
up(i,1,n)lj[i]=1,rj[i]=m;
int tt=n+m-1,h,l;
up(i,1,nm){
h=(ft[i]-1)/m+1;l=(ft[i]-1)%m+1;
if(lj[h]<=l&&rj[h]>=l){//可以选
printf("%d%c",i,--tt?' ':'\n');
if(!tt)return 0;
int k=h-1;
while(k){
rj[k]=rj[k]>l?l:rj[k];//根据性质
--k;
}
k=h+1;
while(k<=n){
lj[k]=lj[k]<l?l:lj[k];//根据性质
++k;
}

}
}
return 0;
}
文章目录
|

博客使用Disqus作为评论系统