首页 > 其他分享 >【NOIP2017普及组复赛】题2:图书管理员

【NOIP2017普及组复赛】题2:图书管理员

时间:2024-05-30 11:57:39浏览次数:24  
标签:NOIP2017 编码 23 1123 000 管理员 复赛 读者 图书

题2:图书管理员

【题目描述】

图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个 正整数。 每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图 书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。 小 D D D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写 一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他 需要的书,请输出 − 1 -1 −1。

【输入】

第一行,包含两个正整数 n n n 和 q q q,以一个空格分开,分别代表图书馆里 书的数量和读者的数量。 接下来的 n n n 行,每行包含一个正整数,代表图书馆里某本书的图书编码。 接下来的 q q q 行,每行包含两个正整数,以一个空格分开,第一个正整数代表图书馆 里读者的需求码的长度,第二个正整数代表读者的需求码。

【输出】

件有 q q q 行,每行包含一个整数,如果存在第 i i i 个读者所需要的书,则在第 i i i 行输出第 i i i 个读者所需要的书中图书编码最小的那本书的图书编码,否则输出 − 1 -1 −1。

【输入样例】

5 5
2123
1123
23
24
24
2 23
3 123
3 124
2 12
2 12

【输出样例】

23
1123
-1
-1
-1

【样例说明】

第一位读者需要的书有 2123 、 1123 、 23 2123、1123、23 2123、1123、23,其中 23 23 23 是最小的图书编码。第二位读者需要的书有 2123 、 1123 2123、1123 2123、1123,其中 1123 1123 1123 是最小的图书编码。对于第三位,第四位和第五位读者,没有书的图书编码以他们的需求码结尾,即没有他们需要的书,输出 − 1 -1 −1。

【数据规模与约定】

对于 20 % 20\% 20% 的数据, 1 ≤ n ≤ 2 1 ≤ n ≤ 2 1≤n≤2。

另有 20 % 20\% 20% 的数据, q = 1 q = 1 q=1。

另有 20 % 20\% 20% 的数据,所有读者的需求码的长度均为 1 1 1。

另有 20 % 20\% 20% 的数据,所有的图书编码按从小到大的顺序给出。

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 , 000 , 1 ≤ q ≤ 1 , 000 1 ≤ n ≤ 1,000,1 ≤ q ≤ 1,000 1≤n≤1,000,1≤q≤1,000,所有的图书编码和需求码均不超过 10 , 000 , 000 10,000,000 10,000,000。

【代码如下】:

#include <bits/stdc++.h>
using namespace std;
const int S = 1005;
long long b[S], x[S], tmp[S], xc[S]; 
int n, q;
int main() {
	cin >> n >> q;
	for (int i = 1; i <= S; i++)
		tmp[i] = 1;
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	sort(b, b + n + 1); 
	for (int i = 1; i <= q; i++) {
		cin >> xc[i] >> x[i];
		for (int j = 1; j <= xc[i]; j++)
			tmp[i] *= 10; 
	}
	for (int i = 1; i <= q; i++) {
		for (int j = 1; j <= n; j++)
			if (b[j] % tmp[i] == x[i]) { 
				cout << b[j] << '\n';
				break;
			} else if (j == n) {
				cout << -1 << '\n';
				break;
			}
	}
	return 0;
}

标签:NOIP2017,编码,23,1123,000,管理员,复赛,读者,图书
From: https://blog.csdn.net/lpstudio/article/details/139310014

相关文章

  • CSP历年复赛题-P1308 [NOIP2011 普及组] 统计单词数
    原题链接:https://www.luogu.com.cn/problem/P1308题意解读:给定单词a,文本b,在b中找a的个数,并找a第一次出现的位置,注意b中任何位置可能含有多个连续空格。解题思路:通过双指针找b中每一个单词的首、尾位置i,j,与a进行一一比较即可。注意1:比较时不考虑大小写,可以统一转成小写字符tolo......
  • CSP历年复赛题-P1199 [NOIP2010 普及组] 三国游戏
    原题链接:https://www.luogu.com.cn/problem/P1199题意解读:人机轮流选将,电脑策略就是破坏可能和人已选能组成最大默契值的将,问人是否必胜,求出站的一对武将的默契值。解题思路:贪心题通常比较难以下手,经过分析,人肯定不可能选到每一行的最大默契值,因为电脑会破坏;进一步思考,那人能......
  • CSP历年复赛题-P1190 [NOIP2010 普及组] 接水问题
    原题链接:https://www.luogu.com.cn/problem/P1190题意解读:n个人在m个水龙头排队接水,每个人接水量不同,接完水的排队的人可以接上,求总的接水时间。解题思路:1、先把前m个人安排在m个水龙头2、对于m后面的每一个人,都排在目前m个水龙头总接水时间最短的后面3、最后看m个水龙头最大......
  • CSP历年复赛题-P1179 [NOIP2010 普及组] 数字统计
    原题链接:https://www.luogu.com.cn/problem/P1179题意解读:统计l~r之间的整数包括多少个数字2。解题思路:枚举每一个数,对每一个数的每一位数字进行判断。100分代码:#include<bits/stdc++.h>usingnamespacestd;intl,r,ans;intmain(){cin>>l>>r;f......
  • CSP历年复赛题-P1058 [NOIP2008 普及组] 立体图
    原题链接:https://www.luogu.com.cn/problem/P1058题意解读:在m*n的平面上,输出若干个立方体,每一个格子可以有高度不同的多个立方体。解题思路:此题咋一看来,无从下手,仔细分析,其实一道模拟题。如何模拟?我们一起来解决一下几个关键问题:1、如何画图?要在平面上输出图案,本质上就是将......
  • CSP历年复赛题-P1067 [NOIP2009 普及组] 多项式输出
    原题链接:https://www.luogu.com.cn/problem/P1067题意解读:模拟法依次输出多项式内容即可,但是需要考虑的周全,主要有以下关键点:1、系数为0时不输出多项式2、第一个符号,只有负号才输出3、次数不为0时,不输出为1的系数;次数为0时,输出所有系数4、次数为1时,不输出次数;次数为0时不输......
  • CSP历年复赛题-P1057 [NOIP2008 普及组] 传球游戏
    原题链接:https://www.luogu.com.cn/problem/P1057题意解读:n个人围一圈,从1开始传球m次,每次可以往左或右传,计算球再次传给1的方案数。解题思路:求方案数,通常就是DP问题,此题DP状态并不难想,如果实在不会,也可以通过DFS暴搜得部分分。1、DFS60分代码:#include<bits/stdc++.h>using......
  • CSP历年复赛题-P1055 [NOIP2008 普及组] ISBN 号码
    原题链接:https://www.luogu.com.cn/problem/P1055题意解读:验证ISBN最后一位是否正确。解题思路:直接模拟,不多说,上代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;intmain(){strings;cin>>s;intcode=0;intcnt=0;for(inti......
  • CSP历年复赛题-P1096 [NOIP2007 普及组] Hanoi 双塔问题
    原题链接:https://www.luogu.com.cn/problem/P1096题意解读:汉诺双塔的移动次数,与经典汉诺塔的区间在于同一个尺寸盘子有两个。解题思路:可以直接用经典汉诺塔方法来计算,双塔的结果就最终乘以2即可。首先想到的是递归,但是由于数据量n最大200,递归会超时,但是50%的样例应该没问题,先......
  • 【NOIP2015普及组复赛】题3:求和
    题3:求和【题目描述】一条狭长的纸带被均匀划分出了nnn个格子,格子编号从11......