11.28 模拟赛

总结

T1 读完题就会了。感觉没什么坑直接写。10min 过大样例。没啥好拍的就不拍了。

T2。感觉不难啊，这种模拟 Kruskal 的题都做一堆了。想。

谔谔正解会不了一点。写个乱搞，看看能不能过大样例。

一开始是没过的，因为少写了一种情况。很久之后意识到改过来发现大样例过了！

然后没对拍。当时真不知道在想啥。

T3 什么玩意，样例解释怎么蹦出个 \(4\)？？？对称点是啥？？？？？花了一点时间（<5min）发现题意看不懂一点，而且部分分挺少，不管了看 T4。

然而事实上 T3 的题面确实很脑瘫。赛后听 lhl 才终于理解题意。而且全机房就 lhl 读懂了题。。。。。而且 A 了。。。。。。。Orz Orz Orz

T4。不是有结论”与+或=和“吗。那么问题不久变成了从 \([l, r]\) 内选若干数，使得它们的与和为 \(sum / 2\) 吗！

想一想做法。\(nq\) 暴力平凡。\(a_i \le 15\) 平凡。随机……或许也是平凡的。有 \(50\)！！！！！

赶紧写。

然后样例没过。然后发现自己跟个小丑似的”与+或=和“跟着题一点关系没有。

还是只会 \(8\) 分。火大。

T2 做法肯定不是正解，但说不定能骗一堆分。先把保底 \(50\) 写了。

然后我还是小丑，\(u_i \in \{0,1\}\) 写了但是忘拼提交的代码上了。

\(100+40+0+0\)。T4 咋挂了？？？哦哦哦哦哦哦出题人题面没写集合不能为空。我***

题解

A. 送信卒

注意到 \(k\) 越小最短路一定不会边长。于是二分答案。check 用 Dijkstra。

B. 星际联邦

解法 1（题解做法）

考虑蓝莓（捷克语：Borůvka）算法。

它的思想很类似 Kruskal。Kruskal 一次操作会选择两个连通块合并，而蓝莓算法则是多个。

流程是这样的：

• 最开始图中有 \(n\) 个连通块。即没有边。
• 为每个点 \(u\) 找一条边 \((u,v,w)\)，其中 \(v\) 和 \(u\) 不在同一个连通块内，且 \(w\) 最小。将这条边称为这个的 最小边。
• 将所有最小边的端点的两个连通块合并。答案加上这些最小边的边权。
• 若此时剩余连通块数量 \(>1\)，回到第二步。否则结束。

【模板】最小生成树 用蓝莓算法实现如下：

int n, m, p[N];
int best[N];		// 最小边
bool st[N];

struct Edge {
	int a, b, c;
}e[N];

int fifa(int x) {
	return x == p[x] ? x : p[x] = fifa(p[x]);
}

void merge(int a, int b) {
	p[fifa(a)] = fifa(b);
}

bool cmp(int a, int b) {
	if (!b) return true;
	if (e[a].c != e[b].c) return e[a].c < e[b].c;
	return a < b;	// 如果边权相等，视作编号小的边更小。
}

void solve() {
	cin >> n >> m;
	
	for (int i = 1; i <= m; ++ i ) {
		cin >> e[i].a >> e[i].b >> e[i].c;
	}
	
	for (int i = 1; i <= n; ++ i ) {
		p[i] = i;
	}
	
	int cnt = 0, res = 0;
	bool flg = true;
	while (flg) {
		flg = false;
		
		memset(best, 0, sizeof best);	
		for (int i = 1; i <= m; ++ i )
			if (!st[i]) {
				int a = fifa(e[i].a), b = fifa(e[i].b);
				if (a == b) continue;
				if (cmp(i, best[a])) best[a] = i;
				if (cmp(i, best[b])) best[b] = i;
			}
		
		for (int i = 1; i <= n; ++ i )
			if (best[i] && !st[best[i]]) {
				flg = true;
				cnt ++ ;
				res += e[best[i]].c;
				st[best[i]] = true;
				merge(e[best[i]].a, e[best[i]].b);
			}
	}
	
	if (cnt == n - 1) cout << res;
	else cout << "orz";
}

复杂度为什么正确？因为一轮操作后图中连通块的数量至少减半。所以复杂度是 \(\mathcal O((n+m)\log n)\)。

对于本题，发现一个点 \(i\) 的最小边一定是前缀最大值或后缀最小值。直接维护即可。

但是最小边的定义里写明，两个端点不能在同一个连通块内。于是还需要维护前缀次小值和后缀次大值。这里的 次 表示不和最值连通块相同的最值。

解法 2（乱搞）

考虑对于每个 \(j\)，找到所有 \(i < j\) 的 \(a_i\) 的前 \(M\) 大，和所有 \(i > j\) 的 \(a_i\) 的前 \(M\) 小。这样边的数量是 \(\mathcal O(nM)\) 的。

实测 \(M=18\) 可过。

C. 对称旅行者

考虑期望。

显然一次跳跃后，第 \(i\) 个人会从 \(x_i\) 跳到 \(\frac 12 (2x_i-x_{i-1}+2x_i-x_{i+1}) = x_{i-1}+x_{i+1}-x_i\)。

然后 P7962 [NOIP2021] 方差。求 \(x\) 的差分数组 \(\Delta x_i=x_i-x_{i-1}\)。

那么第 \(i\) 个人跳一步，相当于交换 \(\Delta x_i,\Delta x_{i+1}\)。

为啥？

原本 \(\Delta x_i=x_i-x_{i-1}\)。跳跃后 \(\Delta x'_i = x_{i-1}+x_{i+1}-x_i-x_{i-1}=x_{i+1}-x_i=\Delta x_{i+1}\)。

原本 \(\Delta x_{i+1}=x_{i+1}-x_i\)。跳跃后 \(\Delta x'_{i+1}=x_{i+1}-(x_{i-1}+x_{i+1}-x_i)=x_{i-1}-x_i = \Delta x_i\)。

也就是说一轮操作 \(a_1 \sim a_m\) 相当于依次执行 \(\operatorname{swap}(\Delta x_{a_1},\Delta x_{a_1+1})\dots \operatorname{swap}(\Delta x_{a_m},\Delta x_{a_m+1})\)。先暴力做一遍，求出 \(p_i\) 表示 \(x'_i = x_{p_i}\)。

然后快速幂维护 \(p^k\)。

最后前缀和。