[数据结构与算法]重返天梯-L3-029 还原文件 (30 分)

题目描述

一份重要文件被撕成两半，其中一半还被送进了碎纸机。我们将碎纸机里找到的纸条进行编号，如图 1 所示。然后根据断口的折线形状跟没有切碎的半张纸进行匹配，最后还原成图 2 的样子。要求你输出还原后纸条的正确拼接顺序。

图1 纸条编号

图2 还原结果

输入格式：

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

随后一行给出一个正整数 M（≤100），为碎纸机里的纸条数量。接下去有 M 行，其中第 i 行给出编号为$i（1\le i\le M）$的纸条的断口信息，格式为：

$Kh[1]h[2]...h[K]$其中 K 是断口折线角点的个数（不超过 $10^4+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;
}