String STL set map Trie - NekoMio's Blog

描述#

硬盘中里面有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

数据范围和约定#

对于20%的数据
0<n,m<=50
每次询问k无限制
0<重要值<=10^9
0<数字序列中的数字<=10
所有文件数字序列长度之和<=500
所有询问前缀数字序列长度之和<=500
对于另外20%的数据
0<n,m<=50
每次询问k无限制
0<重要值<=10^9
0<数字序列中的数字<=10^9
所有文件数字序列长度之和<=500
所有询问前缀数字序列长度之和<=500
对于另外20%的数据
0<n,m<=510^4
每次询问k=1或k=2
0<重要值<=10^9
0<数字序列中的数字<=10
所有文件数字序列长度之和<=210^5
所有询问前缀数字序列长度之和<=2*10^5
对于剩下的数据
0<n,m<=510^4
每次询问k无限制
0<重要值<=10^9
0<数字序列中的数字<=10^9
所有文件数字序列长度之和<=210^5
所有询问前缀数字序列长度之和<=2*10^5

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <vector>
5
#include <map>
6
#include <set>
7
#include <ctime>
8
using namespace std;
9
vector<int> l;
10
struct Improtant
11
{
12
    int i, Imp;
13
    bool operator<(const Improtant &a) const
14
    {
15
        return Imp == a.Imp ? i < a.i : Imp < a.Imp;
16
    }
17
} number[50005];
18
struct Trie
19
{
20
    map<int, Trie *> mp;
21
    set<Improtant> mark;
22
} * root;
23
void insert(int x)
24
{
25
    Trie *rt = root;
26
    rt->mark.insert(number[x]);
27
    for (int i = 0; i < l.size(); i++)
28
    {
29
        if (!rt->mp[l[i]])
30
            rt->mp[l[i]] = new Trie;
31
        rt = rt->mp[l[i]];
32
        rt->mark.insert(number[x]);
33
    }
34
}
35
void Query(int k)
36
{
37
    Trie *rt = root;
38
    for (int i = 0; i < l.size(); i++)
39
    {
40
        if (rt->mp[l[i]] == NULL)
41
        {
42
            printf("0\n");
43
            return;
44
        }
45
        rt = rt->mp[l[i]];
46
    }
47
    set<Improtant>::iterator it = rt->mark.begin();
48
    printf("%d ", rt->mark.size());
49
    for (int i = 1; i <= k && it != rt->mark.end(); i++, it++)
50
    {
51
        printf("%d ", it->i);
52
    }
53
    printf("\n");
54
    return;
55
}
56
int main()
57
{
58
#ifdef Mine
59
    freopen("1.in", "r", stdin);
60
#else
61
    freopen("string.in", "r", stdin);
62
#endif
63
    freopen("string.out", "w", stdout);
64
    int n, m;
65
    root = new Trie;
66
    scanf("%d%d", &n, &m);
67
    int t, s, a;
68
    for (int i = 1; i <= n; i++)
69
    {
70
        number[i].i = i;
71
        scanf("%d%d", &t, &number[i].Imp);
72
        while (t--)
73
        {
74
            scanf("%d", &s);
75
            l.clear();
76
            for (int j = 1; j <= s; j++)
77
            {
78
                scanf("%d", &a);
79
                l.push_back(a);
80
            }
81
            insert(i);
82
        }
83
    }
84
    int k;
85
    for (int i = 1; i <= m; i++)
86
    {
87
        scanf("%d%d", &k, &s);
88
        l.clear();
89
        for (int j = 1; j <= s; j++)
90
        {
91
            scanf("%d", &a);
92
            l.push_back(a);
93
        }
94
        Query(k);
95
    }
96
    //printf("%lf",(double)clock()/CLOCKS_PER_SEC);
97
}