重返天梯-L3-029 还原文件 (30 分)
题目描述
一份重要文件被撕成两半,其中一半还被送进了碎纸机。我们将碎纸机里找到的纸条进行编号,如图 1 所示。然后根据断口的折线形状跟没有切碎的半张纸进行匹配,最后还原成图 2 的样子。要求你输出还原后纸条的正确拼接顺序。
图1 纸条编号
图2 还原结果
输入格式:
输入首先在第一行中给出一个正整数 N ( 1 < N ≤ 1 0 5 ) N(1<N≤10^5 ) N(1<N≤105),为没有切碎的半张纸上断口折线角点的个数;随后一行给出从左到右 N 个折线角点的高度值(均为不超过 100 的非负整数)。
随后一行给出一个正整数 M(≤100),为碎纸机里的纸条数量。接下去有 M 行,其中第 i 行给出编号为 i ( 1 ≤ i ≤ M ) i(1≤i≤M) i(1≤i≤M)的纸条的断口信息,格式为:
K h [ 1 ] h [ 2 ] . . . h [ K ] K h[1] h[2] ... h[K] Kh[1]h[2]...h[K]其中 K 是断口折线角点的个数(不超过 1 0 4 1 10^4 1 104 1),后面是从左到右 K 个折线角点的高度值。为简单起见,这个“高度”跟没有切碎的半张纸上断口折线角点的高度是一致的。
输出格式:
在一行中输出还原后纸条的正确拼接顺序。纸条编号间以一个空格分隔,行首尾不得有多余空格。
题目数据保证存在唯一解。
输入样例:
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
题目解析(字符串哈希)
由于要判等字符串,因此想到字符串哈希
DFS搜索
按位置搜索,用子串从左到右填充原串
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int N = 1e5 10, P = 131, M = 110;
ull h[N], p[N], g[M]; //这里一定要开的是ULL
int n, m;
bool st[M];
int width[M],ans[M];
ull get(int l, int 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;
}
scanf("%d", &m);
for (int i = 1; i <= m; i ) {
int k;
scanf("%d", &k);
width[i] = k;
for (int j = 0; j < k; j ) {
int x;
scanf("%d", &x);
g[i] = g[i] * P x ;
}
}
// 从第1个位置,原串中的位置
dfs(1, 1);
for (int i = 1; i <= m; i ){
if(i == 1) printf("%d", ans[i]);
else printf(" %d", ans[i]);
}
return 0;
}
……
遍历搜索
没有满分,只有26
,暂未找到未过的案例
这里有个结果排序的弯没绕过来当时,有3个量:哈希值、原串中的位置、题目给出的顺序。一开始把哈希值用来排序了,几经周转得出答案,其实只要把原串中的位置进行排序即可
在原串中寻找子串的位置
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ull;
typedef pair<ull, int> PII;
const int N = 1e5 10, P = 131;
int str[N];
ull h[N], p[N];
int n, m;
ull get(int l, int r) {
return h[r] - h[l-1]*p[r-l 1];
}
int main () {
scanf("%d", &n);
for(int i = 1; i <= n; i ) scanf("%d", &str[i]);
p[0] = 1;
// 原样例字符串哈希
for (int i = 1; i <= n; i ) {
p[i] = p[i-1] * P;
h[i] = h[i-1] * P str[i] 1;
}
scanf("%d", &m);
vector<PII> v;
int top = 1;
// 将纸片转成哈希值,在原串中搜索
for(int i = 1; i <= m; i ) {
int k;
scanf("%d", &k);
ull tmp = 0;
for (int j = 0; j < k; j ) {
int x;
scanf("%d", &x);
tmp = tmp * P x 1;
}
for (int j = 1; j <= n-k 1; j ) {
if (tmp == get(j, j k-1)) {
// 将原串中的位置和题目给出的顺序放入vector
v.push_back({j, top});
top ;
break;
}
}
}
// 对所处位置进行排序,得出先后
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i ) {
if (!i) {
printf("%d", v[i].second);
}else printf(" %d", v[i].second);
}
return 0;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfjejf
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01