首页技术正文

洛谷 P3955 图书管理员题解

程序员智慧技术 2022年11月14日

0 收藏 959 点赞 3,509 浏览 864 个字

每日一题 day12 打卡

Analysis

模拟+快速幂

先把图书的编码存起来排序，保证第一个找到的就是最小的。如果要求一个数后x位，就将这个数模10的x次方，同理，我们可以通过这个规律来判断后缀。每个编码和需求码都不超过10000000，所以x<8。为了保险，我使用了快速幂来求10的x次方。

时间复杂度 O ( n*q*log (8) ) < O(1000000) 可以接受

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #define maxn 1000+10
 using namespace std;
 inline int read()
 {
     int x=;
     bool f=;
     char c=getchar();
     for(; !isdigit(c); c=getchar()) if(c=='-') f=;
     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
     if(f) return x;
     return -x;
 }
 inline void write(int x)
 {
     if(x<){putchar('-');x=-x;}
     if(x>)write(x/);
     putchar(x%+'');
 }
 int n,q;
 int num[maxn];
 inline int ksm(int x,int y)
 {
     int res=;
     while(y>)
     {
         if(y&)
             res*=x;
         x*=x;
         y>>=;
     }
     return res;
 }
 int main()
 {
     n=read();q=read();
     for(int i=;i<=n;i++) num[i]=read();
     sort(num+,num+n+);
     for(int i=;i<=q;i++)
     {
         int len=read(),req=read(),ans=-;
         for(int j=;j<=n;j++)
             if(num[j]%ksm(,len)==req)
             {
                 ans=num[j];
                 break;
             }
         write(ans);
         printf("\n");
     }
     return ;
 }