P3955 图书管理员 题解


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

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

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

评论

  • Loveti
    太菜了
作者: YUAN2017  更新时间: 2017-11-18 09:23  在Ta的博客查看 举报    1  

蒟蒻的我第一次发题解,大牛勿喷.......

说实话,普及组第二题太水了 O(∩_∩)O~~~

思路就是暴力找

代码里有解释

上代码:

#include<bits/stdc++.h>
using namespace std;
int p,q;
long long a[10001],b[10001],len[10001],x[10001];
int main()
{
    //freopen("librarian.in","r",stdin);
    //freopen("librarian.out","w",stdout);
    cin>>p>>q;
    for(int i=1;i<=p;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+p+1);//保证找到的图书编号最优 
    for(int i=1;i<=q;i++)
    {
        int flag=0;
        cin>>len[i]>>b[i];//输入 
        long long w=pow(10,len[i]);//w是10的len[i]次方(用于判断图书的后len[i]位) 
        for(int j=1;j<=p;j++)//寻找图书 
        {
            x[j]=a[j]%w;//x[j]是a[j]的末len[i]位 
            if(x[j]==b[i])//若找到 
            {
                cout<<a[j]<<endl;//输出图书编号 
                flag=1;//标记 
                break; //找到就退出 
            }
        }
        if(flag==0)//若找不到 
        {
            cout<<"-1"<<endl;//输出-1 
        }
    }
    return 0;
}

评论

  • 还没有评论
作者: I_promise  更新时间: 2017-11-14 21:35  在Ta的博客查看 举报    1  

(本题解按洛谷数据AC)

没有pascal的题解

我来发一波

考场里10分钟做完

然后第三题打码2个多小时,结果50。。。心塞

思路很简单

将书码快排

每个人的需求码读入后,寻找合适的书

如果找到,直接输出

这里用了字符串处理,下面有不用字符串的思路,自行阅读

下面是简(fan)单(suo)的代码(考场代码):

···pascal

var a:array[0..1001] of longint;
    n,q,i,j,m,k:longint;
    s1,s2:string; f:boolean;
procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
begin
  //assign(input,'librarian.in'); reset(input);
  //assign(output,'librarian.out'); rewrite(output);//考场必备哦
  read(n,q);
  for i:=1 to n do read(a[i]);//读入书码
  sort(1,n);//快排,记得从小到大哦
  for i:=1 to q do
  begin
    read(m,k); //一个一个读入需求码
    f:=true;
    for j:=1 to n do
    if k<=a[j] then//寻找可用的书
    begin
      str(k,s1);//需求码为s1
      str(a[j],s2);//书码为s2
      s2:=copy(s2,length(s2)-m+1,m);//截取书码末尾
      if s1=s2 then//比较
      begin
        writeln(a[j]);//可行直接输出
        f:=false;
        break;//节约时间,退出循环(不过这道题目不需要节约时间)
      end;
    end;
    if f then writeln(-1);//不可行输出-1
  end;
  //close(input); close(output);//考场必备哦
end.
···

评论

  • 还没有评论
作者: 侦探鼠 更新时间: 2019-10-13 18:07  在Ta的博客查看 举报    0  

题解 P3955 【图书管理员】(论图书管理员有多懒)


Some ideas

首先,读入并存入数组,排列。取余查找*,有就输出**,无输出-1
* 用循坏!千万别用pow函数。虽然洛谷上pow能过,但一个系统一个数据。别的网站由于实数整数原因,过不了!!!
**因为先前已经排列,所以没必要再去找。一来浪费时间,二来不会输出最小的

$\color{white}\colorbox{white}{\text{第三篇题解,管理大大求过!!!}}$

Code

#include<bits/stdc++.h>
using namespace std;
int n,q,ans,noww;
int a[1005],b[1005],c[1005];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);//读并存入
    sort(a+1,a+n+1);//排它!!!
    for(int i=1;i<=q;i++)
        scanf("%d%d",&b[i],&c[i]);//读入
    for(int i=1;i<=q;i++)
    {
         ans=-1;noww=1;//重新定义,避免之前的影响这一次运算
         //while(b[i]--)noww*=10;
         while(c[i]>=noww)noww*=10;/*两种循坏方式*/
         for(int j=1;j<=n;j++)    
           if(a[j]%noww==c[i])//取余判断
           {
            ans=a[j];           
            break;
           }  
           printf("%d\n",ans);//输出
    }
    return 0;
}

最后过了

评论

  • lyj080620112358
    不会用using namespace std;吗
  • Warer_______
    气势磅礴[doge]
