「NOI 2014」随机数生成器 - 贪心

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 \(\texttt{random}\) 和 C/C++ 中的 \(\texttt{rand}\)）来获得随机性。事实上，随机数生成函数也不是真正的「随机」，其一般都是按某个算法计算得来的。

比如，下面这个二次多项式递推算法就是一个常用算法：

算法选定非负整数 \(x_0,a,b,c,d\)，并采用如下公式递推进行计算。 \[\forall i \geq 1,\ x_i=(ax_{i-1}^2+bx_{i-1}+c)\bmod d\] 这样可以得到一个任意长度的非负整数 数列 \(\{x_i\}_{i \geq 1}\)。一般说来，我们认为这个 数列 是随机的。

利用随机序列 \(\{x_i\}_{i \geq 1}\)，我们还可以采用如下算法产生一个从 \(1\) 到 \(K\) 的 随机排列 \(\{T_i\}^K_{i \geq 1}\)：

  1. 初始设 \(T\) 为 \(1 \sim K\) 的递增序列；
  2. 对 \(T\) 进行 \(K\) 次交换，第 \(i\) 次交换，交换 \(T_i\) 和 \(T_{(x_i \bmod i)+1}\) 的值。

此外，小 H 在这 \(K\) 次交换的基础上，又 额外 进行了 \(Q\) 次交换工作，对于第 \(i\) 次交换，小 H 会选定两个额外下标 \(u_i\) 和 \(v_i\)，并交换 \(T_{u_i}\) 和 \(T_{v_i}\) 的值。

为了检验这个随机生成算法的实用性，小 H 设计了如下问题：

小 H 有一个 \(N\) 行 \(M\) 列的棋盘，她首先按照上述过程，通过 \(N\times M+Q\) 次交换操作，生成一个 \(1 \sim N \times M\) 的随机排列 \(\{T_i\}^{N \times M}_{i \geq 1}\)，然后将这 \(N \times M\) 个数逐行逐列依次填入这个棋盘：也就是第 \(i\) 行第 \(j\) 列的格子上所填入的数应为 \(T_{(i-1)M+j}\)。

接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 \(N\) 行第 \(M\) 列的格子。

小 H 把所经过格子上的数字都记录了下来，并 从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 \(N+M-1\) 的升序序列，我们称之为 路径序列。

小 H 想知道，她可能得到的 字典序最小 的 路径序列 应该是怎样的呢？

解题思路

本题诈骗，实际上可直接模拟出 \(T\) 序列，为使字典序最小，我们可以从 \(1\) 到 \(n + m - 1\) 的点权顺序遍历点，看目前遍历到的点是否可以加入到路径中。通过分析题目，我们可以很容易地得出对于每个被选用的点 \((x, y)\)，则坐标位于 \((x' < x, y' > y)\) 与 \((x' > x, y' < y)\) 的点无法被选。于是我们可以记录每一行可选的坐标区间，然后每次更新答案的同时更新坐标区间即可。由于答案只有 \(n\) 个数，时间复杂度为 \(O(n^2)\)。

本题略卡空间，每个点的坐标直接在线计算即可卡过。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <iostream>
#include <vector>

const int MAXN = 5000;

int main() {
    long long x0, a, b, c, d;
    int n, m, q;

    scanf("%lld %lld %lld %lld %lld", &x0, &a, &b, &c, &d);
    scanf("%d %d %d", &n, &m, &q);

    std::vector<int> t(n * m + 1);
    long long x = x0;
    for (int i = 1; i <= n * m; i++) {
        t[i] = i;
        x = (a * x % d * x % d + b * x % d + c) % d;
        std::swap(t[i], t[x % i + 1]);
    }

    while (q--) {
        int u, v;
        scanf("%d %d", &u, &v);
        std::swap(t[u], t[v]);
    }

    std::vector<int> pos(n * m + 1);
    for (int i = 1; i <= n * m; i++) pos[t[i]] = i;

    auto getX = [m](int a) -> int { return (a - 1) / m + 1; };
    auto getY = [m](int a) -> int { return a % m ? a % m : m; };

    std::vector<int> l(n + 1, 1), r(n + 1, m);
    for (int i = 1; i <= n * m; i++) {
        if (getY(pos[i]) >= l[getX(pos[i])] && getY(pos[i]) <= r[getX(pos[i])]) {
            printf("%d ", i);
            for (int j = 1; j < getX(pos[i]); j++) r[j] = std::min(r[j], getY(pos[i]));
            for (int j = getX(pos[i]) + 1; j <= n; j++) l[j] = std::max(l[j], getY(pos[i]));
        }
    }
    putchar('\n');

    return 0;
}