放个差传点在这
apple365怎么这么坏啊难度从后往前

T1

简化题意就是给所有的犯人分成两堆使这两堆的仇恨值最大值最小
本题最坑是：敌人的敌人不一定是我的敌人，所以这里直接pass普通并查集，只能用种类并查集
我们使用最值生成树的时候，要使怨气最大值最小，所以我们要尽量让两个怨气大的远离，排序的时候要把怨气大的放在前面，然后枚举每一条边，如果这两个还没分配监狱，就将他们拆开，否则这就是两个监狱的怨气最大值

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+7;
int n,m;
int fa[maxn];
int find(int x) {
	if(fa[x]==x) {
		return x;
	}
	return fa[x]=find(fa[x]);
} 
void unionn(int u,int v) {
	int x=find(u),y=find(v);
	if(x!=y) {
		fa[x]=y;
	}
}
struct Node{
	int u,v,w;
}edge[maxn];
bool cmp(Node a,Node b) {
	return a.w>b.w;
} 
int ans=0;
void kruskal() {
	for(int i=0;i<maxn;i++) {
		fa[i]=i;
	}
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=m;i++) {
		int u=find(edge[i].u);
		int v=find(edge[i].v);
		if(u==v) {
			cout<<edge[i].w;
			exit(0);
		} else {
			unionn(edge[i].u+n,edge[i].v);
			unionn(edge[i].u,edge[i].v+n);
		}
	}
	cout<<0<<'\n';
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>edge[i].u>>edge[i].v>>edge[i].w;
	}
	kruskal();
	return 0;
}
//A

T2

首先二维不方便进行并查集，所以转成一维，公式为

(x-1)*n+y

然后就开始跑并查集，如果这一个点之前走过说明已经有环了，直接输出，否则给这两个点并上继续去找

T3

首先跑一编埃氏筛筛出a到b中所有的质数，然后枚举a到b，再枚举每一个质数，如果这个质数>p并且可以被整除就用并查集并上
最后枚举a到b看有几个不同的父亲就可以了

T4

并查集板子题但是题开都没开，把x和i并上如果fa[i]==i钥匙不在i位置，cnt加上就可以了

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int fa[maxn],n;
int find(int x) {
	if(fa[x]==x) {
		return x;
	}
	return fa[x]=find(fa[x]);
}
void unionn(int u,int v) {
	int x=find(u),y=find(v);
	if(x!=y) {
		fa[x]=y;
	}
}
signed main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		fa[i]=i;
	}
	for(int i=1; i<=n; i++) {
		int x;
		cin>>x;
		unionn(x,i);
	}
	int sum=0;
	for(int i=1; i<=n; i++) {
		sum+=(fa[i]==i);
	}
	cout<<sum;
	return 0;
}

10.14总结

文章操作

T1

T2

T3

T4

相关推荐

评论

10.14总结