作者: 聪明的猪 更新时间: 2019-09-22 11:46  在Ta的博客查看 举报    0  

蒟蒻题解,dalao轻喷

整体思路

其实这道题还算比较简单(去你的),我们将其全部输入之后再一个一个处理,对比编码和需求码后将最小的分别对应地储存,时间复杂度大概为 $ \mathcal{O}\left( n^2 \right) $ 吧主要是我太蒻了

核心代码详解

气势磅礴的头文件。

#include <algorithm> // std::min
#include <array> // std::array
#include <cmath> // std::pow
#include <iostream> // std::cin,std::cout,std::endl
#include <limits> // std::numeric_limits
#include <memory> // std::shared_ptr

用来储存需求码的结构体。

struct request
{
    bool flag; // 标记是否找到了对应的图书编码
    int len; // 需求码长度
    long code, min; // 需求码和当前对应最小的图书编码
};

来一波数组。

std::array<long, 1010> bookCode; // 图书编码
std::array<std::shared_ptr<request>, 1010> requestCode; // 需求码

以下缩进皆为main函数内。

气势磅礴的初始化。

    for (std::array<std::shared_ptr<request>, 1010>::iterator iter = requestCode.begin(); iter != requestCode.end(); iter++) // 使用了迭代器,其实没有什么卵用
    {
        *iter = std::make_shared<request>();
        (*iter)->len = 0;
        (*iter)->code = 0;
        (*iter)->min = (std::numeric_limits<long>::max)() - 1; // 将min设置为long的最大值
        (*iter)->flag = false;
    }

气势磅礴的输入。

    std::cin >> n >> q;
    for (std::array<long, 1010>::iterator iter = bookCode.begin(); iter != bookCode.begin() + n; iter++) // 然并卵
    {
        std::cin >> *iter;
    }
    for (std::array<std::shared_ptr<request>, 1010>::iterator iter = requestCode.begin(); iter != requestCode.begin() + q; iter++) // 然并卵
    {
        std::cin >> (*iter)->len >> (*iter)->code;
    }

真正的核心代码。

    for (int i = 0; i < q; i++) // 需求码循环
    {
        for (int j = 0; j < n; j++) // 图书编码循环
        {
            if (bookCode.at(j) % static_cast<long>(std::pow(10, requestCode.at(i)->len)) == requestCode.at(i)->code) // 判断是否是需要的图书
            {
                requestCode.at(i)->min = std::min(bookCode.at(j), requestCode.at(i)->min); // 选最小
                requestCode.at(i)->flag = true; // 设为已有编码了
            }
        }
    }

整体代码

拒绝抄袭,共创和谐洛谷

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <limits>
#include <memory>
struct request
{
    bool flag;
    int len;
    long code, min;
};
std::array<long, 1010> bookCode;
std::array<std::shared_ptr<request>, 1010> requestCode;
int main(void)
{
    int n = 0, q = 0;
    bookCode.fill(0);
    for (std::array<std::shared_ptr<request>, 1010>::iterator iter = requestCode.begin(); iter != requestCode.end(); iter++)
    {
        *iter = std::make_shared<request>();
        (*iter)->len = 0;
        (*iter)->code = 0;
        (*iter)->min = (std::numeric_limits<long>::max)() - 1;
        (*iter)->flag = false;
    }
    std::cin >> n >> q;
    for (std::array<long, 1010>::iterator iter = bookCode.begin(); iter != bookCode.begin() + n; iter++)
    {
        std::cin >> *iter;
    }
    for (std::array<std::shared_ptr<request>, 1010>::iterator iter = requestCode.begin(); iter != requestCode.begin() + q; iter++)
    {
        std::cin >> (*iter)->len >> (*iter)->code;
    }
    for (int i = 0; i < q; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (bookCode.at(j) % static_cast<long>(std::pow(10, requestCode.at(i)->len)) == requestCode.at(i)->code)
            {
                requestCode.at(i)->min = std::min(bookCode.at(j), requestCode.at(i)->min);
                requestCode.at(i)->flag = true;
            }
        }
    }
    for (int i = 0; i < q; i++)
    {
        if (!(requestCode.at(i)->flag))
        {
            std::cout << -1 << std::endl;
        }
        else
        {
            std::cout << requestCode.at(i)->min << std::endl;
        }
    }
    return 0;
}

A了这道题,祝你们成功

评论

  • 还没有评论
作者: optmize_2  更新时间: 2019-09-20 21:33  在Ta的博客查看 举报    0  

