首页 > 代码库 > HZOI String STL的正确用法

HZOI String STL的正确用法

                                                                  String          3s 512 MB
描述
硬盘中里面有n个文件,文件从1到n标号,每个文件可以用若干个数字序列来表示,而且每个文件存在一个重要值。现在请你完成一个搜索系统,有m
个搜索的操作,如果一个文件中有以这个数字序列为前缀的数字序列,那么这个文件会被搜索到,现在我们想知道会有多少个文件被搜索到,以及这
些文件中重要值前k小的是哪些。
输入
第一行两个数n,m。
接下来n行是对每个文件的描述(标号依次是1到n):
每行的前两个数字分别为描述这个文件的数字序列个数t和文件的重要值v。
接下来有t组数。
每组数先有一个数l,表示这个数字序列的长度。
接下来有l个数,表示这个序列。
接下来m行表示m个搜索操作:
每行的前两个数字分别为搜索数k和前缀长度l。
接下来l个数是这个前缀的数字序列。
输出
共m行。
每行来表示搜索的结果:
首先你需要输出有多少个文件会被搜索到。
接下来你需要输出k个数,依次是重要值前k小的标号(根据重要值由小到大输出,重要值相同时,标号小的排在前面)。
如果搜索到的文件数p比k小,那么你只需要输出p个,如果没有搜索到文件就不用输出了。
样例输入
5 5
1 1 5 1 2 3 4 5
1 2 5 1 2 4 5 3
1 8 5 2 1 4 3 2
1 9 5 2 1 8 5 2
1 1 5 1 2 3 4 5
2 2 1 2
3 2 1 2
4 2 1 2
4 2 2 1
1 2 2 1
样例输出
3 1 5
3 1 5 2
3 1 5 2
2 3 4
2 3
n,m<=50000,插入长度和与询问长度和<=200000


这道题很明显是个trie,但是数那么大不好定义儿子,我们可以在每个文件里建一棵trie但是这样的话总时间为10^10,行不通,那么我们就建一棵全局的trie我们把每个点都在其经过路径上放进去那么只会插入200000个点,而且开出来的trie点也不会超过200000,这样时间复杂度是200000,至于把每个数拆开,出题人说太麻烦......

这样的话我们可以直接把map当儿子,把set当节点储存,对于set,它里面有一个内置的东西是一个结束标志,就是在end()的时候输出的那个,当里面没有元素的的时候begin()就和end()一样了,那其实应该是个标记指针,对于pair要调iostream他有自动的先按第一关键字再按第二关键字的排序性质,而且它可以当做一种变量。

对于动态的trie来说,指针确实不太好打。

#include<set>
#include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define MAXN 200050
using namespace std;
typedef pair<int,int> p;
set<p> s[MAXN];
set<p>::iterator it;
map<int,int>ch[MAXN];
inline int read()
{
    int SUM=0;
    char ch=getchar();
    while(ch<0||ch>9)ch=getchar();
    while(ch>=0&&ch<=9)
    {
        SUM=(SUM<<1)+(SUM<<3)+ch-0;
        ch=getchar();
    }
    return SUM;
}
int n,m,tot=1;
inline void insert(p x)
{
    int l=read();
    int now=1;
    while(l--)
    {
        int y=read();
        if(!ch[now].count(y))ch[now][y]=++tot;
        now=ch[now][y];
        s[now].insert(x);
    }
}
int need[MAXN];
int main()
{
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        int t=read(),v=read();
        for(int j=1;j<=t;j++)
         insert(make_pair(v,i));
    }
    for(int i=1;i<=m;i++)
    {
        int k=read(),l=read(),now=1;
        for(int j=1;j<=l;j++)need[j]=read();
        int j;
        for(j=1;j<=l&&ch[now].count(need[j]);j++)
            now=ch[now][need[j]];
        if(j<=l)now=0;
        printf("%d ",s[now].size());
        if(k>s[now].size())k=s[now].size();
        for(j=1,it=s[now].begin();j<=k;++it,j++)
         printf("%d ",it->second);
        printf("\n");
    }
    return 0;
}

 

HZOI String STL的正确用法