定义一个数字串为“妙”的当且仅当：该串包含某一子序列为 $2017$ ，且不包含子序列 $2016$。

定义一个数字串的“丑值”为：该串至少删去几个字符，可以使得剩余串变“妙”；如果删去任意多个字符，均无法使该串变“妙”，则该串的“丑值”是 $-1$。

给定一个长度为 $n$ 的数字串 $s$ 。有 $q$ 次询问，每次询问用 $(l_i,r_i)$ 表示。对于每次询问，回答子串 $s[l_i...r_i]$ 的“丑值”。

链接

Codeforces

题解

我们考虑只有一个询问而且子串是整个字符串的做法。

我们令 $dp[i][p]$ (其中 $p \in \{0,1,2,3,4\}$) 表示使 $p$ 最多恰好匹配到 $2017$ 的第 $p$ 个位置的最小删除代价，那么我们可以写出如下的 dp 转移方程：

如果我们把一般矩阵的 $(\mathbb Z, \cdot,+)$ 变成 $(\mathbb Z,+,\min)$ ，因为我们的转移只与这个位置的字符有关，那么我们可以写出状态矩阵 $M_i$ ， 使：

1. $s_i = 2$ 时：
   

   $$ M_i = \left[\begin{matrix}{} 1 & \inf & \inf & \inf & \inf\\ 0 & 0 & \inf & \inf & \inf\\ \inf & \inf & 0 & \inf & \inf\\ \inf & \inf & \inf & 0 & \inf\\ \inf & \inf & \inf & \inf & 0\\ \end{matrix}\right] $$

2. $s_i = 0$ 时：
   

   $$ M_i = \left[\begin{matrix}{} 0 & \inf & \inf & \inf & \inf\\ \inf & 1 & \inf & \inf & \inf\\ \inf & 0 & 0 & \inf & \inf\\ \inf & \inf & \inf & 0 & \inf\\ \inf & \inf & \inf & \inf & 0\\ \end{matrix}\right] $$

3. $s_i = 1$ 时
   

   $$ M_i = \left[\begin{matrix}{} 0 & \inf & \inf & \inf & \inf\\ \inf & 0 & \inf & \inf & \inf\\ \inf & \inf & 1 & \inf & \inf\\ \inf & \inf & 0 & 0 & \inf\\ \inf & \inf & \inf & \inf & 0\\ \end{matrix}\right] $$

4. $s_i = 7$ 时：
   

   $$ M_i = \left[\begin{matrix}{} 0 & \inf & \inf & \inf & \inf\\ \inf & 0 & \inf & \inf & \inf\\ \inf & \inf & 0 & \inf & \inf\\ \inf & \inf & \inf & 1 & \inf\\ \inf & \inf & \inf & 0 & 0\\ \end{matrix}\right] $$

5. $s_i = 6$ 时
   

   $$ M_i = \left[\begin{matrix}{} 0 & \inf & \inf & \inf & \inf\\ \inf & 0 & \inf & \inf & \inf\\ \inf & \inf & 0 & \inf & \inf\\ \inf & \inf & \inf & 1 & \inf\\ \inf & \inf & \inf & \inf & 1\\ \end{matrix}\right] $$

6. other
   

   $$ M_i = \left[\begin{matrix}{} 0 & \inf & \inf & \inf & \inf\\ \inf & 0 & \inf & \inf & \inf\\ \inf & \inf & 0 & \inf & \inf\\ \inf & \inf & \inf & 0 & \inf\\ \inf & \inf & \inf & \inf & 0\\ \end{matrix}\right] $$

初始矩阵：

对于询问，我们把矩阵扔到线段树上，因为有结合律（什么你问为什么？我也不知道），每次查询线段树即可，注意合并的时候要右边的矩阵在左，左边的矩阵在右做乘法。

事实上这道题可以支持单点修改的呢（

时间复杂度：$O(5^2 q \log n )$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 410000,N = 5;

struct Matrix{
  int num[N][N];
  Matrix(int op = 0){
    memset(num,0x3f,sizeof(num));
    if(op == 1) for(int i = 0;i<N;i++){
      num[i][i] = 0;
    }
  }
  int *operator [] (int n){return num[n];}
};

Matrix mul(Matrix &a,Matrix &b){
  Matrix ans;
  for(int i = 0;i<N;i++){
    for(int j = 0;j<N;j++){
      for(int k = 0;k<N;k++){
        ans[i][j] = min(ans[i][j],a[i][k] + b[k][j]);
      }
    }
  }
  return ans;
}
Matrix get(int x){
  Matrix t(1);
  if(x == 2) t[0][0] = 1,t[1][0] = 0;
  if(x == 0) t[1][1] = 1,t[2][1] = 0;
  if(x == 1) t[2][2] = 1,t[3][2] = 0;
  if(x == 7) t[3][3] = 1,t[4][3] = 0;
  if(x == 6) t[4][4] = 1,t[3][3] = 1;
  return t;
}

int n,q;
char s[MAXN];

namespace Seg{
  Matrix sum[MAXN<<2];
  #define lson (nown<<1)
  #define rson (nown<<1|1)
  #define mid ((l+r)>>1)
  void build(int nown,int l,int r,char *s){
    if(l == r) sum[nown] = get(s[l] - '0');
    else{
      build(lson,l,mid,s),build(rson,mid+1,r,s);
      sum[nown] = mul(sum[rson],sum[lson]);
    }
  }
  Matrix query(int nown,int l,int r,int ql,int qr){
    if(ql <= l && r <= qr){
      return sum[nown];
    }
    else{
      Matrix L(1),R(1);
      if(ql <= mid) L = query(lson,l,mid,ql,qr);
      if(qr >= mid+1) R = query(rson,mid+1,r,ql,qr);
      return mul(R,L);
    } 
  }
}
int main(){
  scanf("%d %d",&n,&q);
  scanf("%s",s+1);
  Seg::build(1,1,n,s);
  for(int i = 1;i<=q;i++){
    int l,r;
    scanf("%d %d",&l,&r);
    Matrix ans = Seg::query(1,1,n,l,r);
    printf("%d\n",ans[4][0] > (r-l+1)?-1:ans[4][0]);
  }
  return 0;
}