洛谷 P3955 图书管理员题解

每日一题 day12 打卡

Analysis

模拟+快速幂

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

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 1000+10
 6 using namespace std;
 7 inline int read() 
 8 {
 9     int x=0;
10     bool f=1;
11     char c=getchar();
12     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
13     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
14     if(f) return x;
15     return 0-x;
16 }
17 inline void write(int x)
18 {
19     if(x<0){putchar('-');x=-x;}
20     if(x>9)write(x/10);
21     putchar(x%10+'0');
22 }
23 int n,q;
24 int num[maxn];
25 inline int ksm(int x,int y)
26 {
27     int res=1;
28     while(y>0)
29     {
30         if(y&1)
31             res*=x;
32         x*=x;
33         y>>=1;
34     }
35     return res;
36 }
37 int main()
38 {
39     n=read();q=read();
40     for(int i=1;i<=n;i++) num[i]=read();
41     sort(num+1,num+n+1);
42     for(int i=1;i<=q;i++)
43     {
44         int len=read(),req=read(),ans=-1;
45         for(int j=1;j<=n;j++)
46             if(num[j]%ksm(10,len)==req)
47             {
48                 ans=num[j];
49                 break;
50             } 
51         write(ans);
52         printf("
");
53     }
54     return 0;
55 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

洛谷 P3955 图书管理员 题解

Analysis

洛谷 P3955 图书管理员题解