题意：给出一个字符串，每次询问一个区间[l,r]，求使得这个区间含有9102但不含有8102最少要删掉几个字符
首先我们考虑将串反转，这样就变成了含有2019但不含有2018的问题了
我们构建一个状态数为5的自动机
状态0：字符集为空
状态1：字符集为2
状态2：字符集为20
状态3：字符集为201
状态4：字符集为2019
每加入一个字符就为对应的两个状态连一条边
两个字串合并我们只需对两个字符串的自动机进行一次dp即可
这样我们维护一个自动机的线段树，每个区间维护一个子串的自动机
查询的时候合并字串区间的自动机即可
AC代码：
#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int maxn=2e5+5; struct Matrix { int a[5][5]; void init() { memset(a, INF, sizeof(a)); for (int i = 0; i < 5; i++)a[i][i] = 0; } void print() { for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++)cout << a[i][j] << " "; cout << endl; } } Matrix operator*(Matrix A) { Matrix ret; memset(ret.a,INF, sizeof(ret.a)); for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) for (int k = 0; k < 5; k++) //因为是倒过来的2019，合并自动机我们要反过来合并 ret.a[i][j] = min(ret.a[i][j], A.a[i][k] + a[k][j]); return ret; } }tree[maxn<<2]; char s[maxn]; void pushup(int rt) { tree[rt] = tree[rt << 1] * tree[rt << 1 | 1]; } void build(int l,int r,int rt) { if (l == r) { tree[rt].init(); if (s[l] == ‘2‘)tree[rt].a[0][0] = 1, tree[rt].a[0][1] = 0; else if (s[l] == ‘0‘)tree[rt].a[1][1] = 1, tree[rt].a[1][2] = 0; else if (s[l] == ‘1‘)tree[rt].a[2][2] = 1, tree[rt].a[2][3] = 0; else if (s[l] == ‘9‘)tree[rt].a[3][3] = 1, tree[rt].a[3][4] = 0; else if (s[l] == ‘8‘)tree[rt].a[3][3] = 1, tree[rt].a[4][4] = 1; return; } int m = (l + r) >> 1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); pushup(rt); } Matrix query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R)return tree[rt]; int m = (l + r) >> 1; Matrix res; res.init(); if (L <= m)res = query(L, R, l, m, rt << 1); if (R > m)res = res * query(L, R, m + 1, r, rt << 1 | 1); return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q, l, r; cin >> n >> q; cin >> (s + 1); build(1, n, 1); while (q--) { cin >> l >> r; Matrix res = query(l, r, 1, n, 1); cout << (res.a[0][4] == INF ? -1 : res.a[0][4]) << ‘\n‘; } return 0; }
原文：https://www.cnblogs.com/xusirui/p/11553028.html