[NOIP 2017 普及组] 图书管理员

GitHub跳转原题关系图返回列表

按需求码长度把每本书的后缀分类，预处理每种后缀能对应到的最小图书编码后回答查询。

OJ: luogu

题目 ID: P3955

难度:普及-

标签:模拟枚举

日期: 2026-06-19 01:03

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 n 本书，每本书都有一个正整数图书编码。

每次给出一个需求码长度 l 和一个需求码 x，要找出所有“后 l 位恰好等于 x”的图书中，编码最小的那一本。

如果没有任何一本书满足，输出 -1。

思路

先看最直接的做法：

每次查询都把所有图书扫一遍，检查：

book % 10^l == x

如果满足，就拿它更新最小值。

这个想法最直观，也适合做对拍：

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXL = 8;
const int INF = 0x3f3f3f3f;

int n, q;
int a[MAXN];
int pw10[MAXL + 1];

void init_pow10() {
    pw10[0] = 1;
    for (int i = 1; i <= MAXL; i++) {
        pw10[i] = pw10[i - 1] * 10;
    }
}

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

    init_pow10();

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= q; i++) {
        int len, need;
        int ans = INF;
        cin >> len >> need;

        // 逐本书检查后 len 位是否等于需求码。
        for (int j = 1; j <= n; j++) {
            if (a[j] % pw10[len] == need) {
                ans = min(ans, a[j]);
            }
        }

        if (ans == INF) {
            cout << -1 << '\n';
        }
        else {
            cout << ans << '\n';
        }
    }

    return 0;
}

但正式做法可以把这一步提前做掉。

因为图书编码最大不超过 10^7，所以长度最多只要考虑到 8 位。

我们可以对每一本书，枚举后缀长度 1..8：

  1. 算出它后 len 位组成的数
  2. 记录这个后缀目前能对应到的最小图书编码

这样就得到一张“后缀 -> 最小图书编码”的表。

以后每次查询时，直接按 (len, x) 去查：

  • 查得到就输出预处理好的最小值
  • 查不到就输出 -1

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXL = 8;

int n, q;
int a[MAXN];
int pw10[MAXL + 1];
map<int, int> best[MAXL + 1];

void init_pow10() {
    pw10[0] = 1;
    for (int i = 1; i <= MAXL; i++) {
        pw10[i] = pw10[i - 1] * 10;
    }
}

void build_answer() {
    for (int i = 1; i <= n; i++) {
        for (int len = 1; len <= MAXL; len++) {
            int suffix = a[i] % pw10[len];
            if (best[len].count(suffix) == 0 || a[i] < best[len][suffix]) {
                best[len][suffix] = a[i];
            }
        }
    }
}

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

    init_pow10();

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build_answer();

    for (int i = 1; i <= q; i++) {
        int len, need;
        cin >> len >> need;
        if (best[len].count(need)) {
            cout << best[len][need] << '\n';
        }
        else {
            cout << -1 << '\n';
        }
    }

    return 0;
}

复杂度

预处理时，每本书会枚举 1..8 这几个长度，所以时间复杂度是 O(8n)O(8n)。

每次查询用映射查找，时间复杂度是 O(logM)O(log M)，这里 M 是这一类后缀的种数。

总复杂度可以写成 O(n+qlogM)O(n + q log M)，空间复杂度是 O(M)O(M)。

总结

这题的关键是把“每次都扫描全部图书”改成“先把所有可能后缀的最小值记下来”。

本质上是一个很小范围的后缀预处理题。