题目传送门(BZOJ)
>原文链接<

题解 :

从头到尾都弥漫着暴力的气息。

我们先暴力的把矩阵推出来,然后从小往大枚举,如果枚举到的数字没有被打上标记,那么就给它左下和右上所有的点都打上标记,表示不能再取。

不需要证明,这样做字典序一定最小。

唯一的坑是开三个5000^2开不下,我们把其中一个循环利用就好。

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 5010;#define P(i, j) ((i-1)*m+j)int x[N*N], a[N][N];bool vis[N][N];long long S, A, B, C, D;int n, m, Q;int getRand() { return S = (A*S*S%D+B*S%D+C)%D;}int main() { cin >> S >> A >> B >> C >> D >> n >> m >> Q; for(int i = 1; i <= n*m; i ++ ) x[i] = i, swap(x[i], x[getRand()%i+1]); for(int i = 1, x1, x2; i <= Q; i ++ ) scanf("%d%d", &x1, &x2), swap(x[x1], x[x2]); for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) a[i][j] = x[P(i, j)]; for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) x[a[i][j]] = P(i, j); for(int i = 1; i <= n*m; i ++ ) { int curx = x[i]/m+1-(x[i]%m == 0), cury = x[i]-(curx-1)*m; if(!vis[curx][cury]) { if(i != 1) putchar(' '); printf("%d", i); for(int j = curx+1; j <= n; j ++ ) for(int k = cury-1; k; k -- ) { if(vis[j][k]) break; vis[j][k] = 1; } for(int j = curx-1; j; j -- ) for(int k = cury+1; k <= m; k ++ ) { if(vis[j][k]) break; vis[j][k] = 1; } } }}