這把打的不順，開頭交不上去就慌了。后面的T2,T3wa麻了。

目錄

• 4082. 子序列【簽到】
• 4083. 最大公約數(shù)【分解因子】
• 4084. 號(hào)碼牌【并查集】

4082. 子序列【簽到】

https://www.acwing.com/problem/content/description/4085/
暴力做法:

#include<bits/stdc++.h> using namespace std; int main(void) {string s;cin>>s;int cnt=0;for(int i=0;i<s.size();i++)for(int j=i+1;j<s.size();j++)for(int z=j+1;z<s.size();z++) if(s[i]=='Q'&&s[j]=='A'&&s[z]=='Q') cnt++;cout<<cnt;return 0; }

前綴和做法:

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int sum[N]; int main(void) {string s;cin>>s; s="0"+s;int cnt=0,n=s.size()-1;for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(s[i]=='Q'?1:0);for(int i=1;i<=n;i++) if(s[i]=='A') cnt+=sum[i-1]*(sum[n]-sum[i]);cout<<cnt;return 0; }

4083. 最大公約數(shù)【分解因子】

https://www.acwing.com/problem/content/description/4086/
對(duì)每一個(gè)數(shù)，分解因子，最后枚舉所有的因子，取一個(gè)max即可。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,x,cnt[N]; int main(void) {cin>>n;for(int i=0;i<n;i++){cin>>x; cnt[x]++;for(int j=2;j<=x/j;j++){if(x%j==0){cnt[j]++;if(x/j!=j) cnt[x/j]++;}}}int ans=1;for(int i=2;i<N;i++) ans=max(ans,cnt[i]);cout<<ans;return 0; } #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,x,cnt[N]; int main(void) {cin>>n;for(int i=0;i<n;i++) cin>>x,cnt[x]++;int ans=1;for(int i=2;i<N;i++) //直接暴力枚舉所有的公共因子即可{int s=0;for(int j=i;j<N;j+=i) s+=cnt[j];//計(jì)算該因子所對(duì)應(yīng)的個(gè)數(shù)ans=max(ans,s);}cout<<ans;return 0; }

4084. 號(hào)碼牌【并查集】

https://www.acwing.com/problem/content/4087/
根據(jù)題意建圖，然后枚舉每一個(gè)點(diǎn)，看是否可以到達(dá)目的地即可。

#include<bits/stdc++.h> using namespace std; const int N=110; int g[N][N],st[N],n,a[N],b[N]; bool dfs(int u,int ed) {if(u==ed) return true;bool flag=0;st[u]=1;for(int i=1;i<=n;i++){if(st[i]) continue;if(g[u][i]) flag=max(flag,dfs(i,ed));}return flag; } int main(void) {cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++){if(i+b[i]<=n) g[i][i+b[i]]=1,g[b[i]+i][i]=1;if(i-b[i]>=1) g[i][i-b[i]]=1,g[i-b[i]][i]=1;}for(int i=1;i<=n;i++){memset(st,0,sizeof st);if(!dfs(i,a[i])) //不可以到達(dá){puts("NO");return 0;}}puts("YES"); }

其實(shí)不用建圖，因?yàn)槎际请p向邊，故直接用并查集，判斷當(dāng)前的點(diǎn)和目的地是不是同一個(gè)集合即可。

#include<bits/stdc++.h> using namespace std; const int N=110; int p[N],n,a[N],b[N]; int find(int x) {if(x!=p[x]) p[x]=find(p[x]);return p[x]; } int main(void) {cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++) p[i]=i;for(int i=1;i<=n;i++){if(i+b[i]<=n) p[find(i+b[i])]=find(i);if(i-b[i]>=1) p[find(i-b[i])]=find(i);}for(int i=1;i<=n;i++){if(find(i)!=find(a[i])){puts("NO");return 0;}}puts("YES"); } 《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Acwing第 28 场周赛【完结】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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