Luogu 2354 [NOI 2014] 随机数生成器

传送门

思路

唉，我太弱了，什么都不会，这么一个傻逼题，我却看成了要你构造一种交换方案使得答案最小，结果后面的额外交换是题目给定的。唉，我太弱啦！

显然生成这个矩阵没有任何难度，然后就很容易想到一个贪心方案：从小到大依次检查是否可以选择某个数。如果不行就跳过，如果可以就选上，并且规定其左下和右上不能选。这个过程可以通过记录每一行能够选的位置的最大开始位置和最小结束位置来实现，但是我太弱了，什么都不会，这个都想不到。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
#define loop register int
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int maxn = int(5e3) + 5;
LL x, a, b, c, d;
int n, m, q;

int rect[maxn * maxn];

void exchange()
{
    for (loop i = 1, to = n * m; i <= to; i++)
    {
        x = (a * x % d * x + b * x + c) % d;
        std::swap(rect[i - 1], rect[x % i]);
    }
    while (q--)
    {
        std::swap(rect[readIn() - 1], rect[readIn() - 1]);
    }
}

int pos[maxn * maxn];
int minRange[maxn];
int maxRange[maxn];

void solve()
{
    for (loop i = 0, to = n * m; i < to; i++)
        pos[rect[i]] = i;
    std::vector<int> ans;
    ans.reserve(n + m - 1);

    for (loop i = 0; i < n; i++)
    {
        minRange[i] = 0;
        maxRange[i] = m - 1;
    }
    for (loop i = 1, to = n * m; i <= to; i++)
    {
        int r = pos[i] / m;
        int c = pos[i] % m;
        if (!(minRange[r] <= c && c <= maxRange[r]))
            continue;
        ans.push_back(rect[pos[i]]);
        for (int j = 0; j < r; j++)
            maxRange[j] = std::min(maxRange[j], c);
        for (int j = r + 1; j < n; j++)
            minRange[j] = std::max(minRange[j], c);
    }
    for (loop i = 0; i < ans.size(); i++)
    {
        printOut(ans[i]);
        putchar(' ');
    }
}

void run()
{
    x = readIn();
    a = readIn();
    b = readIn();
    c = readIn();
    d = readIn();
    n = readIn();
    m = readIn();
    q = readIn();
    for (loop i = 1, to = n * m; i <= to; i++)
        rect[i - 1] = i;
    exchange();

    solve();
}

int main()
{
    run();
    return 0;
}