此题可以用字典树写

字典树顾名思义,是一棵树.

你可以在里面插入字符串和询问某串是否被入(这道题是插入数字,而且有些操作不太一样)当它里面什么也没有的时候长这样:

blob

像什么

除根节点外,每个节点都代表一个数字,从根节点到树上某点走过的最短路径就是一个字符串.

让我们来看看插入114514之后会发生什么:

blob

但是------

这里有一个问题:

如果插入114514,查询114514返回的值自然是true(这里不考虑最小值),但查询514的时候似乎也会返回true...

所以,当插入一个数的时候,要在插入完的地方做个标记,查询时,如果结束为止有一个标记,返回true,否则返回false.

就像这样:

blob

现在我们再插入6749与1949.

blob

可以发现,如果这些数字的前缀重复大,那么存储占的空间就会非常少.

现在我们考虑如何实现代码:

字典树节点定义:

struct trie{
    int id,son[10];  //当前节点编号与10个子节点编号
    bool use[10]; //子节点是否被插入过
    bool wd; //这是否是个单词(如图中的1,6,1节点wd的值就是true)
}t[10010];  //也可以用vector<trie>t;

但是本题似乎要求最小值233333... 那就加个变量mn呗:

struct trie{
    int id,son[10];
    bool use[10];
    bool wd;
    int mn;
    tries()
    {
        mn=2147483647;  //一定要初始化
    }
}t[10010];

对应地,我们可以得到字典树的插入:

void ins(int now,int key,int tmp)
{
    t[now].mn=min(t[now].mn,tmp);  //插入时记得维护最小值 
    if(key==0)  //插入完毕 
    {
        t[now].wd=true;  //标记这里是个完整的图书编号 
        return;
    }

    if(t[now].use[key%10]) ins(t[now].son[key%10],key/10,tmp);  //%取后缀,/去后缀 
    else{
        t[now].use[key%10]=true;  //儿子节点被使用 
        t[now].id=++nowid;  //儿子节点被使用 
        t[now].son[key%10]=++nowid;  //儿子节点被使用 
        ins(t[now].son[key%10],key/10,tmp);  //插入儿子节点 
    }
}

还有查询:

int ask(int now,int key,int tmp)
{
    if(key==0)  //查询结束 
    {
        return t[now].mn;  //返回最小值 
    }

    if(t[now].use[key%10]) return (ask(t[now].son[key%10],key/10,tmp));  //查询儿子节点 
    else{
        return -1;  //t[now].use[key%10]如果等于false代表该儿子节点根本不存在,当然返回-1啦 
    }
}

下面是代码:

#include<bits/stdc++.h>
using namespace std;

struct trie{
    int id,son[10];
    bool use[10];
    bool wd;
    int mn;
    tries()
    {
        mn=2147483647;  //一定要初始化
    }
}t[10010];

int nowid=1;  //当前节点数 
int n,q,len;  //n,q如题,len没什么用 

int num;  //插入和查询的输入 

void ins(int now,int key,int tmp)
{
    t[now].mn=min(t[now].mn,tmp);  //插入时记得维护最小值 
    if(key==0)  //插入完毕 
    {
        t[now].wd=true;  //标记这里是个完整的图书编号 
        return;
    }

    if(t[now].use[key%10]) ins(t[now].son[key%10],key/10,tmp);  //%取后缀,/去后缀 
    else{
        t[now].use[key%10]=true;  //儿子节点被使用 
        t[now].id=++nowid;  //儿子节点被使用 
        t[now].son[key%10]=++nowid;  //儿子节点被使用 
        ins(t[now].son[key%10],key/10,tmp);  //插入儿子节点 
    }
}

int ask(int now,int key,int tmp)
{
    if(key==0)  //查询结束 
    {
        return t[now].mn;  //返回最小值 
    }

    if(t[now].use[key%10]) return (ask(t[now].son[key%10],key/10,tmp));  //查询儿子节点 
    else{
        return -1;  //t[now].use[key%10]如果等于false代表该儿子节点根本不存在,当然返回-1啦 
    }
}

int main()
{
    t[1].id=1;  //t[1]是根,里面什么都没有 
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>num;
        ins(1,num,num);  //插入num 
    }
    for(int i=1;i<=q;i++)
    {
        cin>>len>>num;  //不用管len 
        cout<<ask(1,num,num)<<endl;  //查询num 
    }
    return 0;
}

注:本题使用的trie并不是标准的字典树,而是变了形的(存放最小值,插入数字)

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



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