BZOJ3671: [Noi2014]隨機數生成器(貪心)

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

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;
}