【题解】P3955 图书管理员 (NOIP2017普及组 T2)
为什么发这道题呢,因为这道题官方标签是字符串和排序,实际上可以不用,反而更简单
先看下题
[NOIP2017 普及组] 图书管理员
题目背景
NOIP2017 普及组 T2
题目描述
图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个正整数。 每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。 小 D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他需要的书,请输出 -1
。
输入格式
第一行,包含两个正整数 ,以一个空格分开,分别代表图书馆里 书的数量和读者的数量。
接下来的 行,每行包含一个正整数,代表图书馆里某本书的图书编码。
接下来的 行,每行包含两个正整数,以一个空格分开,第一个正整数代表图书馆 里读者的需求码的长度,第二个正整数代表读者的需求码。
输出格式
$ q$ 行,每行包含一个整数,如果存在第 个读者所需要的书,则在第 行输出第 个读者所需要的书中图书编码最小的那本书的图书编码,否则输出。
样例 #1
样例输入 #1
1 | 5 5 |
样例输出 #1
1 | 23 |
提示
数据规模与约定
对于 的数据,。
另有 的数据,。
另有 的数据,所有读者的需求码的长度均为 。
另有 的数据,所有的图书编码按从小到大的顺序给出。
对于 的数据,,所有的图书编码和需求码均不超过 。
思考
NOIP 2017普及组 第2题。
主要就是比较一个数后几位长度是否与给定值相等,那么很容易想到的是字符串,比较后面几位,写起来费事一点
我翻遍了洛谷题解区,清一色的字符串+STL里的快排,其实不需要,我们先理解一个性质
1234 这个数,如何取后面2位,也就是34?通过数学里的方法,我们只需要对1234 mod 100就能求到是34。同样如果对1234取后面3位的234,只需要 mod1000即可。1000是10的3次方,我们也正好要后面3位数。
所以:一个数需要取末尾n位数,就可以用这个数mod(10^n)
明白这个后,那就很简单了,设某个读者需要的书末尾长度是len,那么pow(10,len)就是这个mod数,也就是用书籍号码去mod它。
对于排序,也不需要那么复杂,因为我们只需要最小的,所以一开始int一个非常大的数,然后只要发现符合规则的数且小于这个初始值的,赋值给它就可以。
代码
1 |
|
理解了思考那一段之后,我想这个代码就很容易看懂了。