并不对劲的bzoj3214:p3333:[ZJOI2013]丽洁体-白红宇

并不对劲的bzoj3214:p3333:[ZJOI2013]丽洁体

阅读量：4977 次

发布时间：2019-06-12

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

题目大意

有三个由若干个单词组成的字符串\(T,A,B,C(|T|,|A|,|B|,|C|\leq 5*10^4,单词长度\leq5,每个单词出现次数\leq500)\)

求从\(T\)中至少删去多少个单词，使\(T\)变成\(A*B*C\)的形式，其中\(*\)可以用若干个单词替换，输入数据保证有解

题解

发现删去若干个单词后，一个前缀变成了\(A\)，一个后缀变成了\(C\)，那么找到最短的有\(A\)为子序列的前缀和最短的有\(C\)为子序列的后缀就行

在剩下的部分中，找到最短的以\(B\)为子序列的子串

\(B\)中的第一个单词只出现了不超过\(500\)次，那么就可以先枚举起点，再用上面的方法贪心

时间复杂度\(\Theta(|T|*(B的第一个单词出现次数))\)

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #define rep(i,x,y) for(register int i=(x);i<=(y);++i)#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)#define maxn 50001#define maxm 501#define LL long long#define UI unsigned intusing namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)&&ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); return x*f;}void write(int x){ if(x==0){putchar('0'),putchar('\n');return;} int f=0;char ch[20]; if(x<0)putchar('-'),x=-x; while(x)ch[++f]=x%10+'0',x/=10; while(f)putchar(ch[f--]); putchar('\n'); return;}char s[10],c;UI t[maxn],a[2][maxn],b[maxn];int len,lent,lena[2],lenb,hd,tl,fakeans,ansb=2147483647;UI hsh(){ UI res=0,now=1; rep(i,1,len){if(s[i]<'a'||s[i]>'z')break;res+=now*(UI)(s[i]-'a'+1),now=now*(UI)27;} return res;}int getstr(UI * u){ int lenu=0; do { len=0;c=getchar(); while(c==' '||c=='\n')c=getchar(); while(c!=' '&&c!='\n')s[++len]=c,c=getchar(); u[++lenu]=hsh(); }while(c!='\n'); return lenu;}int main(){ lent=getstr(t),lena[0]=getstr(a[0]),lenb=getstr(b),lena[1]=getstr(a[1]); int j=0; rep(i,1,lent) { if(t[i]==a[0][j+1])j++; if(j==lena[0]){hd=i+1;fakeans=i-j;break;} }j=lena[1]+1; dwn(i,lent,1) { if(t[i]==a[1][j-1])j--; if(j==1){tl=i-1;fakeans+=lent-i+1-lena[1];break;} } rep(i,hd,tl) if(t[i]==b[1]) { int j=1; rep(k,i+1,tl) { if(t[k]==b[j+1])j++; if(j==lenb){ansb=min(ansb,k-i+1-j);break;} } } write(fakeans+ansb); return 0;}