2019ICPC-Nanchang

Posted on | Edited on | In | Views:

C. Hello 2019 (cf-705e)

题意

输入一个字符串，区间询问 $[s_l,s_r]$ 中，删去最少的字符，使得出现子序列 $”2019”$ ，而不出现 $”2018”$

题解

$5$ 个状态：

  • 0 - $””$
  • 1 - $”2”$
  • 2 - $”20”$
  • 3 - $”201”$
  • 4 - $”2019”$

使用一个 $5\times5$ 的矩阵来表示每个点的状态转移所需要的代价，区间查询即这个区间的矩阵的乘积，这里的乘积有些不同，有点像 $floyd$

代码

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
char s[N],t[N];
struct node{
    int a[5][5];
    node(){meminf(a);}
    node operator+(const node& Y)const{
        node res;
        for0(i,5)
        for0(j,5)
        for0(k,5){
            res.a[i][j]=min(res.a[i][j],a[i][k]+Y.a[k][j]);
        }
        return res;
    }
}Sum[N<<2];
void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}//PushUp函数更新节点信息 ，这里是求和
void Build(int l,int r,int rt){ //Build函数建树，l,r表示当前节点区间，rt表示当前节点编号
	if(l==r) {//若到达叶节点 
        // scanf("%d",&Sum[rt]);
		//Sum[rt]=A[l];//储存数组值 
        for0(i,5)Sum[rt].a[i][i]=0;
        
        if(t[l]=='2'){
            Sum[rt].a[0][0]=1;
            Sum[rt].a[0][1]=0;
        }else if(t[l]=='0'){
            Sum[rt].a[1][1]=1;
            Sum[rt].a[1][2]=0;
        }else if(t[l]=='1'){
            Sum[rt].a[2][2]=1;
            Sum[rt].a[2][3]=0;
        }else if(t[l]=='9'){
            Sum[rt].a[3][3]=1;
            Sum[rt].a[3][4]=0;
        }else if(t[l]=='8'){
            Sum[rt].a[3][3]=1;
            Sum[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);//更新信息 
}
node Query(int L,int R,int l,int r,int rt){//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号
	if(L <= l && r <= R){//在区间内，直接返回 
		return Sum[rt];
	}
	int m=(l+r)>>1;
	node ANS;
	if(L <= m) ANS=ANS+ Query(L,R,l,m,rt<<1);
	if(R >  m) ANS=ANS+ Query(L,R,m+1,r,rt<<1|1);
    return ANS;
}
int main() {
#ifdef PerpEternal
    // freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
    // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat", "w", stdout);
#endif
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,q;
    in(n,q);
    in(s+1);
    for(int i = 1; i <= n; i++){
        t[i] = s[n - i + 1];
    }
    Build(1,n,1);
    int l,r;
    while(q--){
        in(l,r);
        node tmp=Query(n-r+1,n-l+1,1,n,1);
        if(tmp.a[0][4]==inf)out(-1,1);
        else out(tmp.a[0][4],1);
    }
    return 0;
}

题意

题解

代码

1
2