zqs`s blog

有朋自远方来，虽远必诛

1/27练习赛总结

发表于 更新于 分类于 Valine：

赛时过程：

四道题ABCD，IOI赛制。线上赛。这次是和xxs们打当然我也是xxs，所以对rk1甚至AK比较有信心

A题签到，尼玛明明算好了开long long结果最后输出写成了%d，又交了一遍才过。

B题，就一个并查集统计Size和每个点的度数，板子题。

C题艹这不是我做过的原题改版吗，写了35分。

看了看排名。我235rk1，WCH把A题A了还做了D题，70pts。

尼玛，在我做C题时去干D题还想偷袭我。年轻人不讲武德，来骗，来偷袭，我一个十几岁的老同志，这好吗，这不好！我劝这位年轻人，耗子尾汁，以后不要再犯这样的小聪明

然后怕被WCH巨佬挤下去（虽然只是暂时挤下去）花了四五分钟A了D。回头看C找到了问题，发现此题甚为麻烦。我写了个unordered_map套unordered_set，十分鬼畜复杂度还是假的（比赛结束后改成了正确的复杂度结果跑得还更慢了），但不管怎么说总算A了，可以AK离场了。

摸了一会儿鱼，卡了A题的常数干正事去了。最后rk2lm100，rk3WCH195WCH：cnm

赛后总结：

C题，提交次数还是太多（5次）。另外A题不是一次性过的是二次性过。以后做题要注意提交次数了，尽量一次过（特别是对于水题）。

赛后题解：

老师让我写题解给一起打这场比赛的小学同学们，那就写得详细点吧QwQ。代码放最后面，方便不想展示代码的老师修改题解

嗯……A题好像差不多都A了，具体的令 $s_i=\sum\limits^{j\le i}_{j=1}a_j^2$ ，$g_i=\sum\limits^{j\le n}_{j=i}a_j$，那么就可以枚举位置 $k$ 了。另外，建议算一下数据范围，免得十年OI一场空，不开____见祖宗。

B题，其实是个板子，但是除了我没有人做出来。记 $cnt_i$ 表示 $i$ 为根的集合中的元素数量（注意是 $i$ 为根，所以 $i$ 必须是一个并查集的根）。

merge的时候就fa[x]=y,cnt[y]+=x即可（$x,y$ 分别为要合并的两个集合的根节点）。

然后记录每个点的度数。对于每个点，输出它所在的集合中元素的个数减去度数减去 $1$ （$1$ 是它自己算一个人）。

C题。首先举个例子。如果 $a_i$ 能和 $a_j$ 交换，$a_j$ 能和 $a_k$ 交换，那么 $a_i$ 就能和 $a_k$ 交换。也就是说，如果 $a_i$ 能够和 $a_j$ 交换，那么所有能够和 $a_i$ 交换的下标都能和所有能和 $a_j$ 交换的下标交换。

说到这里肯定都想到并查集了吧。若 $a_i$ 和 $a_j$ 能够交换，合并 $i$ 和 $j$ 所在的集合即可。若 $i$ 和 $j$ 位于同一个集合，则 $a_i$ 和 $a_j$ 能够交换。

这个题还有一个细节：对于一个固定的 $i$，可能存在多个 $j$ 使得 $a_i==b_j$。不难发现直接提前合并所有相同的 $b_j$ 对应的 $j$ 所在的集合是行不通的。

为了解决这个问题，这里再给出一个结论：

若 $S1$ 是能够和 $a_i$ 交换的所有下标 $k$ 构成的集合中满足 $a_i=b_k$ 的子集，$S2$ 是能够和 $a_j$ 交换的所有下标 $k$ 构成的集合中满足 $a_j=b_k$ 的子集，则 $S1\and S2=\empty$ 或 $S1=S2$

看起来这么高大上，实际上仔细想想，能和 $a_i$ 交换的集合与能和 $a_j$ 交换的集合，即 $i$ 所在的集合与 $j$ 所在的集合。很显然这两个集合要么相等要么没有交集，也就自然而然地进一步的出了上面的结论。

那这个结论有什么用呢？设mp[i][j] 表示以 $i$ ，$a_x=j$ 的下标 $x$ 的数量。那么扫一遍 $a$ 中的元素，只要 $mp_{find(i), a_i}$ （find为找根节点的函数）不为0，它就一定能交换到至少一个 $a_i==b_j$ 的 $j$ 位置。根据上面的结论，随便交换到哪一个都无所谓，因此直接--mp[find(i)][a[i]] 即可。

实现的时候注意一个东西，要么把值给离散化，要么像我一样懒人式的使用 unordered_map。使用 unordered_map 非常可靠，虽然它底层哈希算法总会有出错的可能，但是我用这个东西的程序从来没因为这个东西而翻车当然它因此常数巨大，而且时间复杂度还比离散化小（少一个log）。如果真的怕用 map 也行。

算是比赛中一道有思维含量也比较有趣的题。

D题，WA70分盲猜是向上取整的时候翻车了。用每个并查集的 size 除以 $k$ 就好，合并的时候如何维护 size 和B题一样。

尼玛，ABD的题解加起来都没有C题多

$Code:$

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#define int long long
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 131072, stdin), p1 == p2) ? EOF : *p1 ++)

char buf[131072], *p1, *p2;
inline int read() {
	char ch;
	int x(0);
	while ((ch = gc) < 48);
	do x = x * 10 + ch - 48; while ((ch = gc) >= 48);
	return x;
}
int a[1000005], s[1000005], g[1000005];

signed main() {
	int n(read()), ans(0);
	for (int i(1); i <= n; ++ i)
		a[i] = read(), s[i] = s[i - 1] + a[i] * a[i];
	for (int i(n); i; -- i) g[i] = g[i + 1] + a[i];
	for (int i(1); i <= n; ++ i)
		if (s[i] * g[i + 1] > ans) ans = g[i + 1] * s[i];
	return printf("%lld", ans), 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>

int fa[100005], cnt[100005], d[100005];
int find(const int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline void merge(const int x, const int y) {
	if (find(x) != find(y)) cnt[find(y)] += cnt[find(x)], fa[find(x)] = find(y);
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i(1); i <= n; ++ i) fa[i] = i, cnt[i] = d[i] = 1;
	while (m --) {
		int x, y;
		scanf("%d%d", &x, &y);
		merge(x, y), ++ d[x], ++ d[y];
	}
	for (int i(1); i <= n; ++ i) printf("%d ", cnt[find(i)] - d[i]);
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <unordered_map>

int fa[100005], A[100005], B[100005];
bool used[100005];
std::unordered_map<int, std::unordered_map<int, int> > mp;
int find(const int x) {return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);}
struct node {
	int id, v;
	inline bool operator < (const node x) const {return v < x.v;}
	inline bool operator < (const int x) const {return v < x;}
} b[100005];

int main() {
	int n, ans(0);
	scanf("%d", &n);
	for (int i(1); i <= n; ++ i) scanf("%d", A + i);
	for (int i(1); i <= n; ++ i) scanf("%d", B + i);
	for (int i(1); i <= n; ++ i) fa[i] = i;
	int m;
	scanf("%d", &m);
	while (m --) {
		int u, v;
		scanf("%d%d", &u, &v);
		++ u, ++ v;
		fa[find(u)] = find(v);
	}
	for (int i(1); i <= n; ++ i) ++ mp[find(i)][B[i]];
	for (int i(1); i <= n; ++ i)
		if (!mp[find(i)][A[i]]) ++ ans;
		else -- mp[find(i)][A[i]];
	return printf("%d", ans), 0;
}

D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cmath>

int fa[100005], cnt[100005];
bool mark[100005];
int find(const int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline void merge(const int x, const int y) {
	if (find(x) != find(y)) cnt[find(y)] += cnt[find(x)], fa[find(x)] = find(y);
}

int main() {
	int n, m, k, ans(0);
	scanf("%d%d%d", &n, &m, &k);
	for (int i(1); i <= n; ++ i) fa[i] = i, cnt[i] = 1;
	while (m --) {
		int u, v;
		scanf("%d%d", &u, &v);
		merge(u, v);
	}
	for (int i(1); i <= n; ++ i)
		if (!mark[find(i)]) mark[find(i)] = true, ans += ceil(1.00 * cnt[find(i)] / k);
	return printf("%d", ans), 0;
}
-------------本文结束感谢您的阅读-------------