被T2演了好久，T3比較簡單。

目錄

• 4073. 找規律輸出【簽到】
• 4074. 鐵路與公路【一般 / 思維 最短路】
• 4075. 染色【一般 / 并查集 貪心】

4073. 找規律輸出【簽到】

https://www.acwing.com/problem/content/4076/

#include<bits/stdc++.h> using namespace std; int main(void) {int n; cin>>n;for(int i=1;i<=n-1;i++){if(i&1) cout<<"I hate that ";else cout<<"I love that ";}if(n&1) cout<<"I hate it ";else cout<<"I love it ";return 0; }

4074. 鐵路與公路【一般 / 思維 最短路】

https://www.acwing.com/problem/content/4077/
可以確定的是，必有一種是直接1步從1-n的。
故兩者跑最短路取一個max即可

#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int g[N][N],w[N][N],dist[N],st[N],n,m; int Dijkstra(int s) {memset(st,0,sizeof st);memset(dist,0x3f,sizeof dist);memset(w,0x3f3f3f3f,sizeof w);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) if(g[i][j]==s) w[i][j]=1;dist[1]=0;for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++) if(!st[j]&&(t==-1 || dist[j]<dist[t])) t=j;st[t]=1;for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+w[t][j]);}return dist[n]; } int main(void) {cin>>n>>m;for(int i=1;i<=m;i++){int a,b; cin>>a>>b;g[a][b]=g[b][a]=1;}int ans=max(Dijkstra(1),Dijkstra(0));cout<<(ans==0x3f3f3f3f?-1:ans)<<endl;return 0; }

4075. 染色【一般 / 并查集 貪心】

https://www.acwing.com/problem/content/4078/
注意l,r是倆點，將一個集合的所有元素都變成集合內最多的顏色即可。

#include<bits/stdc++.h> using namespace std; const int N=1e5*3+10; int a[N],p[N],n,m,k,ans; vector<int>ve[N]; int find(int x) {if(x!=p[x]) p[x]=find(p[x]);return p[x]; } int main(void) {cin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>a[i],p[i]=i;for(int i=0;i<m;i++){int l,r; cin>>l>>r;if(find(l)!=find(r)) p[find(r)]=find(l);}for(int i=1;i<=n;i++) ve[find(i)].push_back(i);for(int i=1;i<=n;i++){if(ve[i].size()){int t=0;unordered_map<int,int>mp;for(int j=0;j<ve[i].size();j++) t=max(t,++mp[a[ve[i][j]]]);ans+=ve[i].size()-t;}}cout<<ans;return 0; }

總結

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

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