Luogu5994 [PA2014]Kuglarz

tony102

2021 年 01 月 24 日

927 次浏览

暂无评论

719字数

题解

[Link](https://www.luogu.com.cn/problem/P5994)

## Sol

其实我觉得这题就很适合作为联赛题。就是那种典型的水平、积累到了一定层次就会做，有区分度的题目。

首先我们来考虑一下，怎么样才能问出一个被子地下的奇偶性。加入我们问了一段区间$[l,r]$的奇偶性，又问一次$[l,r+1]$的奇偶性，那么$[r,r+1]$这段的有没有球就确定了。原因：假如这两段区间的奇偶性是一奇一偶，说明两个右端点组成的区间必是因为有球才导致的奇偶性不同。

那么我们来形式化地描述这种已经知道$[r,r+1]$的奇偶性的状态：从$[r,r+1]$连一条边。那么，知道$[l,r]$的奇偶性就是从$l$到$r$有一条边（对刚才的性质进行换元就可以了）。我们把按照这种方法建一张图，最终我们就只要选出一些边使这张图联通。最小生成树即可。

我觉得这道题改改可以出道交互题。

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e3 + 5;

int n, m, num;
int fa[SIZE];

struct node {
	int from, to, v;

bool operator< (const node &a) const {
		return v < a.v;
	}
} edge[SIZE * SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

void addEdge(int u, int v, int d) {
	edge[++ num].from = u, edge[num].to = v, edge[num].v = d;
}

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

signed main() {
	// freopen("code.in", "r", stdin);
	n = read();
	for (int i = 1; i <= n; ++ i) {
		for (int j = i, w; j <= n; ++ j) {
			w = read();
			addEdge(i - 1, j, w);
		}
	}
	std::sort(edge + 1, edge + num + 1);
	for (int i = 1; i <= n; ++ i) fa[i] = i;
	int tot = 0, cnt = 0;
	for (int i = 1, fx, fy; i <= num; ++ i) {
		fx = find(edge[i].from), fy = find(edge[i].to);
		if (fx != fy) {
			fa[fx] = fy, ++ cnt, tot += edge[i].v;
		}
		// if (cnt == n - 1) break;
	}
	printf("%lld\n", tot);
	return 0;
}
```

最后修改：2021 年 08 月 20 日