2021年CCCC天梯赛L3 还原文件题解_cccc-l3

题目如下
一份重要文件被撕成两半，其中一半还被送进了碎纸机。

我们将碎纸机里找到的纸条进行编号，如图 1 所示。然后根据断口的折线形状跟没有切碎的半张纸进行匹配，最后还原成图 2 的样子。

要求你输出还原后纸条的正确拼接顺序。

图 1 纸条编号

图 2 还原结果

输入格式
输入首先在第一行中给出一个正整数 N，为没有切碎的半张纸上断口折线角点的个数；随后一行给出从左到右 N 个折线角点的高度值（均为不超过 100 的非负整数）。

随后一行给出一个正整数 M，为碎纸机里的纸条数量。

接下去有 M 行，其中第 i 行给出编号为 i(1≤i≤M) 的纸条的断口信息，格式为：

K h[1] h[2] … h[K]

其中 K 是断口折线角点的个数，后面是从左到右 K 个折线角点的高度值。

为简单起见，这个“高度”跟没有切碎的半张纸上断口折线角点的高度是一致的。

输出格式
在一行中输出还原后纸条的正确拼接顺序。纸条编号间以一个空格分隔。

题目数据保证存在唯一解。

数据范围
1≤N≤105,
1≤M≤100,
1≤K≤104+1
输入样例：
17
95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80
6
4 68 58 58 80
3 81 68 68
3 95 70 80
3 68 60 80
5 80 72 88 81 81
4 80 97 97 68
输出样例：
3 6 1 5 2 4

这题当时做的时候感觉就是搜索，但是怎样存储每个纸条的折线高度值，在搜索的时候怎样比较，还真是个麻烦的问题，突然就没思路了。

后来在看其他人题解的时候，发现这是用字符串哈希做的，这样的话查找也快，第一次见到字符串哈希，算法竞赛入门到进阶我才看到康托展开式，看来得加速学习了，自己的水平还不够，只会搜索和动态和树论还是不行啊。
搬来大佬的代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, M = 110, P = 131;

int n, m;
ULL h[N], p[N];
int width[M];
ULL g[M];
bool st[M];
int ans[M];

ULL get(int l, int r)  // 计算子串 str[l ~ r] 的哈希值
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

bool dfs(int u, int end)
{
    if (end == n) return true;

    for (int i = 1; i <= m; i ++ )
        if (!st[i] && g[i] == get(end, end + width[i] - 1))
        {
            st[i] = true;
            ans[u] = i;
            if (dfs(u + 1, end + width[i] - 1)) return true;
            st[i] = false;
        }
    return false;
}

int main()
{
    scanf("%d", &n);
    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + x + 1;
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i ++ )
    {
        scanf("%d", &width[i]);
        for (int j = 0; j < width[i]; j ++ )
        {
            int x;
            scanf("%d", &x);
            g[i] = g[i] * P + x + 1;
        }
    }

    dfs(1, 1);
    for (int i = 1; i <= m; i ++ )
    {
        printf("%d", ans[i]);
        if (i != m) printf(" ");
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

别问我会不会，我通过这个学会了字符串哈希，下次出个学习笔记！