[NOIP 2012 普及组] 寻宝

题意

有 N 层楼，每层有 M 个房间，编号 0..M-1，围成一圈。

每个房间有两项信息：

这个房间是否有楼梯通向上一层；
这个房间指示牌上的数字 x。

小明在底层先进入某个起始房间。之后每到一层，都要做两件事：

把当前房间指示牌上的数字加入答案；
从当前房间开始，按逆时针方向寻找第 x 个有楼梯的房间，并从那里上楼。

如果当前房间本身就有楼梯，那么它也算第一个有楼梯的房间。

题目要求输出所有层第一次进入房间的数字之和，对 20123 取模。

思路

最直接的做法，是在每一层真的沿着一圈房间慢慢数：

遇到一个有楼梯的房间就计数一次；
数到第 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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXM = 105;
const int MOD = 20123;

int n, m;
int has_stair[MAXN][MAXM];
int val[MAXN][MAXM];

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> has_stair[i][j] >> val[i][j];
        }
    }

    int now;
    cin >> now;

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + val[i][now]) % MOD;

        int need = val[i][now];
        int pos = now;

        // 朴素做法：真的沿着一圈一圈地数第 need 个有楼梯的房间。
        while (true) {
            if (has_stair[i][pos]) {
                need--;
                if (need == 0) {
                    now = pos;
                    break;
                }
            }
            pos++;
            if (pos == m) {
                pos = 0;
            }
        }
    }

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

但这里有个明显浪费：x 最大能到 10^6，而一层里房间数只有 M <= 100。

也就是说，如果某层只有几个有楼梯的房间，我们其实会在同一圈里反复数很多次。

把一层压缩成“楼梯房间环”

对某一层，只保留所有有楼梯的房间编号。

例如这一层有楼梯的房间是：

1, 4, 7

那么无论你怎么沿着整圈房间走，真正会影响上楼落点的只有这三个位置。

因为每绕完整层一圈，遇到的“有楼梯房间顺序”都会重复一次，所以找第 x 个有楼梯房间，其实等价于找第：

((x - 1) mod cnt) + 1

个有楼梯房间，其中 cnt 是这一层有楼梯房间的总数。

怎么确定从哪里开始数

我们把本层有楼梯的房间编号升序存进数组 stair_pos。

现在已知当前房间编号是 now，需要找到“从 now 开始逆时针走，遇到的第一个有楼梯房间”。

这正好就是 stair_pos 中第一个 >= now 的位置，可以用 lower_bound 找到。

如果找到了，就从那个位置开始数；
如果没找到，说明要从数组开头重新开始。

接下来向后移动 step = (x - 1) mod cnt 个位置，就是下一层到达的房间编号。

正式做法

对每一层：

把当前房间的数字加入答案，并对 20123 取模；
令 cnt 为本层有楼梯的房间数；
令 step = (x - 1) mod cnt；
用 lower_bound 找到从当前房间出发的第一个楼梯房间；
下一层房间就是循环数组里的第 (pos + step) 个位置。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000 + 5;
const int MAXM = 100 + 5;
const int MOD = 20123;

int n, m;
int has_stair[MAXN][MAXM];
int val[MAXN][MAXM];
vector<int> stair_pos[MAXN];

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        stair_pos[i].clear();
        for (int j = 0; j < m; j++) {
            cin >> has_stair[i][j] >> val[i][j];
            if (has_stair[i][j]) {
                stair_pos[i].push_back(j);
            }
        }
    }

    int now;
    cin >> now;

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + val[i][now]) % MOD;

        int cnt = (int) stair_pos[i].size();
        int step = (val[i][now] - 1) % cnt;

        // 找到从当前房间开始，逆时针方向遇到的第一个有楼梯房间。
        vector<int>::iterator it = lower_bound(stair_pos[i].begin(), stair_pos[i].end(), now);
        int pos = 0;
        if (it == stair_pos[i].end()) {
            pos = 0;
        }
        else {
            pos = (int) (it - stair_pos[i].begin());
        }

        now = stair_pos[i][(pos + step) % cnt];
    }

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

复杂度

时间复杂度： $O(NM + N log M)$
空间复杂度： $O(NM)$

总结

这题的关键是看出：

虽然房间围成一圈，但真正有意义的只是“有楼梯的那些房间”。

把一层压缩成一个循环数组后，大数字 x 就可以先按楼梯房间总数取模，再做一次循环跳转。

一图流解析

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