A – 矩阵游戏

这道题看了题解之后发现就是一道 sb 题。

考虑将每一列看成一个数，发现如果忽略掉列的操作，这些数仍然满足等差的条件，所以我们只要暴力算完第一列就可以进行等差了。如果考虑列的操作，那么我们就大力暴力就行了，时间复杂度是\(O(n + m)\)。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, mod = 1e9 + 7;

int row[MAX_N], col[MAX_N], n, m, k;
long long ans = 0;
char opt[20];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= max(n, m); i++)
        row[i] = col[i] = 1;

    while (k--)
    {
        int x, y;
        scanf("%s%d%d", opt + 1, &x, &y);
        if (opt[1] == 'R')
            row[x] = 1LL * row[x] * y % mod;
        else
            col[x] = 1LL * col[x] * y % mod;
    }
    int colBatch = 0, batch = 0;
    for (int i = 1; i <= n; i++)
        colBatch = (1LL * colBatch + 1LL * (1LL * (i - 1) * m % mod + 1) % mod * row[i] % mod) % mod, batch = (1LL * batch + 1LL * row[i]) % mod;
    int current = colBatch;
    for (int j = 1; j <= m; j++)
        ans = (ans + 1LL * current * col[j] % mod) % mod, current = (1LL * current + 1LL * batch) % mod;
    printf("%lld", ans);
    return 0;
}

B – 跳房子

这道题听毒瘤的，很长。

我们考虑设置数组\(jump[i]\)表示从第\(i\)行第一列跳到下一次第一列的行号。这样的话，我们在找循环节的时候可以快很多，只需要除掉就好，剩余的地方进行暴力就行。

修改就用到了比较玄秘的方法，考虑一个点被修改对第一列的影响，发现被影响的点必然在一个区间内，且连续，所以我们可以从被修改点往左跳，找到区间并且全部修改为新的答案，这样就可以不用被计算多次了。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2020;

int jump[MAX_N], ptx, pty;
int mp[MAX_N][MAX_N], n, m, q;
char opt[20];

int fix(int pa, int pb) { return (pa % pb + pb) % pb; }

int next_row(int x, int y)
{
    int next_row = -1;
    int max_value = -1;
    for (int rr = x - 1; rr <= x + 1; ++rr)
    {
        const int value = mp[fix(rr, n)][fix(y + 1, m)];
        if (value > max_value)
        {
            max_value = value;
            next_row = rr;
        }
    }
    return next_row;
}

int rush(int x, int y)
{
    do
    {
        x = fix(next_row(x, y++), n);
    } while (y < m);
    return x;
}

struct interval
{
    int l = std::numeric_limits<int>::max();
    int r = std::numeric_limits<int>::min();
    bool isCotain(int x) { return l <= x && x <= r; }
    bool isEmpty() { return l > r; }
    int size() { return r - l + 1; }
};

void update(int x, int y)
{
    const int target_row = rush(x, y);
    interval rows;
    rows.l = rows.r = x;
    int cc = y;
    while (cc > 0)
    {
        --cc;
        interval new_rows;
        for (int rr = rows.l - 1; rr <= rows.l + 1; ++rr)
        {
            if (rows.isCotain(next_row(rr, cc)))
            {
                new_rows.l = rr;
                break;
            }
        }
        for (int rr = rows.r + 1; rr >= rows.r - 1; --rr)
        {
            if (rows.isCotain(next_row(rr, cc)))
            {
                new_rows.r = rr;
                break;
            }
        }
        if (new_rows.isEmpty())
            return;
        rows = new_rows;
    }
    if (rows.size() >= n)
        for (int rr = 0; rr < n; ++rr)
            jump[rr] = target_row;
    else
        for (int rr = rows.l; rr <= rows.r; ++rr)
            jump[fix(rr, n)] = target_row;
    return;
}

void move(int steps)
{
    static int walk_id = 0;
    static int last_walk_id[MAX_N];
    static int last_k[MAX_N];
    walk_id++;

    if (steps >= m - pty)
    {
        steps -= (m - pty);
        ptx = rush(ptx, pty), pty = 0;
    }
    while (steps >= m)
    {
        steps -= m;
        ptx = jump[ptx];

        if (last_walk_id[ptx] == walk_id)
        {
            const int cycle_len = last_k[ptx] - steps;
            if (steps >= cycle_len)
            {
                const int n_cycles = steps / cycle_len;
                steps -= n_cycles * cycle_len;
            }
        }
        last_walk_id[ptx] = walk_id;
        last_k[ptx] = steps;
    }
    while (steps--)
        ptx = fix(next_row(ptx, pty++), n);
}

int main()
{
    /*
    freopen("jump.in", "r", stdin);
    freopen("jump.out", "w", stdout);
    */
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &mp[i][j]);
    scanf("%d", &q);
    for (int i = 0; i < n; i++)
        jump[i] = rush(i, 0);
    while (q--)
    {
        int a, b, c;
        scanf("%s%d", opt + 1, &a);
        if (opt[1] == 'm')
            move(a), printf("%d %d\n", ptx + 1, pty + 1);
        else
        {
            scanf("%d%d", &b, &c);
            a--, b--;
            mp[a][b] = c;
            for (int i = a - 1; i <= a + 1; i++)
                update(fix(i, n), fix(b - 1, m));
        }
    }
    return 0;
}

C – 优美序列

这道题暴力跳，然后 AC 看天命。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, arr[MAX_N], pos[MAX_N], q, log2_[MAX_N];
int stmax[18][MAX_N], stmin[18][MAX_N], posmax[18][MAX_N], posmin[18][MAX_N];

inline int query_pos_max(int l, int r)
{
    int len = r - l + 1, k = log2_[len];
    return max(posmax[k][l], posmax[k][l + len - (1 << k)]);
}

inline int query_pos_min(int l, int r)
{
    int len = r - l + 1, k = log2_[len];
    return min(posmin[k][l], posmin[k][l + len - (1 << k)]);
}

inline int query_max(int l, int r)
{
    int len = r - l + 1, k = log2_[len];
    return max(stmax[k][l], stmax[k][l + len - (1 << k)]);
}

inline int query_min(int l, int r)
{
    int len = r - l + 1, k = log2_[len];
    return min(stmin[k][l], stmin[k][l + len - (1 << k)]);
}

int main()
{

    freopen("sequence23.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
        log2_[i] = log2_[i >> 1] + 1;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &arr[i]), pos[arr[i]] = i;
        stmax[0][i] = arr[i], stmin[0][i] = arr[i];
        posmin[0][arr[i]] = i, posmax[0][arr[i]] = i;
    }
    for (int i = 1; (1 << i) <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            stmax[i][j] = max(stmax[i - 1][j], stmax[i - 1][j + (1 << (i - 1))]);
            stmin[i][j] = min(stmin[i - 1][j], stmin[i - 1][j + (1 << (i - 1))]);
            posmax[i][j] = max(posmax[i - 1][j], posmax[i - 1][j + (1 << (i - 1))]);
            posmin[i][j] = min(posmin[i - 1][j], posmin[i - 1][j + (1 << (i - 1))]);
        }
    scanf("%d", &q);
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        int mx, mi;
        while (r - l + 1 != (mx = query_max(l, r)) - (mi = query_min(l, r)) + 1)
        {
            l = min(l, query_pos_min(mi, mx));
            r = max(l, query_pos_max(mi, mx));
        }
        printf("%d %d\n", l, r);
    }
    return 0;
}