light题目讲解 7.25模拟赛T1
心得:这一道题其实就是自己打暴力打出来的
没有想到正解真的就是暴力枚举
我的做法是这样的
就是枚举A字符串中长度为x的子串
看它是不是B串的子序列
接下来是我的绝望考试代码(100分AC)
//light /* 这一道题我个人的思路就是二分答案+暴力 */ #include<bits/stdc++.h> using namespace std; string A,B; /* 可以逆序枚举字符串,用ne[i][j]表示i位置的下一个j+'a’字母的位置 */ int ne[2000][26];/* void Yuchuli(){ for(int i=B.length()-1;i>=0;i--){ int j=B[i]-'a'; int k=i-1; while(k>=0&&B[k]-'a'!=j){ ne[k][j]=i; k--; // cout<<k<<' '<<j<<' '<<B[i]<<endl; } if(B[k]-'a'==j) ne[k][j]=i; } }*/ int Zixulie(int l,int r){ int i=l;int k=0; // cout<<l<<" "<<r<<endl; while(k<B.length()){ // j=ne[j][A[i]-'a']; int flag=0; for(int j=k;j<B.length();j++) if(A[i]==B[j]){ flag=1; // cout<<i<<" "<<A[i]<<" "<<j<<" "<<B[j]<<" "<<k<<endl; k=j+1;i++; //cout<<i<<" "<<j<<endl; break; } if(flag==0) break; } if(i>r) return 1; else return 0; } bool check(int llenA){ //现在既然已经预处理出来了 就枚举区间 判断是否是子序列 for(int i=0;i+llenA-1<A.length();i++) if(Zixulie(i,i+llenA-1)==0) return false; return true; } int main() { //freopen("light.in","r",stdin); //freopen("light.out","w",stdout); cin>>A>>B; // Yuchuli(); // for(int i=0;i<B.length();i++){ // for(int j=0;j<26;j++) // cout<<ne[i][j]<<" "; // cout<<endl; // } int l=0,r=2001,ans=-1; while(l<r){ int mid=(l+r)>>1; if(mid>A.length()||mid>B.length()){ r=mid-1; continue; } // cout<<l<<" "<<r<<endl; if(check(mid)==0){ ans=mid; r=mid; } else l=mid+1; } cout<<ans; return 0; }/* aabbcc abcabc Tido 2019/7/25 星期四 10:41:04 abcdefddbba aabbcce */
可以看出来,我把这一道题想复杂了
或者说我觉得这道题很麻烦以至于自己的代码很麻烦
我在程序中的很多地方其实是不必要的
例如二分答案
其实一个个从小往大枚举就行(其实都行)
然后我判断的地方一开始也有一点麻烦
这一道题老师的正解是
就是枚举以i为起点,长度为j的子串 最多也就n2
(》》我一开始还在考虑优化)
n最大2000 20002 =4000000=4*106其实还是可以接受的饿哦
综上所述这一道题就是一个超级简单的模拟枚举暴力求解啦
以后在做题的时候稍微对自己的想法和思路有点信心
以后还要学会自己算一下时间复杂度和空间大小,避免卡bug!
Biu加油