COCI 2020/2021 CONTEST #2 解题报告

2023-12-05 07:59:04

Euklid

作为一道构造题，我们先来手玩一下这个 \(R(a,b)\)，发现并没有什么规律（

再来看数据范围：\(h,g\leq 2\times 10^5\)。为了尽可能简单的构造，我们自然希望 \(R(a,b)\) 恒有 \(a\geq b\)，这样除法次数最少为 \(\log 200000<20\)。

\(\gcd\) 相关的这一部分比较好构造，先构造这一部分。令 \(a,b\) 都为 \(g\) 的倍数即可。\(R\) 相关的部分就难构造了不少。这个构造不是很好想出且不唯一，此处仅给出一种构造方法及证明：

\[b=g\left\lceil\frac{h^K}{g}\right\rceil,a=hb+g \]

当 \(\left\lceil\frac{h^K}{g}\right\rceil> 1\) 时易得 \(g<h^K\leq b,\gcd(a,b)=g\) 。因此 \(R(a,b)=R(h,b)=R(b,h)\)。又有 \(h^K\leq b<h^{K+1}\)，因此 \(R(b,h)=R(1,h)=R(h,1)=h\)。证毕。

值得注意的是仅当 \(\left\lceil\frac{h^K}{g}\right\rceil> 1\) 时才有此结论。枚举 \(K=0\sim \log 200000\) 即可，即使 \(h^K\) 可能溢出，也会在更小的 \(K\) 处得解从而退出循环。

Sjekira

两种做法。一种 \(O(n \log n)\)，另一种是 \(O(n)\)。

这个题显然考虑贪心。每次从连通块大小不为 \(1\) 的连通块中删去一个最大的点是最优的，因为我们希望权值大的点尽可能少的被计入答案。那我们逆序模拟这个过程就好了。具体来说将所有点按权值从小到大排序，考虑加入每个点 \(x\) 和它的连边，如果它的出边指向的 \(y_i\) 已加入，那么就合并 \(x\) 与 \(y_i\) 所在的连通块。这个过程中使用 \(\text{dsu}\) 维护连通块权值最大值即可。算法瓶颈在排序处 \(O(n\log n)\)。

第二种做法更有意思一点。我们尝试把贪心得到的值写成一个表达式：

\[\sum_{i=1}^n t_i-\max_{1\leq i\leq n} t_i+\sum_{i=1}^{n-1}\max(t_{x_i},t_{y_i}) \]

证明如下：考虑任意一棵子树 \(T\)，第一个删除的点是 \(T\) 中的 \(x\) 点，它在 \(T\) 中权值是最大的。那么，设 \(id_i\) 为以 \(i\) 为根的子树内取到点权最大值的点的编号，则删去 \(x\to y_k\) 这条边的花费为 \(val_x+val_{id_{y_k}}\)。我们注意到 \(val_x\) 会作为边上两点权值 \(\max\) 被计入答案，并且每个 \(T\) 内的点只会以非 \(\max\) 的形式被计入一次（举例：处理以 \(id_{y_k}\) 为根的子树统计答案时不再会将 \(x\) 与 \(id_{y_k}\) 以非 \(\max\) 的形式计入）。于是证毕。

直接计算此式即可。时间复杂度为 \(O(n)\)。

Svjetlo

似乎并没有什么想法。但我们可以把序列中一个数转化成一条边。然后对于树上每一条边，统计它被经过的次数。

显然的，树上一条边可以被经过 \(0\sim 4\) 次。因为一条边走 \(0\sim 4\) 次就可以覆盖边 \(x\to y\) 相连的点 \(x\) 与点 \(y\) 所有可能的奇偶性，不必走更多次。画个图观察一下，我们发现路径其实是无向的。可以尝试设一个 \(\text{DP}\)，\(f[x,0/1]\) 表示当前子树 \(x\) 除 \(x\) 外其他点都被置为 \(1\)，\(x\) 被置为 \(0/1\) 的最小花费。

但是发现无法进行转移。原因很简单，因为存在多种情况。\(x\) 子树内含 \(/\) 不含起点 \(/\) 终点，答案是不一样的。

于是设 \(f[x,i,j]\) 表示 \(x\) 子树内含有 \(i=0/1/2\) 个关键点，\(x\) 被置为 \(j=0/1\)，子树内其他点都被置为 \(1\) 的最小花费。