P3955 图书管理员 题解


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

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

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

评论

  • 弑葉天行
    orz
  • Jrzy
    +1
  • Jrzy
    考试时写了一大堆字符串算法才60,后来用取模之后就AC了。。
  • 李景熙
    看不懂
  • 兰陵王
    我考试时花了一个小时才“AC”
  • 行政执法
    great bro
  • _巴扎黑_
    hhh
  • Rao_rh
    NOIP不能用cmath吧
  • Wiaorziy
    %%%%%%%%%%%%%%%%%%%%%
  • Wiaorziy
    %
作者: Vanyun 更新时间: 2017-12-26 20:08  在Ta的博客查看 举报    10  

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

重要的就是“%”!!!

我们知道,%是有区取余的作用的,而在代码中,我们根据他所输入的所需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 ;//完美结束
}

评论

  • 小雅涵
    %%%
  • 小雅涵
    大佬orz
作者: KillerXu  更新时间: 2017-11-12 17:12  在Ta的博客查看 举报    5  

对于第一次参加NOIp的蒟蒻来说,看到普及组前两题都笑了,看来题目放水了。

但是,在我考完以后,发现很多人被水淹死了,我就准备发一篇题解,告诉大家凡事不要想的太复杂(例如提高组第一题)

首先要分析数据范围,不是特别大,说明是一道模拟题

再看,编号范围不会超过一千万,##所以不用字符串。

接下来,我们要去比较读者的需求码和图书编码的末尾,既然输入了编码长度,那么显然应该用 图书编码 mod 10^编码长度 与需求码比较,我们可以定义变量min来存储最小编码。

最后如果min还是初值,输出-1,否则输出min

愉快的AC了

#include<stdio.h>
int num[1001];
int main()
{
    int n,q,xq1,xq2,i,m;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++) scanf("%d",&num[i]);//读入图书编码
    int mod,min;//mod用来计算应取余多少
    for(m=1;m<=q;m++)
    {
        mod=1; min=10000000;//赋初值
        scanf("%d%d",&xq1,&xq2);//读入需求码长度和需求码
        for(i=1;i<=xq1;i++) mod*=10;//计算取余值
        for(i=1;i<=n;i++)
        {
            if(num[i]%mod==xq2&&num[i]<min) min=num[i];//如果图书码末尾和需求码一样,且编码比当前最小的编码小,刷新min
        }
        if(min==10000000) printf("-1\n"); else printf("%d\n",min);//判断输出
    }
    return 0;
}//其实就是这么简单,分析好题目就会找到合适的方法

评论

  • _lyc233
    还没有评论
  • HJY0611
    dalao
  • Spect_Scan
    No comments yet...
作者: sbcxknmsl 更新时间: 2017-11-18 20:53  在Ta的博客查看 举报    4  

我不会告诉你我没过普及组初赛

看到这道题总体思路就是:先排序,确保序号较小的在前,然后双重循环,将书的号码和用户要找的号码比较就行了。

然而实际做的时候遇到了很多问题:我用字符串比较书的号码和用户要找的号码,佷麻烦,排序还要使用操作符重载,还要struct……

具体注释见代码

#include<bits/stdc++.h>
using namespace std;
struct str
{
    string s;
    bool operator < (const str&t)const//操作符重载,防止排序时出问题
    {
        if(s!=t.s)
        {
            if(s.length()<t.s.length())return true;
            else if(s.length()>t.s.length())return false;
            else return s<t.s;
        }
    }
};
str num[1005];//书的号码
str nu[1005];//用户要找的号码
int main()
{
    int a,i,j,k,n,m,b;
    cin>>n>>m;
    for(i=0;i<n;++i)
    {
        cin>>num[i].s;
    } 
    for(i=0;i<m;++i)
    {
        cin>>a>>nu[i].s;
    }
    sort(num,num+n);
    for(i=0;i<m;++i)
    {    
        bool t=false;
        a=nu[i].s.length();
        for(j=0;j<n;++j)
        {
            t=false;//注意!要初始化
            b=num[j].s.length();
            for(k=0;k<=a;++k)
                if(nu[i].s[k]!=num[j].s[b-a+k])//比较
                    t=true;
            if(!t)
            {
                cout<<num[j].s<<endl;//输出
                break;
            }
        }
        if(!t)
            continue;//找到后做下一个
        else
            cout<<-1<<endl;//没找到后输出
    }
} 

写完后提交,我过了,然后某神犇跑过来跟我说:你用string比较很慢的,要用int比较

使用书的号码减掉要找到号码,如果结尾都是0,就说明它们的结尾相同!!!!!!!!!!重要思路!!!!!

