洛谷精选 - 字符串合集

https://www.luogu.org/problemnew/lists?name=&orderitem=difficulty&tag=2&content=0&select=1&type=

---

P1000 超级玛丽游戏

做过了，而且很无聊。

---

 

P2562 Kitty猫基因编码

又一个无聊题，题目的数据范围还错。

#include<bits/stdc++.h> using namespace std; #define ll long longchar s[261]; char ans[261]; int top;void check(int b,int l){int all0=1,all1=1;for(int i=b;i<b+l;i++){if(s[i]=='0')all1=0;elseall0=0;if(all1==0&&all0==0){break;}}if(all0)ans[top++]='A';else if(all1)ans[top++]='B';else{ans[top++]='C';check(b,l/2);check(b+l/2,l/2);}//printf("%s\n",ans); }void solve(){while(~scanf("%s",s)){top=0;int n=strlen(s);check(0,n);ans[top++]='\0';printf("%s\n",ans);} }int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

---

 

P2543 奇怪的字符串

模板的最长公共子序列会MLE，所以应该考虑更神奇的做法。

这个字符串明显只有0和1两种情况？

看了题解原来可以用滚动数组，从dp的方程可以推出来。

小心越界。（从1开始就没这么多破事）

#include<bits/stdc++.h> using namespace std; #define ll long longchar a[10005]; char b[10005];int dp[2][10005];int lcs(int al,int bl){for(int i=0;i<al;i++){for(int j=0;j<bl;j++){dp[i%2][j]=(a[i]==b[j])?(((i&&j)?dp[(i-1)%2][j-1]:0)+1):max(i?dp[(i-1)%2][j]:0,j?dp[i%2][j-1]:0);}}return dp[(al-1)%2][bl-1]; }void solve(){while(~scanf("%s%s",a,b)){memset(dp,0,sizeof(dp));printf("%d\n",lcs(strlen(a),strlen(b)));} }int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

---

 

P3880 提示问题

注意fgets会连换行符一起保存在字符串中。

#include<bits/stdc++.h> using namespace std; #define ll long longchar s[105]; char ans1[105]; char ans2[105]; char ans3[105];void solve(){fgets(s,100,stdin);int l=strlen(s);ans1[l]=ans2[l]=ans3[l]='\0';int cnt=0;for(int i=0;i<l;i++){ans1[i]=s[i];if(isalpha(s[i])){ans1[i]='.';cnt++;}}int show=round(1.0*cnt/3.0);for(int i=0;i<l;i++){ans2[i]=ans1[i];if(isalpha(s[i])&&show){ans2[i]=s[i];show--;}}int suc=0;for(int i=0;i<l;i++){ans3[i]=ans2[i];if(ans3[i]=='.'&&(s[i]=='A'||s[i]=='a'||s[i]=='E'||s[i]=='e'||s[i]=='I'||s[i]=='i'||s[i]=='O'||s[i]=='o'||s[i]=='U'||s[i]=='u')){ans3[i]=s[i];suc=1;}}if(suc==0){show=round(cnt*2.0/3.0);for(int i=0;i<l;i++){ans3[i]=ans1[i];if(isalpha(s[i])&&show){ans3[i]=s[i];show--;}}}printf("%s%s%s",ans1,ans2,ans3); }int main(){ #ifdef Yinku//freopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

---

 

P2771 建门 gates

这个跟字符串什么关系？这里造的是栅栏，不能直接存点，还要存点与点之间的边。直接广搜或者深搜都可以，记得记录xy的上下界加快过程。

#include<bits/stdc++.h> using namespace std; #define ll long longint l; char s[1005];int minx,maxx,miny,maxy; int g[4005][4005];void bfs(int cnt,int bi,int bj){queue<pair<int,int> >q;g[bi][bj]=cnt;q.push({bi,bj});while(!q.empty()){int i=q.front().first;int j=q.front().second;q.pop();if(i>=minx&&g[i-1][j]==0){q.push({i-1,j});g[i-1][j]=cnt;}if(j>=miny&&g[i][j-1]==0){q.push({i,j-1});g[i][j-1]=cnt;}if(i<=maxx&&g[i+1][j]==0){q.push({i+1,j});g[i+1][j]=cnt;}if(j<=maxy&&g[i][j+1]==0){q.push({i,j+1});g[i][j+1]=cnt;}} }void solve(){scanf("%d",&l);scanf("%s",&s);g[2001][2001]=-1;int curx=2001,cury=2001;minx=curx,maxx=curx,miny=cury,maxy=cury;for(int i=0;i<l;i++){if(s[i]=='N'){curx--;g[curx][cury]=-1;curx--;}else if(s[i]=='E'){cury++;g[curx][cury]=-1;cury++;}else if(s[i]=='S'){curx++;g[curx][cury]=-1;curx++;}else{cury--;g[curx][cury]=-1;cury--;}g[curx][cury]=-1;minx=min(minx,curx);maxx=max(maxx,curx);miny=min(miny,cury);maxy=max(maxy,cury);}/*for(int i=1950;i<2050;i++){for(int j=1950;j<2050;j++){printf("%d",g[i][j]);}printf("\n");}printf("----\n");*/minx--;minx=max(0,minx);maxx++;miny--;miny=max(0,miny);maxy++;int cnt=0;for(int i=minx;i<maxx;i++){for(int j=miny;j<maxy;j++){if(g[i][j]==0){//cout<<"i="<<i<<" j="<<j<<endl;cnt++;bfs(cnt,i,j);}}}printf("%d\n",cnt-1); }int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

