题解 P3955 【图书管理员】

看下面的人都是字符串啊，模拟啊，真是不给数据结构留点后路。 这道题我是用树写的。 把编码每一位反向插入树中，查找时编码反向查询就行了。 ```cpp #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; } ```