自动搬运

查看原文

来自洛谷，原作者为

	CznTree 采购。只因有狗cerr不删 on csp-s 2024

搬运于2025-08-24 22:06:25，当前版本为作者最后更新于2024-01-17 20:10:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

其实就是连通块最多有多少个嘛，这样我们就可以用 kruskal。

题解

主要是在 kruskal 中的排序怎么排，我们按照题意来写 cmp 函数，这可能也是本题较难的地方。

我们要保留更多的连通块，就把边权从大到小排序，其他的按照题意即可。

bool cmp(Edge a, Edge b) {
	if(a.w == b.w) { // 边权相等
		if(a.u + a.v == b.u + b.v) { // 起点和终点同样也相等
			return a.u < b.u; 
		}
		return a.u + a.v < b.u + b.v; // 比较和
	}
	return a.w > b.w; // 保留更多的连通块 
}

其他的就基本不难了，用调和级数初始化，连边就行了。

Code

#include <bits/stdc++.h> 
#define IOS std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr) 
#define rep(i, a, b) for (int i = a; i <= b; i++) 
#define per(i, a, b) for (int i = a; i >= b; i--)
#define lc(x) x << 1ll 
#define rc(x) x << 1ll | 1ll
#define lowbit(x) ((x) & (-x))
#define LEN_LC (tree[lc(i)].r - tree[lc(i)].l + 1) 
#define LEN_RC (tree[rc(i)].r - tree[rc(i)].l + 1) 
#define LEN (tree[i].r - tree[i].l + 1)  

const int N = 5e5 + 7; 
const int M = 1e7 + 7;
struct Edge{	
	int u, v, w; 
}edge[M];
int dsu[N], c[N]; 

bool cmp(Edge a, Edge b) {
	if(a.w == b.w) {
		if(a.u + a.v == b.u + b.v) {
			return a.u < b.u; 
		}
		return a.u + a.v < b.u + b.v; 
	}
	return a.w > b.w; 
}


void init() {
	rep(i, 1, N) dsu[i] = i; 
}
int find(int x) {
	if(x != dsu[x]) {
		dsu[x] = find(dsu[x]); 
	}  
	return dsu[x];	
} 
int n; 
long long cnt, ans; 
void kruskal() {
	init(); 
	std::sort(edge + 1, edge + 1 + cnt, cmp); 
	rep(i, 1, cnt) {
		int fx = find(edge[i].u); 
		int fy = find(edge[i].v); 
		if(fx != fy) {
			dsu[fx] = fy; 
			std::cout << edge[i].u << " " << edge[i].v << std::endl; 
		}	
	}
}

void solve() {
	std::cin >> n; 
	rep(i, 1, n) {
		std::cin >> c[i]; 
	}
	
	rep(i, 1, n) {
		for (int j = i * 2; j <= n; j += i) {
			cnt++; 
			edge[cnt].u = i; 
			edge[cnt].v = j; 
			if(c[i] == c[j]) {
				edge[cnt].w = -1; 
			} else {
				edge[cnt].w = 0; 
			}
		}
	}
	
	kruskal(); 
}

signed main() {
	IOS;
	solve(); 
	return 0; 
}

后续

老师说这题根本没有紫的难度！！！