---

 

P3375 KMP字符串匹配

用kuangbin的KMP有什么问题呢？怎么就不一样呢？

#include<bits/stdc++.h> using namespace std; #define ll long longchar t[1000000]; char p[1000000];int nex[1000000]; int pos[1000000];void KMP_init(char p[],int pl,int nex[]){int i=0,j=nex[0]=-1;while(i<pl){while(j!=-1&&p[i]!=p[j])j=nex[j];nex[++i]=++j;} }int KMP(char t[],char p[],int tl,int pl){KMP_init(p,pl,nex);int i=0,j=0,ans=0;while(i<tl){while(j!=-1&&t[i]!=p[j])j=nex[j];i++,j++;if(j>=pl){pos[ans++]=i-pl;j=nex[j];}}return ans; }void solve(){scanf("%s",&t);scanf("%s",&p);int tl=strlen(t);int pl=strlen(p);int top=KMP(t,p,tl,pl);for(int i=0;i<top;i++)printf("%d\n",pos[i]+1);for(int i=0;i<pl;i++){printf("%d%c",nex[i]," \n"[i==pl-1]);} }int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

---

 

P3612 Secret Cow Code秘密奶牛码

什么沙雕题啊……题都看不懂……经过题解的提示，每次把最后一个字符加到自己的最前面然后复制一整串。意思是说每次字符串被复制了一倍，设原长为 $l$（从1开始） 那么当 $n==l+1$ 时， $f(n)=(l)$。当 $n>=l+2$ 时， $f(n)=f(n-l-1)$，呃，这就是题解。每次先算出当前的一半 $l$ 就可以了。

打表用的代码：

#include<bits/stdc++.h> using namespace std; #define ll long longchar ans[35000]; int n;int top=0;void rot(){//cout<<top<<endl;int newtop=top;ans[top]=ans[top-1];//cout<<ans<<endl;newtop++;for(int i=0;i<top-1;i++){ans[newtop++]=ans[i];}top=newtop;ans[top]='\0';cout<<ans<<endl; }void solve(){while(~scanf("%s",ans)){cout<<endl;scanf("%d",&n);top=strlen(ans);for(int t=0;t<=6;t++){rot();}}}int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

AC代码：

#include<bits/stdc++.h> using namespace std; #define ll long longchar ans[35000]; ll n;void solve(){while(~scanf("%s",ans)){scanf("%lld",&n);int l=strlen(ans);while(n>l){ll len=l;while(len*2<n)len*=2;if(n==len+1)n=len;elsen=n-len-1;}if(n<=l){printf("%c\n",ans[n-1]);}}}int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

---

 

P3879 阅读理解

