备案网站制作/易推广
依稀记得那个让我崩溃的题目，做了好久没做出来，后来在网上搜了一下发现这个题近乎于原题，我就更崩溃了，今天拜读了了一下大佬的博客，找了好几篇，做法都是线段树加矩阵的做法，用矩阵来记录状态，发一下大佬的博客地址，借他几张图- -：
https://www.cnblogs.com/BCOI/p/10329108.html
ai，j表示从i状态到j状态需要删除的字符数。
这里我们把字符串翻转，我们就可以查2019与2018，不用倒过来了 - -
其中有五个状态，其中有空集，2,20,201,2019五个状态
.这表示，比如加入状态0，加入一个2，如果我们要转到状态0我们需要删掉2，01中的0就是如果这个数是2，那么矩阵的数就是0.
这个图可以表示出现2018的8时，我们需要删除8.
话不多说代码：
#include<bits/stdc++.h>
#define ll (rt<<1)
#define rr (rt<<1|1)
#define gmid (l+r>>1)
using namespace std;
const int maxn=2e5 + 5;
const int maxm=2e6 + 5;
const int mod=1e9 + 7;
const int Inf=0x3f3f3f3f;
struct Matrix { //定义状态矩阵
int a[5][5];
Matrix(int v = 0) {
memset(a,0x3f,sizeof(a));
for(int i=0;i<5;++i) a[i][i]=v;
}
Matrix operator *(const Matrix &o)const{
Matrix g(Inf);
for(int i=0;i<5;++i)
for(int j=0;j<5;++j)
for(int k=0;k<5;++k)
g.a[i][j]=min(g.a[i][j],a[i][k]+o.a[k][j]);
return g;
}
};
char s[maxn];
Matrix sum[maxn<<2];
int n,q;
void add(int r, int l){ //确定矩阵对应状态值，既上图
if(s[l] == '2') sum[r].a[0][0]=1,sum[r].a[0][1] = 0;
else if(s[l] == '0') sum[r].a[1][1]=1,sum[r].a[1][2]=0;
else if(s[l] == '1') sum[r].a[2][2]=1,sum[r].a[2][3]=0;
else if(s[l] == '9') sum[r].a[3][3]=1,sum[r].a[3][4]=0;
else if(s[l] == '8') sum[r].a[3][3]=1,sum[r].a[4][4]=1;
}
void Up(int rt){ //更新线段树节点
sum[rt]=sum[ll]*sum[rr];
}
void build(int l,int r,int rt){ //建立线段树，rt为节点
if(l==r) {
add(rt,l);
return; }
int mid=gmid;
build(l,mid,ll);
build(mid+1,r,rr);
Up(rt);
}
void query(int l,int r,int rt,int L,int R,Matrix &g){ //找到包含于l-r的区间，将其矩阵的值加起来，有点类似于Floyd算法的矩阵最短路径更新过程。
if(l>=L&&r<=R){
g=g*sum[rt];
return;
}
int mid=gmid;
if(L<=mid) query(l,mid,ll,L,R,g);
if(R>mid) query(mid+1,r,rr,L,R,g);
}
int main(){
scanf("%d%d%s", &n, &q, s + 1);
reverse(s+1,s+1+n); //反转字符串
build(1,n,1);
while(q--){
int l,r;
scanf("%d%d", &l, &r);
l=n-l+1;
r=n-r+1;
swap(l,r);
Matrix ans;
query(1,n,1,l,r,ans);
printf("%d\n", ans.a[0][4]!=Inf?ans.a[0][4]:-1); //找最小值输出
}
}