题解：P3955 [NOIP2017 普及组] 图书管理员

别人内卷我在躺平 · 2025-01-05 21:01:16 · 题解

本题算法为：贪心，取模运算，模拟。

本题解法：

• 首先我们要知道，x 除以 10^n 的余数可以得到的是这个数 x 的后 n 位。
• 根据上面这个特性，我们可以先将书的编号从小到大排序，然后每次算出 10^x，再枚举书的编号，如果找到就直接赋值并退出，否则输出 -1。
• 再枚举前可以将答案 ans 设为 -1，这样有一个好处：如果没有找到答案就可以直接输出 -1，不需要特判，比较方便。
  代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int book[maxn];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>book[i];
    sort(book+1,book+1+n);//因为要找编号较小的，所以从小到大排序
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        int tmp=pow(10,x);//取10^x,取模时会用到
        int ans=-1;//先设为-1,方便处理
        for(int i=1;i<=n;i++)
        {
            if(book[i]%tmp==y)//如果取模后是编号y
            {
                ans=book[i];//直接赋值答案并退出。
                break;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}