[NOIP2012-普及] 寻宝

题目描述

藏宝楼除顶层外有 $N$ 层，每层 $M$ 个房间围成一圈，编号 $0\sim M-1$ 。每间房间给出是否有楼梯（ $s$ ）和指示牌数字（ $x$ ）；从某房间出发，按逆时针方向数第 $x$ 个有楼梯的房间上楼，到达上一层同编号房间。给定底层入口房间号，求每层第一个进入房间的指示牌数字之和对 $20123$ 取模。

输入格式： 第一行两个整数 $N,M$ ；接下来 $N\times M$ 行，每行两个整数 $s,x$ ，按层、按房间顺序给出；最后一行一个整数表示底层入口房间号。 输出格式： 一个整数，即密钥对 $20123$ 取模。 样例： 输入 2 3 / 1 2 / 0 3 / 1 4 / 0 1 / 1 5 / 1 2 / 1，输出 5。

思路

每层楼梯位置固定，总数为 $S$ ，数第 $x$ 个等价于数第 $(x-1)\bmod S+1$ 个。把每层有楼梯的房间升序存下，再用前缀和判断目标落在 $[\text{start},M-1]$ 段还是回绕的 $[0,\text{start})$ 段，即可 $O(1)$ 定位上楼房间；逐层累加即得密钥。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 09:45
# update_at: 2026-10-02 09:45

import sys
from collections.abc import Iterator
from itertools import accumulate

MOD = 20123  # 密钥的模数


def climb_floor(stairs: list[int], pre: list[int], start: int, x: int) -> int:
    """从 start 号房出发，返回逆时针数第 x 个有楼梯房间的编号。

    x 可能远大于本层楼梯数 total，先绕整圈消掉：第 x 个等价于第
    k = (x-1) % total + 1 个。再按前缀和把它定位到 [start, M-1] 段
    或回绕后的 [0, start) 段，两段各自一次下标计算即可。
    """
    total = len(stairs)
    k = (x - 1) % total + 1          # 去掉整圈后还差 k 个楼梯
    before = total - pre[start]      # 房间 [start, M-1] 上的楼梯数
    if before >= k:                  # 不用回绕：这是本段里第 k 个楼梯
        return stairs[pre[start] + k - 1]
    return stairs[k - before - 1]    # 回绕后只剩 k-before 个，落在前缀段里


def read_floors(rooms: Iterator[int], n: int, m: int) -> list[tuple[list[int], list[int], list[int]]]:
    """读入 n 层楼，每层返回 (楼梯房间列表, 楼梯前缀和, 指示牌数字列表)。"""
    floors = []
    for _ in range(n):
        signs = []
        stairs = []      # 楼梯房间编号，天然升序
        for j in range(m):
            up = next(rooms)  # 该房间是否有楼梯
            signs.append(next(rooms))
            if up:
                stairs.append(j)
        stair_set = set(stairs)
        # pre[j] = 房间 [0, j) 里的楼梯数，下标按房间号（长度 m+1）
        pre = [0, *accumulate(1 if j in stair_set else 0 for j in range(m))]
        floors.append((stairs, pre, signs))
    return floors


def solve() -> None:
    rooms = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(rooms), next(rooms)
    floors = read_floors(rooms, n, m)
    room = next(rooms)  # 底层入口房间编号

    key = 0
    for stairs, pre, signs in floors:
        key += signs[room]  # 密钥累加本层第一个进入房间的指示牌数字
        room = climb_floor(stairs, pre, room, signs[room])
    print(key % MOD)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:55
 * update_at: 2026-10-06 14:59
 */
#include <iostream>
using namespace std;

typedef long long ll;
const ll MOD = 20123;          // 密钥模数
const int MAXN = 10005;        // 最大层数
const int MAXM = 105;          // 每层最大房间数

int n, m;                      // 层数、每层的房间数
ll s[MAXN][MAXM];              // s[i][j]：第 i 层 j 号房间是否有楼梯
ll x[MAXN][MAXM];              // x[i][j]：第 i 层 j 号房间指示牌数字
ll pre[MAXN][MAXM + 1];        // pre[i][j]：第 i 层 [0, j) 内楼梯个数
int stairs[MAXN][MAXM];        // 每层有楼梯的房间编号，按升序存放
int cnt[MAXN];               // 每层楼梯总数

// 在第 floor 层从 start 出发，返回逆时针数第 x 个有楼梯的房间编号
int climb(int floor_id, int start, ll sign) {
    int total = cnt[floor_id];               // 本层楼梯总数
    // 第 sign 个与第 k 个相同，去掉绕整圈的影响
    ll k = (sign - 1) % total + 1;
    ll before = total - pre[floor_id][start]; // [start, M-1] 中的楼梯数
    if (before >= k) {
        // 不用回绕：start 及其之后的第 k 个楼梯
        return stairs[floor_id][pre[floor_id][start] + k - 1];
    }
    // 回绕到 [0, start) 段，取剩余的第 k - before 个楼梯
    return stairs[floor_id][k - before - 1];
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> s[i][j] >> x[i][j];
        }
        // 预处理前缀和与楼梯编号
        pre[i][0] = 0;
        cnt[i] = 0;
        for (int j = 0; j < m; j++) {
            pre[i][j + 1] = pre[i][j] + s[i][j];
            if (s[i][j]) {
                stairs[i][cnt[i]++] = j;
            }
        }
    }

    int room;
    cin >> room;

    ll key = 0;
    for (int i = 0; i < n; i++) {
        key = (key + x[i][room]) % MOD; // 累加本层进入房间的指示牌数字
        room = climb(i, room, x[i][room]); // 找到上层的进入房间
    }

    cout << key << "\n";
    return 0;
}