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

---

P1000 超級瑪麗游戲

做過了，而且很無聊。

---

?

P2562 Kitty貓基因編碼

又一個無聊題，題目的數(shù)據(jù)范圍還錯。

#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兩種情況？

看了題解原來可以用滾動數(shù)組，從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

這個跟字符串什么關(guān)系？這里造的是柵欄，不能直接存點，還要存點與點之間的邊。直接廣搜或者深搜都可以，記得記錄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秘密奶牛碼

什么沙雕題啊……題都看不懂……經(jīng)過題解的提示，每次把最后一個字符加到自己的最前面然后復制一整串。意思是說每次字符串被復制了一倍，設原長為 $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自動機（簡單版）

我其實是先做的加強版……這里簡單版的話，防止同一個模式串被統(tǒng)計多次就要清空它了。模板交上去居然TLE了，先仔細想想。

我懂了，其實是因為我們先在只考慮某個模式串是不是出現(xiàn)過，那么被搜索過的可以標為-1然后下一次搜索到的時候跳過。但是這是為什么呢？這其實很好想，你從文本串中進入到這個節(jié)點，就說明文本串中有對應的串，假如他是模式串就順手統(tǒng)計了，不然就證明這個串以后都沒有啥用了（每次向它的前綴轉(zhuǎn)移）。

#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自動機，丑了一點。這個是要計數(shù)所以不能夠像上面那樣搜索到了就破壞掉自動機。記得在計數(shù)的時候，要先去掉End[temp]=0防止被清空，然后用cnt[temp]就可以統(tǒng)計該模式串匹配的次數(shù)，然后用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

?

轉(zhuǎn)載于:https://www.cnblogs.com/Yinku/p/10503016.html

總結(jié)

以上是生活随笔為你收集整理的洛谷精选 - 字符串合集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。