本文共 1858 字，大约阅读时间需要 6 分钟。

纸条的拼接问题可以通过构建字符串哈希值并用动态规划的方法来解决。首先，构建哈希值数组和位移乘幂表，然后为每个纸条计算哈希值，最后用动态规划确定正确的拼接顺序。

解决方案

方法思路

为了解决这个问题，我们需要将碎纸机中的纸条按照正确的顺序拼接起来。每个纸条的断口信息可以看作一个模式，而我们需要将其匹配到没有被切碎的半张纸的主字符串中。下面的方法将被用来实现这一点：

这样，通过将纸条视为文本中的模式，我们可以高效地找到正确的拼接顺序。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       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];// 计算子串 [l..r) 的哈希值ULL getHash(int l, int r) {    return h[r] - h[l] * p[r - l];}bool tryMatch(int pos, int end) {    if (end >= n) return true;    for (int i = 1; i <= m; ++i) {        if (!st[i] && g[i] == getHash(end, end + width[i])) {            st[i] = true;            ans[pos] = i;            if (tryMatch(pos + 1, end + width[i])) return true;            st[i] = false;        }    }    return false;}int main() {    // 读取N    scanf("%d", &n);    // 读取N个高度值    h[0] = 0;    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;    }    // 读取M    scanf("%d", &m);    // 读取M个纸条的width    for (int i = 1; i <= m; ++i) {        width[i] = 0;        int x;        scanf("%d", &x);        while (width[i] < x) {            width[i]++;        }        // 读取每个纸条的断口信息        g[i] = getHash(0, 0 + width[i]);    }    // 初始调用    fill(st, st + m + 1, false);    tryMatch(1, n);    // 输出ans数组    for (int i = 1; i <= m; ++i) {        printf("%d", ans[i]);        if (i != m) printf(" ");    }    return 0;}
      
     
    
   

代码解释

通过这种方法，我们可以高效地解决纸条的拼接问题，确保正确顺序的输出。