bzoj 3214 //3214:[ZJOI2013]丽洁体 //在线测评地址https://www.lydsy.com/JudgeOnline/problem.php?id=3214
更多题解，详见https://blog.csdn.net/mrcrack/article/details/90228694BZOJ刷题记录
bzoj 3214
2388 kb120 msC++/Edit1663 B洛谷65ms / 1.25MB / 1.16KB C++
//3214:[ZJOI2013]丽洁体 //在线测评地址https://www.luogu.org/problem/P3333 //该题与一般的字符串处理不一样，涉及空格的读取gets() //基本思路，确定A,B,C的位置，但从样例来看，如A可能会被其它单词所阻隔，难度增加了． //此文https://www.luogu.org/problemnew/solution/P3333 作者: TopCarry 更新时间: 2019-01-21 12:54思路不错，摘抄如下 /* 显然，A和C要往两边靠 因为我们要求得是 A啥B啥C 而不是 啥A啥B啥C啥 只要我们在T中从左往右找到一个A，就可以停下来，不然 1.这一段会更加浪费。 2.B的发挥空间会更少 C同理 现在问题转变成了如何节约的匹配这个B，他已经保证了每个单词只出现500次，那么他的开头B[1]也只有五百个而已，扫一遍把B1找出来，再从每个B1扫五百次求个min就完事了。 */ //样例一直未通过 //cnt=totc;//此处错写成cnt=totb;，昏了。查了10分钟 2019-10-7 21:25 //int i,j,cur;//此处错写成int i,j,cur,ansb=50010; //样例通过，提交AC.2019-10-7 21:33 #include <stdio.h> #include <string.h> #define maxn 50010 char T[maxn][8],A[maxn][8],B[maxn][8],C[maxn][8]; int left,right,tott=0,tota=0,totb=0,totc=0,ansa=0,ansb=50010,ansc=0,match[510],b=0; void init(){//读取T,A,B,C do{ scanf("%s",T[++tott]); }while(getchar()==' '); do{ scanf("%s",A[++tota]); }while(getchar()==' '); do{ scanf("%s",B[++totb]); }while(getchar()==' '); do{ scanf("%s",C[++totc]); }while(getchar()==' '); } void op_A_C(){//处理A,C int i,cnt=1; for(i=1;i<=tott;i++){//处理A if(strcmp(T[i],A[cnt])==0)cnt++; if(cnt==tota+1){ ansa=i-tota,left=i+1; break; } } cnt=totc;//此处错写成cnt=totb;，昏了。查了10分钟 2019-10-7 21:25 for(i=tott;i>=1;i--){ if(strcmp(T[i],C[cnt])==0)cnt--; if(cnt==0){ ansc=tott-(i-1)-totc,right=i-1; break; } } } int min(int a,int b){ return a<b?a:b; } void op_B(){ int i,j,cur;//此处错写成int i,j,cur,ansb=50010; for(i=left;i<=right;i++) if(strcmp(T[i],B[1])==0)match[++b]=i; for(i=1;i<=b;i++){ cur=1; for(j=match[i];j<=right;j++) if(strcmp(T[j],B[cur])==0){ cur++; if(cur==totb+1)ansb=min(ansb,j-match[i]+1-totb); } } } int main(){ init(); op_A_C(); op_B(); printf("%d\n",ansa+ansc+ansb); return 0; }
