BZOJ3671: [Noi2014]随机数生成器(贪心)
2018-07-09 13:25:22来源:博客园 阅读 ()
Submit: 2098 Solved: 946
[Submit][Status][Discuss]
Description
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
3 4 3
1 7
9 9
4 9
Sample Output
HINT
本题的空间限制是 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×
Source
这题究竟是几个意思???
为了科普随机化算法??(雾)
字典序最小?那不就是贪心走小的就行了么?
顺便维护一下每一个$x$,对应那些$y$是能选的
选了一个数之后它左下和右上的矩阵就都不能选了
#include<cstdio> #include<cstring> #include<algorithm> #include<ctime> #include<cstdlib> #define LL long long using namespace std; const int MAXN = 1e5 + 10, INF = 1e8 + 10, mod = 1e9 + 7, mod2 = 1e9 + 6; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M, Q, tot = 0; LL Xi, X0, a, b, c, d; int A[5001 * 5001], Map[5001][5001], l[MAXN], r[MAXN]; int xx[3] = {0, +1, 0}, yy[3] = {0, 0, +1}; main() { #ifdef WIN32 ///freopen("a.in", "r", stdin); #endif X0 = read(); a = read(), b = read(), c = read(), d = read(); N = read(); M = read(); Q = read(); for(int i = 1; i <= N * M; i++) A[i] = i; for(int i = 1; i <= N * M; i++) swap(A[i], A[(Xi = (a * X0 * X0 + b * X0 + c) % d) % i + 1]), X0 = Xi; //for(int i = 1; i <= N * M; i++) printf("%d\n", A[i]); while(Q--) {int x = read(), y = read(); swap(A[x], A[y]);} for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) Map[i][j] = A[++tot]; for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) A[Map[i][j]] =(i - 1) * M + j; memset(Map, 0, sizeof(Map)); for(int i = 1; i <= N; i++) l[i] = 0, r[i] = M + 1; for(int i = 1; i <= N * M; i++) { int y = A[i] % M, x = A[i] / M + 1; if(y == 0) x--, y = M; if(y <= l[x] || y >= r[x]) continue; printf("%d ", i); for(int j = x - 1; j >= 1; j--) r[j] = min(y + 1, r[j]); for(int j = x + 1; j <= N; j++) l[j] = max(y - 1, l[j]); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++生成随机数 2020-04-18
- C/C++产生随机数 2019-12-25
- C++随机数笔记 2019-10-31
- C++生成随机数 2019-10-08
- 产生随机数与相应的猜拳小游戏 2018-09-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash