用来整理模拟赛等

9.23

csp-3【noip23 ZR二十连测 DAY10】

保龄.

A.奇观

狗市题目描述。

不是这题意太大歧义了吧，我讨厌的第二种出题人——题意描述相当不清。

CTH：13 座城市又不代表是 13 座不同的城市。

直接看形式化题目的话（如果能看懂要干什么）那这题确实不难。

解：

容易发现，答案就是 \(C\times C \times F\)。（\(C、F\) 分别表示组成一个 C、F 的方案数）

关键在于 \(CCF\) 怎么求？看懂题意的话，较容易明白：

记 \(v1_i =∑_j[(i, j) ∈ E] ，v2_i=∑_{j,k} [(i, j) ∈ E ∧ (j, k) ∈ E] = ∑_j[(i, j) ∈ E]v1_j\)；

分别为以 \(i\) 为端点能拼成如下形式的方案数。

那么有 \(C=\sum_i v1_i\times v2_i\) ， \(F = \sum v1_i \times \ v1_i \times v2_i\) 。

显然 \(v1_i\) 其实就等于删去 \(m\) 条边后的出度。现在考虑 \(v2_i\) 如何求。

我们再求一个 \(sum=\sum_i v1_i\)，把每个 \(v2_i\) 都赋成 \(sum\)，删去了哪些 \(i,j\) 相连的边，就减去 \(v1_j\) 即可。

B.铁路

随便钦定一个根跑 \(dfs\) 得到所有点的深度 \(dep\) 和父节点 \(fa\)

并查集维护连通块，每次把要合并的点都合并到其中深度最浅的点的并查集上，把 \(n+i\) 映射到这个最浅点上就好了。