Codeforces 750E+2019南昌网络赛C（线段树维护自动机状态转移）

这个题解法之妙导致不想吐槽这场比赛了。。。

原题：Codeforces 750E New Year and Old Subsequence

复现：2019南昌网络赛C题 Hello 2019

原题题意：给定一个数字串，多次询问，每次询问使 $[l,r]$[l,r]区间内存在"2017"这个序列，而不存在"2016"这个序列，至少需要删除多少个元素（无解输出 $-1$−1）

复现题意：给定一个数字串，多次询问，每次询问使 $[l,r]$[l,r]区间内存在"9102"这个序列，而不存在"8102"这个序列，至少需要删除多少个元素（无解输出 $-1$−1）

思路：参考cf题解

先讲原题

1. 在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表 ${\displaystyle \Sigma }$Σ的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。
2. 而本题我们考虑如下 $5$5种状态：
   状态 $0$0：空状态 $or$or 初始状态
   状态 $1$1：包含序列“ $2$2”
   状态 $2$2：包含序列“ $20$20”
   状态 $3$3：包含序列“ $201$201”
   状态 $4$4：包含序列“ $2017$2017”
3. 如果我们将从 $i$i状态转移到 $j$j状态的过程看作一条花费为 $c$c的边，则我们可以得到“ $2$2”，“ $0$0”，“ $1$1”，“ $7$7”，“ $6$6” 这 $5$5个字符所对应的自动机，并且把这样 $5\times 5$5×5的状态转移边放到一个矩阵中，就可以简易地表示自动机。考虑如下代码：

		if(s[l]=='2') t[now].v[0][1]=0, t[now].v[0][0]=1;
        if(s[l]=='0') t[now].v[1][2]=0, t[now].v[1][1]=1;
        if(s[l]=='1') t[now].v[2][3]=0, t[now].v[2][2]=1;
        if(s[l]=='7') t[now].v[3][4]=0, t[now].v[3][3]=1;
        if(s[l]=='6') t[now].v[3][3]=1, t[now].v[4][4]=1;

4. 这 $5$5个矩阵未被声明的元素都被定义为 $inf$inf（主对角线为 $0$0），表明当前自动机在接收这个字符时（这 $5$5种字符），由 $i$i状态转移到 $j$j状态的最小花费为多少。拿 $s\left[i\right]=2$s[i]=2来举例，若当前自动机需要接受字符’ $2$2’，则从 $0$0状态（空状态）转移到 $1$1状态（包含序列“ $2$2”），所需最小花费为 $0$0；而从 $0$0状态（空状态）转移到 $0$0状态（空状态）的最小花费为 $1$1，因为必须要删除当前所接受的字符才行；同时，其他除了主对角线上的转移都是不合法的，因此保留 $inf$inf边，且主对角线上的所有转移（自身转移到自身）都是不需要有任何花费的，因为发生不了转移。后面 $4$4种矩阵同理。但需要注意的是，在当前自动机接受字符’ $6$6‘时，从 $3$3状态（包含序列“ $201$201”）到 $3$3状态（包含序列“ $201$201”），必须删除这个’ $6$6'才行，因此花费为 $1$1；从 $4$4状态（包含序列“ $2017$2017”）到 $4$4状态（包含序列“2017”）,也必须删除掉这个‘ $6$6’才行，因此花费也为 $1$1，而其他的转移跟之前的一样啦。
5. 而当我们想要合并两个自动机时，也就是合并两个串时，我们考虑像 $floyd$floyd一样的思路，考虑由 $i$i状态转移到 $j$j状态中间经过 $k$k状态（枚举 $k$k状态）的最小花费
6. 而如果用线段树维护自动机的合并的话，那是不是就非常好写并且清晰呢？废话不多说，这代码绝对好懂！

Codeforces 750E

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 2e5+10;
const int M = 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

struct Mat{
    int v[M][M];
    void O() { memset(v,inf,sizeof(v)); }
    void I() { O(); for(int i=0; i<M; ++i) v[i][i]=0; }
    friend Mat operator * (Mat a, Mat b) {
        Mat c; c.O();
        for(int i=0; i<5; ++i) for(int j=0; j<5; ++j) for(int k=0; k<5; ++k)
            c.v[i][j]=min(c.v[i][j],a.v[i][k]+b.v[k][j]);
        return c;
    }
}t[maxn<<2];

int n, m, i, j;
char s[maxn];
void build(int l, int r, int now) {
    if(l==r) {
        t[now].I();
        if(s[l]=='2') t[now].v[0][1]=0, t[now].v[0][0]=1;
        if(s[l]=='0') t[now].v[1][2]=0, t[now].v[1][1]=1;
        if(s[l]=='1') t[now].v[2][3]=0, t[now].v[2][2]=1;
        if(s[l]=='7') t[now].v[3][4]=0, t[now].v[3][3]=1;
        if(s[l]=='6') t[now].v[3][3]=1, t[now].v[4][4]=1;
        return;
    }
    int m=(l+r)/2;
    build(l,m,now<<1), build(m+1,r,now<<1|1), t[now]=t[now<<1]*t[now<<1|1];
}

Mat query(int x, int y, int l, int r, int now) {
    if(x<=l&&r<=y) return t[now];
    int m=(l+r)/2;
    Mat res; res.I();
    if(x<=m) res=query(x,y,l,m,now<<1);
    if(y>m) res=res*query(x,y,m+1,r,now<<1|1);
    return res;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read(); scanf("%s", s+1);
    build(1,n,1);
    while(m--) {
        i=read(), j=read();
        printf("%d\n", (i=query(i,j,1,n,1).v[0][4])==inf?-1:i);
    }
}

2019南昌网络赛C

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 2e5+10;
const int M = 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

struct Mat{
    int v[M][M];
    void O() { memset(v,inf,sizeof(v)); }
    void I() { O(); for(int i=0; i<M; ++i) v[i][i]=0; }
    friend Mat operator * (Mat a, Mat b) {
        Mat c; c.O();
        for(int i=0; i<5; ++i) for(int j=0; j<5; ++j) for(int k=0; k<5; ++k)
            c.v[i][j]=min(c.v[i][j],b.v[i][k]+a.v[k][j]); //这里a到b的转移改成b到a的转移，就相当于把原串翻转了
        return c;
    }
}t[maxn<<2];

int n, m, i, j;
char s[maxn];
void build(int l, int r, int now) {
    if(l==r) {
        t[now].I();
        if(s[l]=='2') t[now].v[0][1]=0, t[now].v[0][0]=1;
        if(s[l]=='0') t[now].v[1][2]=0, t[now].v[1][1]=1;
        if(s[l]=='1') t[now].v[2][3]=0, t[now].v[2][2]=1;
        if(s[l]=='9') t[now].v[3][4]=0, t[now].v[3][3]=1; //这里数字小改一下
        if(s[l]=='8') t[now].v[3][3]=1, t[now].v[4][4]=1;
        return;
    }
    int m=(l+r)/2;
    build(l,m,now<<1), build(m+1,r,now<<1|1), t[now]=t[now<<1]*t[now<<1|1];
}

Mat query(int x, int y, int l, int r, int now) {
    if(x<=l&&r<=y) return t[now];
    int m=(l+r)/2;
    Mat res; res.I();
    if(x<=m) res=query(x,y,l,m,now<<1);
    if(y>m) res=res*query(x,y,m+1,r,now<<1|1);
    return res;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read(); scanf("%s", s+1);
    build(1,n,1);
    while(m--) {
        i=read(), j=read();
        printf("%d\n", (i=query(i,j,1,n,1).v[0][4])==inf?-1:i);
    }
}