CF750E 线段树+矩阵乘矩阵加-白红宇

CF750E 线段树+矩阵乘矩阵加

阅读量：5154 次

发布时间：2019-06-13

本文共 4302 字，大约阅读时间需要 14 分钟。

题目描述

A string

The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is

Limak has a string $a_{i}ai and ending at the index b_{i}bi (inclusive).$

输入输出格式

输入格式：

The first line of the input contains two integers

The second line contains a string

The $a_{i}ai and b_{i}bi ( 1<=a_{i}<=b_{i}<=n1<=ai<=bi<=n ), describing a substring in the ii -th query.$

输出格式：

For each query print the ugliness of the given substring.

输入输出样例

输入样例#1：

8 3201667661 81 72 8

输出样例#1：

43-1

输入样例#2：

15 50120166620916703 41 144 151 1310 15

输出样例#2：

-121-1-1

输入样例#3：

4 212342 41 2

输出样例#3：

-1-1

说明

In the first sample:

In the first query,

In the second query,

In the third query,

In the second sample:

In the second query,

In the third query,

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define N 200100 7 #define INF 1e9 8 #define lc (p<<1) 9 #define rc (p<<1|1)10 using namespace std;11 int n,m;12 char s[N];13 struct node14 {15     int a[5][5];16     node(){17         for(int i=0;i<5;i++)18             for(int j=0;j<5;j++)19                 a[i][j]=INF;20     }21 }T[N<<2];22 char ch[]={
   '2','0','1','7','6'};23 int find (char x)//返回数字本身的愚蠢办法24 {25     for(int i=0;i<5;i++)26         if(x==ch[i]) return i;27     return -1;28 }29 node pushup(node &a,node &b){30     node res;31     for(int i=0;i<5;i++)32         for(int j=i;j<5;j++)33             for(int k=i;k<=j;k++)34                 res.a[i][j]=min(res.a[i][j],a.a[i][k]+b.a[k][j]);35     return res;36 }37 void build(int p,int l,int r)38 {39     if(l==r)40     {41         int f=find(s[l]);42         for(int i=0;i<5;i++)43             T[p].a[i][i]=0;//初始化——隔壁有更好的方法44         45         //以下为转移方程初始化46         if(f!=-1&&f<4)//l的值为2 0 1 747         {48             T[p].a[f][f+1]=0;49             T[p].a[f][f]=1;50         }51         else if(f==4)//l为652             T[p].a[3][3]=T[p].a[4][4]=1;53         return;54     }55     int mid=(l+r)>>1;56     build(lc,l,mid);57     build(rc,mid+1,r);58     T[p]=pushup(T[lc],T[rc]);59 }60 node query(int p,int l,int r,int ql,int qr)61 {62     if(ql==l&&qr==r)63         return T[p];64     int mid=(l+r)>>1;65     if(qr<=mid) return query(lc,l,mid,ql,qr);66     if(ql>mid) return query(rc,mid+1,r,ql,qr);67     else68     {69         node tmpl=query(lc,l,mid,ql,mid);70         node tmpr=query(rc,mid+1,r,mid+1,qr);71         return pushup(tmpl,tmpr);72     }73 }74 int main()75 {76     scanf("%d%d",&n,&m);77     scanf("%s",s+1);78     build(1,1,n);79     while(m--)80     {81         int l,r;82         scanf("%d%d",&l,&r);83         int ans=query(1,1,n,l,r).a[0][4];84         if(ans==INF) printf("-1\n");85         else printf("%d\n",ans);86     }87     return 0;88 }