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的博客查看 举报    64  

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

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;
            }    
    }
}

评论

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

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

接下来我们需要对这个数组进行一个操作,那就是用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;
}

评论

  • Billy●Herrington
    %%%
  • M_sea
    Maybe this is dalao
  • 我叫榨菜
    为什么这么复杂?
  • 王鸿翼
    大佬写得代码看都看不懂
  • 我爸
    哈哈呵呵
作者: Ivystorm 更新时间: 2018-09-15 14:32  在Ta的博客查看 举报    15  

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

这道题我是用树写的。

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

#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;
}

评论

  • 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,没理解透
作者: 白桦树 更新时间: 2017-11-14 19:34  在Ta的博客查看 举报    8  

发一个更简单的解法

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

用时: 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;
} 

评论

  • 弑葉天行
    orz
  • Jr_极影兔
    +1
  • Jr_极影兔
    考试时写了一大堆字符串算法才60,后来用取模之后就AC了。。
  • 李景熙
    看不懂
  • 兰陵王
    我考试时花了一个小时才“AC”
  • Youngore
    great bro
  • 马麒翔
    hhh
  • Rao_ruihan
    NOIP不能用cmath吧
  • Wiaorziy
    %%%%%%%%%%%%%%%%%%%%%
  • Wiaorziy
    %
作者: Aonrbet 更新时间: 2017-12-26 20:08  在Ta的博客查看 举报    9  

这个题的整体思想其实非常简单,用不到什么字符串一类的东西!!!

重要的就是“%”!!!

我们知道,%是有区取余的作用的,而在代码中,我们根据他所输入的所需code的长度,来进行取余,最后进行判断,就是这个题基本上最简单的整体思想!!!

然而在考试时,我没有想到%的取余,这次noip就这样炸掉了TAT

忌2017noipQAQ

不瞎歪歪了!!(´・ω・`)

上代码!!!


#include <iostream>
#include <algorithm>
                  // 求最小的嘛,排序必不可少,考试时为了方便就用其中的sort,就不要自己打排序(你开心的话就自己打吧)
#include <cmath> 
                 // 这个头文件中包含着我们要用到的一个很重要的东西!!!
using namespace std;
int n , p , code , longer , ans[1000000] , codes[1000000] ; //定义,个人习惯定义在外面0.0
int judge(int u, int v){//其中,u相当于下面的longer,v相当于code
    int flag = pow ( 10 , u ) ; // 这个pow就是我们要用的非常重要的东西!!! pow(a,b) 最后的结果为a的b次方 使用它要调用cmath
    // 我们为什么要用%呢?是因为%有取余作用,我们根据他所需图书code的长度,来决定我们%的长度,such as : 1123%100=23
    for ( int  i = 1 ; i <= n ; i ++ ){
        if ( codes[ i ] % flag == v) return codes[ i ] ; //如果取余后相等,则返回codes,在下面的main函数中,我们会对codes进行排序,以保证我们找到的是最小的
    }
    return -1 ; //如果找不到就返回-1!!
}
int main (){
    cin >> n >> p ;//输入...这里就不用解释了吧...
    for (int i = 1 ; i <= n ; i++ ){
        cin >> codes[ i ] ;
    }
    sort( codes + 1 , codes + n + 1) ;//关键的排序
    for (int i = 1 ; i <= p ; i ++){
        cin >> longer >> code ; //longer 和 code 的值每次都会被替换掉,所以不用担心值的重复...
        ans[ i ] = judge( longer , code ) ;//ans用来存放我们在judge函数中所返回的值
    }
    for (int i = 1 ; i <= p ; i ++ ){
        cout << ans [ i ] << endl ;//最后,输出!!
    }
    return 0 ;//完美结束
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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