Time Limit: 50 Sec Memory Limit: 256 MB
Submit: 2098 Solved: 946
第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 ) 的值。
输出一行,包含 N+M-1 个由空格隔开的正整数,表示可以得到的字典序最小的路径序列。
1 3 5 1 71 3 4 3 1 7 9 9 4 9
1 2 6 8 9 12
本题的空间限制是 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×
这题究竟是几个意思???
为了科普随机化算法??(雾)
字典序最小?那不就是贪心走小的就行了么?
顺便维护一下每一个$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;
}