Contest Info

practice link

Solutions

A. Find Amir

签到题。

B. Minimum number of steps

签到题。

C. Ice cream coloring

题目大意：给你一棵 \(n\) 个点的树，每个点有一些物品。物品共有 \(m\) 种。保证每种物品所在的结点在树上连通。建立一个 \(m\) 个结点的图，两个结点之间有边，当且仅当两种物品同时存在于树的某个结点上。求该图的一个最小染色。

题解：我们构造地证明，最小染色是 \(\max\{结点的物品种数\}\)。我们以某个这样的结点为根，它包含的所有种类都需要染不同的颜色。dfs 下去的时候，如果出现了新的种类，由于它不存在于父亲中，所以它只能出现在自己的子树中。因此我们只要随便染一个不与父亲中的种类冲突的颜色就可以了。

D. Expected diameter of a tree

搞题。

E. The same permutation

题目大意：给出排列 \(1,2,\cdots,n\)，要求你对每个相邻位置恰交换一次，变回原来的排列，或判断不可能。

题解：如果 \(\frac{n(n-1)}{2}\) 是奇数，显然不可能。否则我们归纳地进行构造，此时 \(n\mod4=0,1\)。

首先我们将 \(n=4,5\) 的情况打个表。假设 \(n-4\) 已经构造完成，我们将每一对 \((2i-1,2i,j,j+1)(1\le i\le\lfloor\frac{n-4}{2}\rfloor,j\in\{n-3,n-1\})\) 进行 \((1,3),(2,4),(1,4),(2,3)\) 的操作，可以观察到这样操作以后没有任何变化。接下来把剩下的 \(4\) 个或 \(5\) 个的操作做了即可。

F. Fake bullions

题目大意：给出一个 \(n\) 个点的 tournament 图，每个点上有 \(s_{i}\) 个海盗，一些海盗开始时拥有真金子，如果 \(u\to v\) 有边，且 \(\exists t, t\mod s_{u}=a,t\mod s_{v}=b\)，且 \(p_{ua}\) 手上有金子（不论真假），\(p_{vb}\) 手上没有金子，那么 \(p_{vb}\) 会获得一个假金子。

之后他们要卖金子，真金子一定能卖掉，假金子可能能卖掉，也可能会被警察发现。一个点的价值定义为该点成功卖出金子的海盗数量。从所有点中取出价值最大的 \(a\) 个点（价值相同时可任选），再从其中选出 \(b\) 个点。问在所有情况下，这 \(b\) 个点有多少种可能的组合，取模。

题解：这个题分为两部分，首先把哪些海盗拥有假金子求出来。首先证明几个引理。

引理 1

设 \(u\to v\) 有边，那么 \(p_{vb}\) 能从 \(u\) 处获得金子的条件为，\(\exists a,a\equiv b\pmod{\gcd(s_{u},s_{v})}\)，且 \(p_{ua}\) 有金子。证明略。

引理 2

设有一条路径，\(i=v_{0},v_{1},\cdots,v_{t}=j\)，记路径上点的集合为 \(C\)，设 \(g=\gcd_{k\in C}(s_{k})\)，假设有一个海盗 \(p_{ia}\) 有金子，那么 \(\forall b,b\equiv a\pmod{g}\)，\(p_{jb}\) 能获得金子。

证明：我们在路径上归纳地证明。

假设 \(\forall b,b\equiv a\pmod{\gcd(s_{v_{0}},\cdots,s_{v_{k}})}\)，\(p_{v_{k},b}\) 都能拿到金子。对 \(\forall b,b\equiv a\pmod{\gcd(s_{v_{0}},\cdots,s_{v_{k+1}})}\)，我们需要找到一个 \(c\equiv a\pmod{\gcd(s_{v_{0}},\cdots,s_{v_{k}})},c\equiv b\pmod{\gcd(s_{v_{k}},s_{v_{k+1}})}\)。由于 \(\forall b,b\equiv a\pmod{\gcd(s_{v_{0}},\cdots,s_{v_{k+1}})}\)，由数论知识可知上述同余方程有解。\(\Box\)

引理 3

对于一个强连通分量 \(C\)，设 \(g=\gcd_{i\in C}(s_i)\)，假设有一个海盗 \(p_{ia}(i\in C)\) 有金子，那么 \(\forall b,b\equiv a\pmod{g},j\in C\)，\(p_{jb}\) 能获得金子。

证明：我们可以找到一条路径，从 \(i\) 开始经过所有点后回到 \(i\)，然后再到 \(j\)。由引理 2 即可证得。

引理 4

若 \(u\to v,v\to w,u\to w\) 都有边，则不需考虑 \(u\to w\)。

证明：由引理 2 可轻易看出。

引理 5

设有两个强连通分量 \(C\) 和 \(D\)，且 \(C\) 中每个点到 \(D\) 中每个点都有边。设 \(g=\gcd_{i\in C}(s_{i}),h=\gcd_{i\in D}(s_{i})\)，假设有一个海盗 \(p_{ia}(i\in C)\) 有金子，那么 \(\forall b,b\equiv a\pmod{\gcd(g,h)},j\in D\)，\(p_{jb}\) 能获得金子。

证明：从 \(i\) 开始经过所有 \(C\) 中的点后回到 \(i\)，然后走到 \(j\)，再经过所有 \(D\) 中的点后回到 \(j\)。由引理 2 即可证得。

综合上述引理，我们可以得到一个高效的算法。首先将所有强连通分量缩点，由于是 tournament 图，所有点都会向所有比它拓扑序大的点连一条边。根据引理 \(4\)，我们只需考虑所有连接拓扑序相邻点的边。复杂度为 \(\mathcal{O}(\sum s_{i})\)。

第二部分，每个点的价值最少是开始时 1 的数量，最多是结束时 1 的数量，分别记为 \(l_{i}\) 和 \(r_{i}\)。假设我们已经有了一个大小为 \(b\) 的集合，我们需要判断它是否可能取到。显然该集合中的点应该取 \(r\)，集合外的点应该取 \(l\)，该集合能被取到当且仅当大于集合中最小价值的集合外的价值不超过 \(a-b\) 个。我们把所有点按 \(r\) 排序，枚举 \(r\) 最小的那个点，然后组合数一下就好了。

总复杂度 \(\mathcal{O}(\sum s_{i}+n^{2})\)。