专栏文章

10.14 晚总结

ssccc_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minlw7v7
此快照首次捕获于
2025/12/02 04:33
3 个月前
此快照最后确认于
2025/12/02 04:33
3 个月前
查看原文

P1525 [NOIP 2010 提高组] 关押罪犯

怨气大的肯定是要优先分开的，所以将关系从大到小排序。
将两个监狱分成两个集合，自己的集合为 xx，创建一个虚拟点 x+nx + n 代表对面的集合。
对于一组 (x,y,w)(x,y,w)，若 find⁡(x)=find⁡(y)\operatorname{find}(x) = \operatorname{find}(y)，则 ww 就是答案。否则，unionn⁡(x,y+n),unionn⁡(x+n,y)\operatorname{unionn}(x,y + n), \operatorname{unionn}(x + n, y)。
CPP
#include <bits/stdc++.h>

using namespace std;

int n, m, sum, fa[200005];

struct Node {
	int u, v, w;
} a[100005];

int find(int x) {
	return (fa[x] == x ? x : fa[x] = find(fa[x]));
}

void unionn(int x, int y) {
	x = find(x), y = find(y);
	if (x != y) {
		fa[x] = y;
	}
	return ;
}

bool cmp(Node a, Node b) {
	return a.w > b.w;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		cin >> a[i].u >> a[i].v >> a[i].w;
	}
	for (int i = 1; i <= n + n; i ++)
		fa[i] = i;
	sort (a + 1, a + 1 + m, cmp);
	for (int i = 1; i <= m; i ++) {
		if (find(a[i].u) == find(a[i].v)) {
			cout << a[i].w;
			return 0;
		} else {
			unionn (a[i].u, a[i].v + n);
			unionn (a[i].u + n, a[i].v);
		}
	}
	cout << 0;
	return 0;
}

U125683 [ybt1347]格子游戏

感言：额，很粗心，我服了，输出把 ii 写成了 mm 调半天没调出来最后输出了个 drawdraw。
用并查集判环。
我们要把二维坐标转为一串数字，(x - 1) * n + y。
令当前坐标为 id1id1，移动后为 id2id2。
当 find⁡(id1)=find⁡(id2)\operatorname{find}(id1) = \operatorname{find}(id2) 时，则说明围了一个环，输出 ii。
当 mm 次操作结束后没有围成一个环，则输出 drawdraw。
CPP
#include <bits/stdc++.h>

using namespace std;

int n, m, fa[200005];

int find(int x) {
	return (fa[x] == x ? fa[x] : fa[x] = find(fa[x]));
}

void unionn(int u, int v) {
	u = find(u), v = find(v);
	if (u != v)
		fa[u] = v;
}

signed main() {
//	freopen("B.in", "r", stdin);
//	freopen("B.out", "w", stdout);
	cin.tie(0), cout.tie(0)->sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n * n; i++) {
		fa[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		char c;
		int x, y;
		cin >> x >> y >> c;
		int id1 = (x - 1) * n + y, id2;
		if (c == 'R')
			id2 = (x - 1) * n + y + 1;
		else if (c == 'D')
			id2 = x * n + y;
		if (find(id1) == find(id2)) {
			cout << i;
			return 0;
		}
		unionn(id1, id2);
	}
	cout << "draw";
	return 0;
}

/*

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
 
(1, 1) -> (2, 1) union 1 and 4     fa[1] = 4

(1, 1) -> (1, 2) union 1 and 2     fa[1] = 2

(1, 2) -> (2, 2) union 2 and 5     fa[2] = 5

(2, 1) -> (2, 2) union 4 and 5     fa[4] = 5

*/

P1621 集合

我们可以在埃氏筛的基础上修改。
枚举每一个 ii，因为 ii 都是素数，所以他的倍数和他都有一个共同的质因子，将他们 unionnunionn，最后判断有多少个不同的集合即可。
CPP
#include <bits/stdc++.h>

using namespace std;

int a, b, p, fa[100005];
bool vis[100005];

int find(int x) {
	return (fa[x] == x ? fa[x] : fa[x] = find(fa[x]));
}

void unionn(int x, int y) {
	x = find(x), y = find(y);
	if (x != y) {
		fa[x] = y;
	}
}

void prime(int n) {
	vis[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			for (int j = i + i; j <= n; j += i) {
				vis[j] = 1;
				if (i >= p) {
					unionn(i, j);
				}
			}
		}
	}
}

signed main() {
//	freopen("C.in", "r", stdin);
//	freopen("C.out", "w", stdout);
	cin.tie(0), cout.tie(0)->sync_with_stdio(false);
	cin >> a >> b >> p;
	for (int i = 1; i <= b; i++) {
		fa[i] = i;
	}
	prime(b);
	int sum = 0;
	for (int i = a; i <= b; i++) {
		if (find(i) == i)
			sum++;
	}
	cout << sum;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...