P3955 图书管理员 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • Michaelwrl
    对我很有帮助!谢谢!
  • Focus_on
    要是以后NOIP取消了库函数的使用怎么办?
  • expect
    楼上害怕的事是tan 90的,14年刚开放。。。
  • Michaelwrl
    @y_z_h 不大可能吧,最多不能用万能头,STL肯定可以的呀
  • 弑葉天行
    return 0?
  • feicx
    以前不能用STL,从14年开始才加的~~~
  • 黎枔龙
    。return是可有可无的
  • 兰陵王
    我反正参加了NOIP2017
  • 兰陵王
    我也是一等奖
  • Sparky_14145
    return 可有可无。。。。。
作者: Michaelwu 更新时间: 2017-11-11 20:47  在Ta的博客查看 举报    97  

这题其实真的不难,就是特别水,纯模拟就可以了。

10分钟还原了比赛时一小时啃出来的题(我太弱了)不过亲测AC。

#include <iostream>
#include <cstdio>
#include <algorithm>//各种常见函数的算法库,比如sort,max,min等
using namespace std;
const int S=1005;
long long b[S],x[S],tmp[S],xc[S]; //x:需求码,xc:x的长度,b:书的编码,tmp后面会用
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);//偷懒,使用STL库排序,+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]){//这里if判断很核心:b[j]%tmp[i]表示取此编码的末xc位
                cout<<b[j]<<endl;
                break;
            }
            else if (j==n){
                cout<<"-1"<<endl;
                break;
            }    
    }
}

评论

  • 12qwaszxcvdfer34
    真香
  • 老李
    6666tql
  • 12345小草
    没学过的出门左转回娘胎重造 额
  • 12345小草
    不错
  • cfjm
  • davidma2007
  • 王江睿
    变输入遍输出,呵呵
  • 王江睿
    原来可以这样!!!!!!!!!
  • 159357qwer
    我顶
  • 饺子龙
    简洁明了! QWQ
作者: lcb9021  更新时间: 2018-11-01 17:10  在Ta的博客查看 举报    72  

(重要的事情说三遍:大佬别看,大佬别看,大佬别看)

不管怎么说,这就是一道模拟

本题主要的难点,就是将读者的需求码与图书编码配对,一旦会配对了,找最小数什么的都是浮云。

把需求码与图书编码配对 = 求图书编码的后 X 位

求图书编码的后 X 位 = 把前面的都去掉。

如何把前面的无关数字去掉呢?这时候我们想起了 % 运算(没学过的出门左转回娘胎重造)。

对于一个数$a$,很显然要取它个位数的方法就是:

对$a$ mod 10

但是这是我们人工计算出的结果,而各个需求码的位数不同,这时候就需要找出一个规律。

对此我们发现了规律:对一个数$a$取其后$n$位,就是对$a$ mod 10^$n$

然后你就会发现题目给的这个位数是真·仁慈 啊。

而cmath函数中带有专门执行幂运算的函数

pow

其中有一个要注意的点是,pow函数并不能直接进行 mod 运算,需要将其带入一个变量进行运算。

主要的思路就讲到这里了,另外特别为蒟蒻讲一下如何求最小数。

if(a[i] < min) min = a[i];

当然前提是要给$min$赋一个很大的值(如666666666)。

最后贴代码

#include<iostream>
#include<cmath>
using namespace std;
int n,q,book[6666],len[6666],num[6666];

int main()
{
    cin>>n>>q;
    for(int i=1; i<=n; i++) cin>>book[i];
    for(int i=1; i<=q; i++) {
        cin>>len[i]>>num[i];
        int tmp = pow(10,len[i]),min = 10000001;
        for(int j=1; j<=n; j++) if(book[j] % tmp == num[i] && book[j] < min) min = book[j];
        if(min != 10000001) cout<<min<<endl;
        else cout<<-1<<endl; 
    }
    return 0;
}

把我顶上去啊!

评论

  • 李景熙
  • chengni
    你的n定义重了
  • 墨末
    给大佬递茶
  • 溟江二十三
    没有用递归取末位的?
  • 溟江二十三
    这样简洁
  • Happynewyear
    好简洁啊!!!
  • Happynewyear
    简洁!!!
  • Happynewyear
    简洁
  • 李博睿
    666
  • cjh070529
    20分
作者: 兮兮相印 更新时间: 2017-12-16 18:05  在Ta的博客查看 举报    49  

这一题,我们首先将书的编号全部读入,存在一个数组里。

接下来我们需要对这个数组进行一个操作,那就是用sort排序,因为题目中说要求符合条件的编号最小的一本书,这样的话,排完序,操作会更方便,在后面就能体现。

排完序,我们采取在线处理,因为如果把需求全部读入后,再做,纯属浪费空间。所以我们边读边做。

那么接下来我们要做的就是把需求编号和书的末尾几个数字进行对比,首先排除用字符去处理的思想,太麻烦了,所以我们采用对数字取模的办法,来处理,也就是说我们如果要取书的编号的后l位,我们只需要将该书的编号对10^l取模即可。

但是如果每次都计算未免显得有些麻烦,所以我们可以用一个m数组去处理,这样就可以了,具体怎么用见代码。

