目錄

• 3821. 區間選數【難度: 簡單 / 知識點:思維】
• 3822. 食堂排隊【中 / 知識點: 模擬】
• 3823. 尋找字符串【難 / 知識點: KMP】

3821. 區間選數【難度: 簡單 / 知識點:思維】

#include<bits/stdc++.h> using namespace std; int main(void) {int t; cin>>t;while(t--){int x,y,xx,yy; cin>>x>>y>>xx>>yy;int ans1=x,ans2=xx;while(1){if(ans1==ans2) ans2++;else break;}cout<<ans1<<" "<<ans2<<endl;}return 0; }

3822. 食堂排隊【中 / 知識點: 模擬】

#include<bits/stdc++.h> using namespace std; struct node {int l,r,id; }Node[1005]; bool cmp(node a,node b) {if(a.l==b.l) return a.id<b.id;return a.l<b.l; } int t,n,st[1005]; int main(void) {cin>>t; while(t--){cin>>n;memset(st,0,sizeof st);for(int i=0;i<n;i++) cin>>Node[i].l>>Node[i].r,Node[i].id=i+1;sort(Node,Node+n,cmp);int k=0;for(int i=1;i<=5000;i++){if(Node[k].l<=i&&Node[k].r>=i){st[Node[k].id]=i;k++;while(k<n&&Node[k].r<=i) k++;}if(k>=n) break;}for(int i=1;i<=n;i++) cout<<st[i]<<" ";cout<<endl;}return 0; }

3823. 尋找字符串【難 / 知識點: KMP】

摘自: https://www.acwing.com/activity/content/code/content/1711095/

KMP 可以求出 s 的每個前綴的最長前后綴匹配長度 match 由于 t 在還需要在 s 中間出現，這個在中間出現的 t 同時也是 s 的某個前綴的前綴和后綴， 所以還是可以用 KMP 求 具體來說： 統計出 match[1..n-2] 中的最大值 mxM（下標從 0 開始） 若 t 在 s 中間存在，則 match[n-1], match[match[n-1]-1], ... 中必然能找到一個不超過 mxM 的數 這個數就對應著在 s 中間出現的 t

說白了就是找最大前綴的，最大前綴

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n; char s[N]; int ne[N]; bool st[N]; int main(void) {int t; cin>>t;while(t--){scanf("%s",s+1);n=strlen(s+1);for(int i=2,j=0;i<=n;i++){while(j&&s[i]!=s[j+1]) j=ne[j];if(s[i]==s[j+1]) j++;ne[i]=j;}for(int i=0;i<=n;i++) st[i]=false;for(int i=1;i<n;i++) st[ne[i]]=true;int res=0;for(int i=ne[n];i;i=ne[i])if(st[i]) {res=i;break;}if(!res) puts("not exist");else {s[res+1]=0;printf("%s\n",s+1);}}return 0; }

總結

以上是生活随笔為你收集整理的Acwing第 14 场周赛【完结】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。