哈希可以过的就不用别的东西了，完全匹配嘛！

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long longint t,p; set<ull> text[1005];char s[25];ull Hash(char s[]){int l=strlen(s);ull H=0;for(int i=0;i<l;i++){H=H*19260817+s[i];}//cout<<H<<endl;return H; }void solve(){while(~scanf("%d",&t)){for(int i=0;i<t;i++){int n;scanf("%d",&n);while(n--){scanf("%s",s);//cout<<Hash(s)<<endl;//cout<<s<<"="; text[i].insert(Hash(s));}//cout<<endl; }scanf("%d",&p);while(p--){scanf("%s",s);//cout<<Hash(s)<<endl;//cout<<s<<"=";ull H=Hash(s);int fi=1;for(int i=0;i<t;i++){if(text[i].count(H)){if(fi)printf("%d",i+1),fi=0;elseprintf(" %d",i+1);}}printf("\n");}} }int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

---

 

上面的都是一直到提高组的难度，感觉还ok吧……

---

 

 

P2814 家谱

岂不是一个父指针树就可以了？还保证树高不超过30，这比前面的题还水吧？

我还哈希半天，汗，直接一个map搞定。

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long longmap<string,string> p; map<string,int> havep;string s; string t; char ins; void solve(){while(~scanf(" %c",&ins)){cin>>s;if(ins=='$')break;if(ins=='#'){t=s;}else if(ins=='+'){p[s]=t;havep[s]=1;}else{t=s;while(havep[s])s=p[s];cout<<t<<" "<<s<<endl;}} }int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

---

 

P3808 AC自动机（简单版）

我其实是先做的加强版……这里简单版的话，防止同一个模式串被统计多次就要清空它了。模板交上去居然TLE了，先仔细想想。

我懂了，其实是因为我们先在只考虑某个模式串是不是出现过，那么被搜索过的可以标为-1然后下一次搜索到的时候跳过。但是这是为什么呢？这其实很好想，你从文本串中进入到这个节点，就说明文本串中有对应的串，假如他是模式串就顺手统计了，不然就证明这个串以后都没有啥用了（每次向它的前缀转移）。

#include<bits/stdc++.h> using namespace std; #define ll long longstruct Trie{int nex[1000010][26],fail[1000010],End[1000010];int root,L;int newnode(){/*for(int i=0;i<26;i++)nex[L][i]=-1;*/End[L++]=0;return L-1;}int cnt;void init(){L=0;cnt=0;memset(nex,-1,sizeof(nex));root=newnode();}void insert(char buf[]){int len=strlen(buf);int now=root;for(int i=0;i<len;i++){int &t=nex[now][buf[i]-'a'];if(t==-1)t=newnode();now=t;}End[now]++;cnt++;}void build(){queue<int>Q;fail[root]=root;for(int i=0;i<26;i++){if(nex[root][i]==-1)nex[root][i]=root;else{fail[nex[root][i]]=root;Q.push(nex[root][i]);}}while(!Q.empty()){int now=Q.front();Q.pop();for(int i=0;i<26;i++)if(nex[now][i]==-1)nex[now][i]=nex[fail[now]][i];else{fail[nex[now][i]]=nex[fail[now]][i];Q.push(nex[now][i]);}}}int query(char buf[]){int len=strlen(buf);int now=root;int res=0;for(int i=0;i<len;i++){now=nex[now][buf[i]-'a'];int temp=now;while(temp!=root&&End[temp]!=-1){res+=End[temp];End[temp]=-1;temp=fail[temp];}//if(res==cnt)//return res; }return res;} };char buf[1000010];Trie ac;int n; void solve(){while(~scanf("%d",&n)){if(n==0)break;ac.init();for(int i=0;i<n;i++){scanf("%s",buf);ac.insert(buf);}ac.build();scanf("%s",buf);cout<<ac.query(buf)<<endl;} }int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

---

 

 

P3796 AC自动机（加强版）

第一次做AC自动机，丑了一点。这个是要计数所以不能够像上面那样搜索到了就破坏掉自动机。记得在计数的时候，要先去掉End[temp]=0防止被清空，然后用cnt[temp]就可以统计该模式串匹配的次数，然后用i2s[temp]记录出需要的string，最后弄个s2i保存string的输入顺序。弄得超级复杂。

#include<bits/stdc++.h> using namespace std; #define ll long longstruct sid{string s;int id;bool operator<(sid i){return id<i.id;} }sid2[200];map<string,int> s2i; map<int,string> i2s;struct Trie{int nex[500010][26],fail[500010],End[500010];int root,L;int newnode(){for(int i=0;i<26;i++)nex[L][i]=-1;End[L++]=0;return L-1;}void init(){L=0;memset(cnt,0,sizeof(cnt));maxcnt=0;root=newnode();}void insert(char buf[]){int len=strlen(buf);int now=root;for(int i=0;i<len;i++){if(nex[now][buf[i]-'a']==-1)nex[now][buf[i]-'a']=newnode();now=nex[now][buf[i]-'a'];}End[now]++;i2s[now]=string(buf);}void build(){queue<int>Q;fail[root]=root;for(int i=0;i<26;i++){if(nex[root][i]==-1)nex[root][i]=root;else{fail[nex[root][i]]=root;Q.push(nex[root][i]);}}while(!Q.empty()){int now=Q.front();Q.pop();for(int i=0;i<26;i++)if(nex[now][i]==-1)nex[now][i]=nex[fail[now]][i];else{fail[nex[now][i]]=nex[fail[now]][i];Q.push(nex[now][i]);}}}int cnt[500010],maxcnt;vector<int> A;int query(char buf[]){int len=strlen(buf);int now=root;int res=0;for(int i=0;i<len;i++){now=nex[now][buf[i]-'a'];int temp=now;while(temp!=root){res+=End[temp];//End[temp]=0;cnt[temp]+=End[temp];if(cnt[temp]>maxcnt){A.clear();maxcnt=cnt[temp];A.push_back(temp);}else if(cnt[temp]==maxcnt){A.push_back(temp);}temp=fail[temp];}}return res;} };char buf[1000010];Trie ac;int n; void solve(){while(~scanf("%d",&n)){if(n==0)break;ac.init();i2s.clear();s2i.clear();for(int i=0;i<n;i++){scanf("%s",buf);ac.insert(buf);string tmp(buf);//sid2[i].s=tmp;//sid2[i].id=i;s2i[tmp]=i;}ac.build();scanf("%s",buf);ac.query(buf);cout<<ac.maxcnt<<endl;vector<sid> v;for(auto i:ac.A){sid t;t.s=i2s[i];t.id=s2i[t.s];v.push_back(t);}sort(v.begin(),v.end());for(auto i:v){cout<<i.s<<endl;}} }int main(){ #ifdef Yinkufreopen("Yinku.in","r",stdin);//freopen("Yinku.out","w",stdout); #endif // Yinkusolve(); } View Code

 

转载于:https://www.cnblogs.com/Yinku/p/10503016.html

总结

以上是生活随笔为你收集整理的洛谷精选 - 字符串合集的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。