[CRCI2008-2009] TABLICA

题意

先有一个 $n \times n$ 的表格，初始按行从左到右、从上到下填入 $1 \dots n^2$ 。

例如 $n=4$ 时，初始表格是：

行\列	1	2	3	4
1	1	2	3	4
2	5	6	7	8
3	9	10	11	12
4	13	14	15	16

一次操作有两种：

把某一行整体循环右移一格；
把某一列整体循环下移一格。

对于每个询问 $(X, R, C)$ ，都要在当前表格上执行下面这套固定流程：

只要 $X$ 还不在第 $C$ 列，就不断右移它当前所在的那一行；
当 $X$ 到了第 $C$ 列后，只要它还不在第 $R$ 行，就不断下移它当前所在的那一列。

要求输出这个询问最少要做多少次操作。注意多个询问是接在一起做的，后面的询问要基于前面操作后的表格继续进行。

思路

先看最直接的想法：真的维护整张表。

每次询问时先把数字 $X$ 找出来，再按题目要求一格一格地移动它：

cpp

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解。
// 直接维护整张表，并按题目要求一格一格地移动目标数字。
const int MAXN = 55;

int n, k;
int a[MAXN][MAXN];

void shift_row_right(int row) {
    int last = a[row][n];
    for (int col = n; col >= 2; col--) {
        a[row][col] = a[row][col - 1];
    }
    a[row][1] = last;
}

void shift_col_down(int col) {
    int last = a[n][col];
    for (int row = n; row >= 2; row--) {
        a[row][col] = a[row - 1][col];
    }
    a[1][col] = last;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    int value = 0;
    for (int row = 1; row <= n; row++) {
        for (int col = 1; col <= n; col++) {
            value++;
            a[row][col] = value;
        }
    }

    for (int q = 1; q <= k; q++) {
        int x, target_row, target_col;
        cin >> x >> target_row >> target_col;

        int row = 0, col = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][j] == x) {
                    row = i;
                    col = j;
                }
            }
        }

        int ans = 0;

        while (col != target_col) {
            shift_row_right(row);
            col = col % n + 1;
            ans++;
        }

        while (row != target_row) {
            shift_col_down(target_col);
            row = row % n + 1;
            ans++;
        }

        cout << ans << '\n';
    }

    return 0;
}

这个做法很好理解，但如果真的维护 $n \times n$ 的表格，空间就是 $O(n^2)$ ，而 $n$ 最大有 $10^4$ ，显然不可能。

单个询问本身其实很简单

如果当前 $X$ 在 $(r, c)$ ，目标是 $(R, C)$ ，那么：

要把它移到第 $C$ 列，需要右移当前这一行
$(C - c + n) \bmod n$ 次；
然后要把它移到第 $R$ 行，需要下移当前这一列
$(R - r + n) \bmod n$ 次。

所以真正困难的不是“这次要移动多少步”，而是：

在经历了前面所有询问之后，数字 $X$ 现在到底在哪个位置？

不维护整张表，只维护历史操作

每个询问实际上只会产生两类影响：

某一行循环右移若干格；
某一列循环下移若干格。

我们把这些操作按顺序记下来。

以后想知道某个数字 $X$ 在哪里，就从它的初始位置出发，把所有历史操作依次“回放”一遍：

如果某次历史操作是“第 $r_0$ 行右移 $d$ 格”，那么只有当前行号正好等于 $r_0$ 的数字才会受影响，它的列号加上 $d$ ；
如果某次历史操作是“第 $c_0$ 列下移 $d$ 格”，那么只有当前列号正好等于 $c_0$ 的数字才会受影响，它的行号加上 $d$ 。

这样就能在不建整张表的情况下，求出任意数字的当前坐标。

为什么这样足够

因为题目里的所有变化，本质上都只是“整行循环位移”或“整列循环位移”。

我们并不关心表里每个格子的值，只关心某个被询问的数字在经历这些位移后落到了哪里。
既然后续询问只有 $K \leqslant 1000$ 个，那么把历史操作全部存下来，再对当前数字回放一遍，复杂度完全够用。

代码

cpp

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69#include <bits/stdc++.h>
using namespace std;

const int MAXK = 1005;
const int MAXOPS = MAXK * 2 + 5;

int n, k;
int op_cnt;
int op_type[MAXOPS];  // 0 表示行右移，1 表示列下移
int op_idx[MAXOPS];   // 受影响的行号或列号
int op_delta[MAXOPS]; // 循环位移的格数

// 把一条历史操作作用到当前坐标 (row, col) 上。
void apply_op(int &row, int &col, int type, int idx, int delta) {
    if (type == 0) {
        if (row == idx) {
            col = (col - 1 + delta) % n + 1;
        }
    } else {
        if (col == idx) {
            row = (row - 1 + delta) % n + 1;
        }
    }
}

// 计算数字 x 在当前表格中的位置。
void get_position(long long x, int &row, int &col) {
    row = (int)((x - 1) / n) + 1;
    col = (int)((x - 1) % n) + 1;
    for (int i = 1; i <= op_cnt; i++) {
        apply_op(row, col, op_type[i], op_idx[i], op_delta[i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int q = 1; q <= k; q++) {
        long long x;
        int target_row, target_col;
        cin >> x >> target_row >> target_col;

        int row, col;
        get_position(x, row, col);

        int row_move = (target_col - col + n) % n;
        int col_move = (target_row - row + n) % n;

        cout << row_move + col_move << '\n';

        if (row_move != 0) {
            op_cnt++;
            op_type[op_cnt] = 0;
            op_idx[op_cnt] = row;
            op_delta[op_cnt] = row_move;
        }

        if (col_move != 0) {
            op_cnt++;
            op_type[op_cnt] = 1;
            op_idx[op_cnt] = target_col;
            op_delta[op_cnt] = col_move;
        }
    }

    return 0;
}

复杂度

时间复杂度： $O(K^2)$
空间复杂度： $O(K)$

这里 $K$ 是询问个数。每次查询最多回放前面 $2K$ 条历史操作。

总结

这题表面上像表格模拟，实际上根本不用维护整张表。

核心转化是：把每次询问留下的影响压成“某行右移多少格、某列下移多少格”，以后查询某个数字的位置时，只回放这些历史操作即可。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。