最后,还有一个小技巧,就是说,存在找不到的情况,要输出-1,所以为了避免额外的判断,我们可以将a的初始值设置为-1,这样不用判断直接输出即可。

还有注意找到符合条件的就记录为a,然后break,因为我们只要最小的,这就可见当初排序的方便之处。

下面给代码:

#include<bits/stdc++.h>
using namespace std;
int m[8]={1,10,100,1000,10000,100000,1000000,10000000};//传说中的m数组,需要多长的,直接带入下标即可。
int n,q;
int b[1005];//记录图书
int main(){
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);
    }
    sort(b,b+n);//排序
    while(q--){
        int l,n;
        scanf("%d%d",&l,&n);
        int a=-1;      //初始值设置为-1
        for(int i=0;i<n;i++){
            int g=b[i]%m[l];  //直接带入对应的截取长度,这就是m的好处
            if(g==n){
                a=b[i];
                break;         //注意break
            }
        }
        printf("%d\n",a);
    }
    return 0;
}

评论

  • Steven_Meng
    YPY loves DYF!!!
  • chenhaiquan
    mod[6]和mod[7]重复
  • dreampossible
    给大佬递茶
  • Loi_magic
    我觉得这个sort是不对的,明明是从下标1开始存的数据,但却是从0开始sort,显然可以ac纯属数据太水
  • Loi_magic
    应该是sort(a+1,a+n+1)才对啊
  • misaka_八重樱
    楼上的,a+n+1和a+1+n有什么区别,况且人家代码的起始地址a+1也不是从0开始的啊
  • _lyk
    %%%%%%
  • zhangke1
    太巨
  • 余杭哲
    前面sort不对滴别跑,人家数组从1开始,而sort第一位是起点下标,a就表示了最小下标(即0),而a+1不就是1嘛。。。一看就是刚学sort,没理解透
  • 大神无敌222
    思路好 Orz
作者: 白桦树 更新时间: 2017-11-14 19:34  在Ta的博客查看 举报    20  

发一个更简单的解法

看到题解有些复杂了,其实可以不用字符串处理,不用取模求每一位

用时: 0ms / 内存: 2164KB

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 1005
using namespace std;
int n,q,l,code;//l为需求码长度,code为需求码
int a[maxn];//存储图书馆编号
int mod[9]={0,10,100,1000,10000,100000,1000000,10000000,100000000};//方便取模,mod[i]表示一个数取后i位要模多少
int judge(){//函数,返回找到的编号
    for(int i=1;i<=n;i++){
        if(a[i]%mod[l]==code) return a[i];//如果第i个图书编码的后l位正好等于code,那么就找到了对应的数
    }
    return -1;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);//STL快排,从小到大排序,确保找到的是最小的数
    for(int i=1;i<=q;i++){
        cin>>l>>code;
        cout<<judge()<<endl;
    }
    return 0;
} 

评论

  • Billy●Herrington
    %%%
  • M_sea
    Maybe this is dalao
  • 我叫榨菜
    为什么这么复杂?
  • 王鸿翼
    大佬写得代码看都看不懂
  • 我爸
    哈哈呵呵
  • tgs9311
    trie?
  • james666
    写下你的评论
  • 黑掉Farmer_John
    写下你的评论...
  • panzhicun
    看不懂啊?有这么复杂吗!
  • Harrington
    大佬
作者: Ivystorm 更新时间: 2018-09-15 14:32  在Ta的博客查看 举报    24  

看下面的人都是字符串啊,模拟啊,真是不给数据结构留点后路。

这道题我是用树写的。

把编码每一位反向插入树中,查找时编码反向查询就行了。

#include <iostream>
#include <cstdio>
using namespace std;
struct xtree{//建树
       xtree *sons[20];//下一位数字
       int cou;
       int nums;//最小的编码
};
xtree *neww(){//新建一个新节点
      xtree *p=new xtree;
      p->cou=0;
      for(int i=0;i<10;i++)
         p->sons[i]=NULL;
      return p;
}
void hui(xtree *now,int num,int xsxs){//递归插入书籍信息
     if(num==0){//最底层
       now->cou++;
       if(now->nums!=0)
         now->nums=min(now->nums,xsxs);
       else
         now->nums=xsxs;
       return;
     }
     //否则继续递归
     if(now->sons[num%10]==NULL)
       now->sons[num%10]=neww();
     hui(now->sons[num%10],num/10,xsxs);
     if(now->nums!=0)
       now->nums=min(now->nums,xsxs);
     else
       now->nums=xsxs;
}
int aq(xtree *now,int num){//询问
    if(now==NULL)
      return -1;
    if(num!=0)
      return aq(now->sons[num%10],num/10);
    return now->nums;
}
int main(){
    xtree *root=neww();//根节点
    int n,q,junk;
    cin>>n>>q;
    for(int i=0;i<n;i++){
       scanf("%d",&junk);
       hui(root,junk,junk);//插入
    }
    for(int i=0;i<q;i++){
       int wei;
       scanf("%d%d",&wei,&junk);
       printf("%d\n",aq(root,junk));//寻找
    }
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。