首页 > 代码库 > 【BZOJ3671】[Noi2014]随机数生成器 暴力
【BZOJ3671】[Noi2014]随机数生成器 暴力
【BZOJ3535】[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≤1081≤ui,vi≤N×M
题解：矩阵生成的方法。。。它让你怎么做你就怎么做就行了，不过有点卡空间，以后不再用到的数组可以废物利用一下~
然后输出路径。。。直接每次贪心看一下最小的那个数能不能选，如果能，就暴力将它的左下和右上方（严格）的所有格子标记为不能选，注意不要重复打标记。
#include <cstdio>#include <cstring>#include <iostream>#define P(A,B) ((A-1)*m+B)#define X(A) ((A-1)/m+1)#define Y(A) ((A-1)%m+1)using namespace std;typedef long long ll;int n,m,q,A,B,C,D;ll x0;int p[25000010],v[25000010];int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) {if(gc==‘-‘)f=-f; gc=getchar();} while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret*f;}int main(){ x0=rd(),A=rd(),B=rd(),C=rd(),D=rd(),n=rd(),m=rd(),q=rd(); int i,j,k,a,b,flag=0; for(i=1;i<=n*m;i++) v[i]=i; for(i=1;i<=n*m;i++) x0=(A*x0*x0+B*x0+C)%D,swap(v[i],v[x0%i+1]); for(i=1;i<=q;i++) a=rd(),b=rd(),swap(v[a],v[b]); for(i=1;i<=n*m;i++) p[v[i]]=i; memset(v,0,sizeof(v)); for(i=1;i<=n*m;i++) { if(v[p[i]]) continue; a=X(p[i]),b=Y(p[i]); if(flag) printf(" "); flag=1; printf("%d",i); for(j=a+1;j<=n;j++) { if(v[P(j,b-1)]) break; for(k=b-1;k;v[P(j,k)]=1,k--) if(v[P(j,k)]) break; } for(j=a-1;j;j--) { if(v[P(j,b+1)]) break; for(k=b+1;k<=m;v[P(j,k)]=1,k++) if(v[P(j,k)]) break; } } return 0;}【BZOJ3671】[Noi2014]随机数生成器 暴力
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。