UOJ #6.[NOI2014]随机数生成器

序

这个题,难在阅读.

题目大意

跳过!
链接:🔗

解析

首先根据题目得到一个随机数列$\lbrace x_i=(a×x_{i−1}^2+b×x_{i−1}+c)$mod$d\rbrace$其中$i\in{1…n×m}$
搞一个数列$T$,其中$T_i=i$,$i\in{1….n×m}$
对每一项$T_i$,我们$swap(T_i,$$T_{x_imodi+1})$
以上$3$步结束后,得到的就是棋盘要填的数$T_i$

样例一数据生成的棋盘如下:

12	9	1	7
5	11	6	2
4	10	3	8

路线便是$12->9->1->6->2->8$
一个有技巧的贪心来选数.
首先,$map[1][1]$必定选.
如果我们不考虑棋盘顺序,若要序列最小,显然是选最小数的放进去,那么我们便从$1$这个数开始贪心.
那么,这个数我们什么时候才取它呢?
根据题目要求,我们从左上角到右下角,只能向右或者向下走,只要选过的数在要选的数左上方或右下方的时候,这个数才是可选的,或者说是可到达的.
假设当我们要选$9$时,我们已经选了$1,2,6,8,12$,我们看$9$能否到达呢?
显然,左侧离它最近的数要$\ge$它的行,右侧离它最近的数要$\leq$它的行.这样我们就可以选它.
当然,选完后更新$L[],R[]$.

即代码:

//x为行,y为列
//n行,m列
for (int i = 1; i <= n; i++)
     L[i] = 1 ,R[i] = m;
for (int i = 1; i <= n * m; i++){
    L[x] <= y && y <= R[x]
    for (int j = 1; j < x; j++)
         R[j] = min(R[j], y);

    for (int j = n; j > x; j--)
        L[j] = max(L[j], y);
}

理解了这个贪心,题目就很水了.
据说要注意空间,时间…..全程cin好像没啥事.

#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int INF = 1e7;
const int MAXN = 5e3 + 10;

int T[MAXN * MAXN], l[MAXN * MAXN], R[MAXN], L[MAXN];

int main()
{
    int a, b, c, d;
    int n, m, q;
    cin >> l[0] >> a >> b >> c >> d >> n >> m >> q;

    for (int i = 1; i <= m * n; i++)
        T[i] = i, l[i] = (1LL * a * l[i - 1] * l[i - 1] + 1LL * b * l[i - 1] + c) % d;

    for (int i = 1; i <= n * m; i++)
        swap(T[i], T[l[i] % i + 1]);

    int x, y;
    for (int i = 0; i < q; i++) {
        cin >> x >> y;
        swap(T[x], T[y]);
    }

    for (int i = 1; i <= n * m; i++)
        l[T[i]] = i;

    for (int i = 1; i <= n; i++)
        R[i] = m, L[i] = 1;

    for (int i = 1, sum = 0; i <= n * m; i++) {
        x = (l[i] - 1) / m + 1, y = l[i] % m ? l[i] % m : m;

        if (L[x] <= y && y <= R[x]) {
            cout << i << ' ';
            sum++;
            if (sum == n * m - 1)
                break;

            for (int j = 1; j < x; j++)
                R[j] = min(R[j], y);

            for (int j = n; j > x; j--)
                L[j] = max(L[j], y);
        }
    }

    return 0;
}