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

article/2025/7/1 22:53:22

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

我们将碎纸机里找到的纸条进行编号，如图 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;
}