[ABC329E] Stamp

yhx0322 · 2023-11-19 13:01:05 · 题解

update on 2023.12.13：更改了描述模糊的内容

Description

有两个字符串 S 和 T，还有一个长度为 N 的仅由字符 # 构成的字符串 X。

现在可以执行若干次操作，每次可以选择字符串 X 中连续的 M 段覆盖为 T。

求：是否能通过若干次操作，使得 X 和 S 相等。

Solution

考虑一个覆盖时间的序列（钦定每一次覆盖记录在其右端点上），发现对于当前点 p：

只有 [p,p+m-1] 这一段区间会影响该点的取值，考虑爆搜，对于当前位置 p，只需要考虑 [p-m+1,p] 这一段长度为 m 的时间序列，枚举当前一个新的位置的相对时间排名，确定下来 [p-m+1,p] 的相对时间顺序，于是位置 p-m+1 的值会被 [p-m+1,p] 中时间值最大的点覆盖掉，再判断 p-m+1 的值是否与 S 串对应位置相等即可。

优化点，即当前状态包含当前位置 p，和前面的时间序列 st，若之前已经走到过 <p,st> 这样一个状态，那当前就没必要继续往下搜了。

Code

#include <bits/stdc++.h>

using namespace std;

unordered_map<int, int> mp;
int n, m;

int gethash(int now, int stat[5]) {
    int hsh = now;
    for (int i = 0; i < m - 1; i++) hsh = hsh * m + stat[i];
    return hsh;
}

char s[200055];
char t[55];

bool search(int now, int stat[5]) {
    int hsh = gethash(now, stat);
    if (mp.find(hsh) != mp.end()) return false;
    mp[hsh] = 1;
    if (now == n + 1) {
        char x[6];
        for (int j = 1; j < m; j++) {
            for (int k = 0; k < m - 1; k++) {
                if (stat[k] == j) {
                    for (int l = 2; l <= m - k; l++) {
                        x[l] = t[l + k];
                    }
                }
            }
        }
        for (int i = 2; i <= m; i++) if (s[n + i - m] != x[i]) return false;
        return true;
    }
    for (int i = 1; i <= m; i++) {
        int new_stat[5];
        new_stat[0] = i;
        for (int j = 1; j < m; j++) {
            new_stat[j] = stat[j - 1];
            if (stat[j - 1] >= i) ++new_stat[j];
        }
        bool flag = true;
        for (int j = 0; j < m; j++) {
            if (new_stat[j] == m) {
                if (s[now - m + 1] != t[j + 1]) flag = false;
            }
        }
        if (!flag) continue;
        for (int j = 0; j < m - 1; j++) {
            if (new_stat[j] > new_stat[m - 1]) --new_stat[j];
        }
        if (search(now + 1, new_stat)) return true;
    }
    return false;
}

int stat[5];
int main() {
    cin >> n >> m;
    scanf("%s%s", s + 1, t + 1);
    if (s[1] != t[1]) {
        puts("No");
        return 0;
    }
    for (int i = 0; i < 5; i++) stat[i] = m - i - 1;
    if (search(m + 1, stat)) {
        printf("Yes");
        return 0;
    }
    printf("No");
    return 0;
}