【题解】LOJ 2248 「NOI2014」随机数生成器

Problem

给定一个 $n*m$ 的矩阵,每个格子 $(i,j)$ 均有一个数 $a_{i,j}\in[1,n*m]$

从 $(1,1)$ 出发,每次只能向下走或者向右走,求到 $(n,m)$ 路径上经过的权值从小到大排序后字典序最小的是多少

Thought

首先打乱的过程可以直接模拟,然后这个题和随机数就没有半毛钱关系了

由于是进行完排序后的字典需最小,那么我们可以确定一个优先级:尽量从小到大拿
每次选择当前位置能够拿到的最小的作为目标,这样能够保证前面的都尽量的小

选择某个点 $(i,j)$ 后,在第 $j$ 列及左侧的路径不能高于第 $i$ 行,第 $j$ 列及右侧的路径不能低于第 $i$ 行,每次这样直接扫过即可,时间复杂度 $O(n*2*n)$

Code

略微卡常,建议 LOJ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 5010;
typedef pair <int, int> Pos;
ll x, a, b, c, d;
int n, m, q;

int num[N * N], pos[N * N];
int up[N], dw[N];
int sta[N * 2], top;

int main() {
    x = read(); a = read(); b = read(); c = read(); d = read();
    n = read(); m = read(); q = read();
    for(int i = 1; i <= n * m; ++ i)
        num[i] = i;
    for(int i = 1; i <= n * m; ++ i) {
        x = (a * x % d * x % d + b * x % d + c) % d;
        swap(num[i], num[x % i + 1]);
    }
    for(int i = 1; i <= q; ++ i) {
        int u = read(), v = read();
        swap(num[u], num[v]);
    }
    
    for(int i = 1; i <= n * m; ++ i)
        pos[num[i]] = i;
    for(int i = 1; i <= m; ++ i) {
        up[i] = 1; dw[i] = n;
    }
    sta[++ top] = num[n * m];
    sta[++ top] = num[1];

    for(int i = 1; i <= n * m; ++ i) {
        if(i == num[1] || i == num[n * m]) continue;

        int X = (pos[i] - 1) / m + 1, Y = (pos[i] - 1) % m + 1;
        if(X < up[Y] || X > dw[Y]) continue;

        sta[++ top] = i;
        for(int j = Y + 1; j <= m; ++ j)
            if(up[j] < X) up[j] = X;
        for(int j = 1; j < Y; ++ j)
            if(dw[j] > X) dw[j] = X;
    }
    sort(sta + 1, sta + n + m);
    for(int i = 1; i <= n + m - 1; ++ i)
        printf("%d ", sta[i]);
    return 0;
}
Comments

添加新评论