NOI2014随机数生成器
Description
.jpg)
Input
第1行包含5个整数，依次为 x_0,a,b,c,d ，描述小H采用的随机数生成算法所需的随机种子。第2行包含三个整数 N,M,Q ，表示小H希望生成一个1到 N×M 的排列来填入她 N 行 M 列的棋盘，并且小H在初始的 N×M 次交换操作后，又进行了 Q 次额外的交换操作。接下来 Q 行，第 i 行包含两个整数 u_i,v_i，表示第 i 次额外交换操作将交换 T_(u_i )和 T_(v_i ) 的值。
Output
输出一行，包含 N+M-1 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。
Sample Input
1 3 5 1 71
3 4 3
1 7
9 9
4 9
3 4 3
1 7
9 9
4 9
Sample Output
1 2 6 8 9 12
HINT
.jpg)
本题的空间限制是 256 MB，请务必保证提交的代码运行时所使用的总内存空间不超过此限制。
一个32位整数（例如C/C++中的int和Pascal中的Longint）为4字节，因而如果在程序中声明一个长度为 1024×1024 的32位整型变量的数组，将会占用 4 MB 的内存空间。
2≤N,M≤5000
0≤Q≤50000
0≤a≤300
0≤b,c≤108
0≤x0<d≤108
1≤ui,vi≤N×M
题解
这道题比较逗T T
首先整个棋盘可以在nm的时间内求出，但是注意不要疯狂取模不然会T
接着会发现一个比较逗比的性质，就是从1开始取到n*m，能取就取共取n+m-1个是最优的
那么只要这样模拟一下即可
蛋疼的地方在于2500万的数组只能开俩，要循环利用T T
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,nm,q,top; ll a,b,c,d; int x[25000005],t[25000005],up[5005],down[5005],ans[10005]; void add(int a,int b) { for(int i=1;i<=n;i++) if(i<a)up[i]=min(b,up[i]); else if(i>a)down[i]=max(b,down[i]); } int main() { memset(up,127/3,sizeof(up)); x[0]=read();a=read();b=read();c=read();d=read(); n=read();m=read();q=read();nm=n*m; for(int i=1;i<=nm;i++) x[i]=(x[i-1]*(a*x[i-1]+b)+c)%d,t[i]=i; for(int i=1;i<=nm;i++) swap(t[i],t[(x[i]%i)+1]); for(int i=1;i<=q;i++) { int x=read(),y=read(); swap(t[x],t[y]); } for(int i=1;i<=nm;i++)x[t[i]]=i; int a,b; for(int i=1;i<=nm;i++) { if(x[i]%m)a=x[i]/m+1; else a=x[i]/m; b=x[i]%m;if(!b)b+=m; if(b<=up[a]&&b>=down[a]) { add(a,b); ans[++top]=i; if(top==n+m-1)break; } } for(int i=1;i<=top;i++) { printf("%d",ans[i]); if(i!=top)printf(" "); } return 0; } |
计数器 9854477
OI 课件=>
OI 课件=>
卡内存简直恶心……
其实这样没多大意义。。