于是我又写了一个

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,i,j,k,n,m,num[1005],cou[1005],number[1005];//num:书的号码  cou:要找的号码  //number:要找号码的位数
    cin>>a>>b;
    for(i=0;i<a;++i)cin>>num[i];
    for(i=0;i<b;++i)cin>>number[i]>>cou[i];
    sort(num,num+a);//排序
    for(i=0;i<b;++i)
    {
        bool t=false;
        m=10;
        for(k=1;k<number[i];++k)
            m*=10;         //位数
        for(j=0;j<a;++j)
        {
            n=num[j]-cou[i];
            if((n%m)==0)//比较
            {
                t=true;
                break;
            }
        }
        if(t)
            cout<<num[j]<<endl;//输出
        else
            cout<<-1<<endl;
    }
    return 0;
}
0ms!!!

评论

  • windflower
    6666666 ]
  • 重力做功
    大佬
  • 纪律部部长
    这方法,怎么想的?牛逼啊!
  • shujunfengjun
    厉害了,我的哥
  • shujunfengjun
    棒棒的
  • shujunfengjun
作者: windflower 更新时间: 2017-11-19 06:32  在Ta的博客查看 举报    3  

看了下之前Pascal的题解

好像用整型读入的都是用逐位比较的

那我就来发一个比较机智的比较方法

var
  i,j,k,n,m,s:longint;
  a,b:array[1..23333]of longint;//数据范围个人习惯,,,
begin
  b[1]:=10;
  for i:=2 to 7 do
    b[i]:=b[i-1]*10;//预处理
  readln(n,m);
  for i:=1 to n do
    readln(a[i]);//读入不解释
  for i:=1 to  n-1 do
    for j:=i+1 to n do
      if a[i]>a[j] then
        begin
          s:=a[i];
          a[i]:=a[j];
          a[j]:=s;
        end;//排序不解释
  for i:=1 to m do
    begin
      readln(k,s);
      for j:=1 to  n do
        if (a[j]>=s) and ((a[j]-s) mod b[k]=0) then//如果a[j]结尾是s的话,那么减去s后肯定是个整十整百整千······的数,那么再mod=0判断一下就行了
          begin
            writeln(a[j]);//输出
            k:=-1;
            break;
          end;
        if k<>-1 then writeln(-1);//输出
    end;
end.//结束

评论

  • 违规用户名RtDPj^93
    沙发
  • 扇贝sann
    暴力不能救中国人,但是他就得了oier
作者: 征途者二号 更新时间: 2019-10-27 21:27  在Ta的博客查看 举报    2  

好吧,这一道题从本质上看,就是一道纯暴力模拟,但是暴力不能救中国人

一切的起源,都是起源于计算机超快超强的特性,自然而然出现了这一用海量的计算来解题的思路——暴力。你废话这么多干啥

我简单讲一下我做这道题的思路:

1.把图书馆的数据导入到图书管理员的大脑内(这很ke幻)

3.排个序,以达到题目要求(这样找到就可以直接退出查找了)

2.边读边做,防止出现烦人的超时

4.找一下(用一个叫search函数),并将结果输出

5.结束

接下来我讲一下这个search的自定义函数:

1.从头开始找

·其实可以用STL的lower_bound找到第一个大于等于10^(x-1)的数在a数组中的对应下标,但是由于我在敲代码后这个STL老跟我过不去,所以只能从头找了

2.把要比较的这个a[i]转换成string类型的s2

·接下来介绍一个简单的从int类型转换成string类型的函数:to_string,格式就是这样:
        string s1=to_string(a[i]);//例子
3.这下就可以一位一位地比较了,然后结束

好了我废话说得够多了,上代码吧

#include <bits/stdc++.h>
#define maxn 1100
using namespace std;
int a[maxn],n,m,x;
string s;
int search()
{
    for (int i=1;i<=n;i++)
    {
        string s1=to_string(a[i]);
        bool bl=true;//初始化一个辅助判定变量和完成把int的a[i]转为string类型的s2 
        if (s1.size()<s.size()) continue;//如果图书馆编码的位数比 需求码还短,就可以跳过了 
        for (int k=1;k<=s.size();k++)//一个位一个位地比较 
        if (s1[s1.size()-k]!=s[s.size()-k]) //如果对应位不等,就不是 
        {
            bl=false;break;//标记一下,就不用再找下去了 
        }
       // cout<<"CASE:"<<s<<" result:"<<bl<<"  AIM:  "<<s1<<endl;
        if (bl) return a[i];//如果是答案,就返回答案值 
    }
    return -1;//没找到?那就-1 
}
int main()
{
    cin>>n>>m;//读入 
    for (int i=1;i<=n;i++)
    cin>>a[i];//读入图书馆编码 
    sort(a+1,a+n+1);//排序(原因?回去看看题目) 
    for (int i=1;i<=m;i++)
    {
        cin>>x>>s;
        cout<<search()<<endl;//边读边做 
    }
    return 0;//结束 
}

然后喜滋滋地拿到DEV_C++上一试:编译失败

为什么?

看一看错误提示,你就会发现是to_string出的问题。

因为to_string是C++11的函数,所以会报错

好了,这下就很简单了:把程序拿到洛谷上,选定C++11,我就成功地一次A掉了。

看在我这么辛苦打了一篇题解之后,麻烦给一点宝贵建议吧,毕竟我还是个蒟蒻

 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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