♐ CSP_J 组真题
2017年
2. 图书管理员

线上OJ:

一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1415 (opens in a new tab) AcWing:https://www.acwing.com/problem/content/description/472/ (opens in a new tab)

核心思想:

举例2123和23,因为需求码的23长度为2,所以只要判断 2123 % 100,余数和23相等即可.

注1: % 100是考虑23长度为2, 就对10^2求余数
注2: 由于输出最小的,所以对图书编号先排序,然后再匹配, 这样得到的第一个就是答案
注3: 由于n和q都是1000,所以时间复杂度只有 10610^6。可以在排序后直接暴力匹配

题解代码:

#include <bits/stdc++.h>
using namespace std;
// 先枚举10的几次方备用, 比如23长度为2,则求余数时%p[2],正好是%100
int p[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; 
 
// 核心思想: 举例2123和23,因为23长度为2,所以2123%100,余数和23相等
// 由于输出最小的,所以对图书编号先排序,然后匹配的第一个就是答案 
// 由于n和q都是1000,所以时间复杂度只有10^6。可以在排序后暴力匹配 
int main()
{
	int n, q, len, user_num;
	cin >> n >> q;
	int book[n+5];
	
	for(int i = 1; i <= n; ++i)  cin >> book[i];  // 读入图书编码 
		
	sort(book + 1, book + 1 + n);  // 直接调用sort进行升序排序 
	
	for(int i = 1; i <= q; ++i)	   // q次询问 
	{
		cin >> len >> user_num;
		int flag = 0;
		for(int j = 1; j <= n; ++j)	// 对排好序的书进行注意判断 
		{
			if(book[j] % p[len] == user_num) // 如果书编号 % 10^(需求码长度) == 需求码,则找到 
			{
				flag = 1;
				cout << book[j] << endl;
				break;
			}
		}
		if(!flag)	cout << -1 << endl;
	}
	return 0;
}