[noip2017-普及] 图书管理员

题目描述

图书馆中每本书有正整数编码。给出 $n$ 个图书编码和 $q$ 个询问，每个询问形如 $(k, b)$ ：若某编码的十进制末 $k$ 位恰好等于 $b$ ，则该书符合这位读者的需求。对每个询问输出符合要求的最小图书编码，没有则输出 $-1$ 。输入：第一行 $n, q$ ；随后 $n$ 行每行一个图书编码；随后 $q$ 行每行两个正整数 $k, b$ 。样例输入 5 5 / 2123 1123 23 24 24 / 2 23 / 3 123 / 3 124 / 2 12 / 2 12，输出 23 / 1123 / -1 / -1 / -1。数据范围： $n, q \leqslant 1000$ ，编码与需求码均不超过 $10^7$ 。

思路

把图书编码升序排序，再在有序数组里从左往右找第一个满足 code % 10^k == b 的编码，首个命中即候选中的最小者。用需求码长度决定模数 $10^k$ ，顺带处理了前导零。

参考代码

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#!/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 12:32
# update_at: 2026-10-02 12:32

import sys

pow10 = [1] * 8  # pow10[k] = 10**k，用来按长度截取编码的末 k 位


def build_pow10() -> None:
    """预处理 10 的幂：需求码长度 ≤ 7，取末 k 位只需要这张小表。"""
    for k in range(1, 8):
        pow10[k] = pow10[k - 1] * 10


def best_suffix_match(codes: list[int], queries: list[tuple[int, int]]) -> list[int]:
    """对每个询问 (长度 k, 需求码 need) 返回以 need 结尾的最小图书编码，不存在为 -1。

    编码按从小到大排好后从左往右扫，命中的第一个后缀就是最小答案，
    于是每个询问只需在有序编码里做一次顺序查找，O(n) 回答。
    """
    return [
        next((code for code in codes if code % pow10[k] == need), -1)  # 首个匹配即最小
        for k, need in queries
    ]


def solve() -> None:
    build_pow10()
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, q = next(data), next(data)
    codes = sorted(next(data) for _ in range(n))  # 排序让「首个命中 = 最小答案」成立
    queries = [(next(data), next(data)) for _ in range(q)]
    print('\n'.join(map(str, best_suffix_match(codes, queries))))


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/**
 * 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 15:50
 * update_at: 2026-10-06 15:50
 */
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1005; // 图书数量上限

ll code[MAXN];      // 升序排序后的图书编码
ll pow10[10];       // pow10[k] = 10^k，用来截取末 k 位

int main() {
    pow10[0] = 1;
    for (int k = 1; k <= 8; k++) {
        pow10[k] = pow10[k - 1] * 10;
    }

    ll n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> code[i];
    }
    sort(code, code + n); // 排序后「第一个命中」就是最小的编码

    for (int i = 0; i < q; i++) {
        ll len, need;
        cin >> len >> need;
        ll ans = -1;
        for (int j = 0; j < n; j++) {
            // 编码末 len 位等于需求码，即对 10^len 取模相等
            if (code[j] % pow10[len] == need) {
                ans = code[j];
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

[noip2017-普及] 图书管理员

目录

题目描述

思路

参考代码