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

知识点

枚举、模运算、数位处理

解题思路

长度为len的需求码可用book模10^len判断。每次查询遍历所有图书，满足后缀要求时维护最小编码，找不到输出-1。n和q均不超过1000，百万次比较可直接处理。

正确性说明

十进制编码除以10^len所得余数正是末len位的数值；该需求码按题意长度给出。因此枚举筛出所有满足需求的书并取最小值，得到要求的答案。

易错点

有重复图书编码；不能返回输入顺序第一本而忘记最小值；没有匹配输出-1；10^len用整数循环计算。

复杂度

时间O(nq+各查询长度之和)，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;vector<long long>a(n);for(auto&x:a)cin>>x;while(q--){int len;long long code;cin>>len>>code;long long mod=1;while(len--)mod*=10;long long ans=LLONG_MAX;for(auto x:a)if(x%mod==code)ans=min(ans,x);cout<<(ans==LLONG_MAX?-1:ans)<<'\n';}}