当前位置：首页 > news >正文

ACM---大一第三周周赛(Floyd算法+并查集算法学习周)

news 2025/8/5 8:30:19

🚀write in front🚀
📝个人主页：认真写博客的夏目浅石.CSDN
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏：ACM周训练题目合集.CSDN
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊
✉️为什么我们不知疲倦，因为我们都在做自己所热爱的事 ♐

文章目录

A - Color the ball
B - Suits
C - 六度分离
D - 无处不在的宗教
E - 农场派对
F - 怪物（简易版）
G - 嫌疑犯
比赛情况：
总结

在这里插入图片描述

A - Color the ball

杭电—Color the ball
在这里插入图片描述
解题思路：考察差分数组，基础模板

#include<iostream>
#include <cstring>using namespace std;int arr[100010];
int n,i;int main()
{while(scanf("%d", &n), n!=0){memset(arr, 0, sizeof(arr));for(i=1;i<=n;i++){int l,r;cin>>l>>r;arr[l]++;arr[r+1]--;}for(i=1;i<=n;i++){arr[i]+=arr[i-1];if(i!=n){printf("%d ", arr[i]);}else printf("%d",arr[i]);}cout<<endl;}return 0;
}

B - Suits

洛谷—Suits
在这里插入图片描述
解题思路：数学问题，一直分类讨论就可以解了

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>using namespace std;int a,b,c,d,e,f;
typedef long long ll;
ll m1,m2;
ll mn=-1;int main() 
{	cin>>a>>b>>c>>d>>e>>f;int max=0;int mn=min(a,d);int mx=min(c,d);if(e*mn+f*min(b,min(c,d-mn))>max){max=e*mn+f*min(b,min(c,d-mn));}if(e*min(a,d-min(b,mx))+f*min(b,mx)>max){max=e*min(a,d-min(b,mx))+f*min(b,mx);}if(e*mn>max){max=e*mn;}if(f*min(b,mx)>max){max=f*min(b,mx);}cout<<max;return 0;
}

C - 六度分离

杭电—六度分离
在这里插入图片描述

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>using namespace std;#define inf 0x3f3f3f3fint g[101][101];
int n,m,ans;int main()
{while(cin>>n>>m){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j) g[i][j]=0;else g[i][j]=inf;}}while(m--){int a,b;cin>>a>>b;g[a][b]=g[b][a]=1;}for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(g[i][j]>g[i][k]+g[k][j]){g[i][j]=g[i][k]+g[k][j];}}}}//以上全部是模板int flag=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(g[i][j]>7){puts("No");flag=1;break;}}if(flag) break;}if(flag==0)puts("Yes");}return 0;
}

D - 无处不在的宗教

POJ无处不在的宗教

在这里插入图片描述

//水题，竟然我也能AC....
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>using namespace std;int n,m;
int p[100010];int find(int x)
{return p[x]==x?x:(p[x]=find(p[x]));//算法模板}
int s=1;
int main()
{cin>>n>>m;
again:int ans=0;for(int i=1;i<=n;i++) p[i]=i;while(m--){int i,j;cin>>i>>j;i=find(i);j=find(j);if(i!=j){p[i]=j;//模板}}for(int i=1;i<=n;i++){if(find(i)==i){ans++;}}printf("Case %d: %d\n",s++,ans);cin>>n>>m;if(n==0&&m==0) return 0;else goto again;return 0;
}

E - 农场派对

#10075. 「一本通 3.2 练习 1」农场派对
在这里插入图片描述

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;#define inf 0x3f3f3f3f//结论，一个很大的数，适合这个算法的初始化int n,m,x;
long long g[1010][1010];
long long path[1010][1010];int main()
{int max=0;cin>>n>>m>>x;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) g[i][j]=0;else g[i][j]=inf;}}for(int i=1;i<=m;i++){int a,b,t;cin>>a>>b>>t;g[a][b]=t;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(g[i][j]>g[i][k]+g[k][j]){g[i][j]=g[i][k]+g[k][j];}}}}//以上全部是算法模板for(int i=1;i<=n;i++){if(g[i][x]+g[x][i]>=max)//这里根据题目要求来写就对了，调试了一会儿AC了{max=g[i][x]+g[x][i];}}cout<<max<<endl;return 0;
}

F - 怪物（简易版）

A. Monsters (easy version)
在这里插入图片描述

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>using namespace std;typedef long long ll;ll t,n,arr[200010],i,j;int main()
{cin>>t;while(t--){ll cnt=0;cin>>n;for(i=1;i<=n;i++) cin>>arr[i];sort(arr+1,arr+n+1);if(arr[1]!=1){cnt+=arr[1]-1;arr[1]=1;}for(i=2;i<=n;i++){if(arr[i]-arr[i-1]>=2){cnt+=arr[i]-arr[i-1]-1;arr[i]=arr[i-1]+1;}}cout<<cnt<<endl;}return 0;
}

G - 嫌疑犯

The Suspects
在这里插入图片描述

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>using namespace std;int n,m,ans,k;
int p[100010];
int a[100010];int find(int x)
{return p[x]==x?x:(p[x]=find(p[x]));//并查集的固定模板
}inline void he(int i,int j)
{int x=find(i);int y=find(j);if(x<y)//这里意思是：让小的数做根节点，也是为了贴近题目要求{p[y]=x;}else p[x]=y;
}int main()
{while(cin>>n>>m&&n||m){ans=0;for(int i=0;i<n;i++) p[i]=i;//初始化while(m--){cin>>k;cin>>a[0];//合并for(int i=1;i<k;i++){cin>>a[i];he(a[i],a[i-1]);}}for(int i=0;i<n;i++){if(find(i)==0)//根据题意来求解。{ans++;}}cout<<ans<<endl;}return 0;
}