XIX Open Cup named after E.V. Pankratiev. Grand Prix of Daejeon, Division 1

Contest Info

date: 2019.05.05 16:00-21:00

practice link

Solutions

A. A plus equals B

题目大意:给你两个 \(10^{18}\) 内的正整数 \(A,B\),要求你在 \(5000\) 步内使得 \(A,B\) 相等,每步可以执行 \(A+=A,A+=B,B+=A,B+=B\) 四种之一。

题解:注意到 \(A,B\) 可以同时除以它们的 \(\gcd\),不影响结果。那么我们可以通过将 \(A\)\(2\),来变相地将 \(B\) “除以 \(2\)”。之后我们假设 \(A,B\) 均为奇数,且不相等。不妨设 \(A>B\),那么我们执行 \(B+=A\),再不断将 \(B\) 除以 \(2\),显然 \(B\) 一定会变成一个更小的奇数。那么我们总能在有限步内得到 \(1\)\(1\)

注意到每次 \(|A-B|\) 会减半。最大的步数为 \(2\times(1+2+\cdots+60)\),在 \(5000\) 步之内。

C. Cactus Determinant

题目大意:求一棵仙人掌的邻接矩阵的行列式。

题解:首先证明几个结论。

  • 一个排列交换任意两个位置后,逆序数一定改变奇偶性。

交换相邻两个位置显然,交换不相邻的两个位置可以分解成奇数次交换相邻两个位置。

  • 一个排列的逆序数的奇偶性与它各个环的逆序数之和的奇偶性。即环之间的逆序数一定是偶数。

利用上一个结论,由于我们只需要在环内部交换即可得到单位排列,所以该结论正确。

  • 一个环两个方向的逆序数相同

不妨设其中一个方向的排列为 \(p\),那么另一个方向的排列是 \(p^{-1}\),显然 \(i<j\)\(p_{i}>p_{j}\)\(p^{-1}_{i}<p^{-1}_{j}\)\(i>j\) 等价,容易知道这两个排列的逆序数完全相同。

因此,该行列式等于满足下列条件的方案的贡献之和:

将仙人掌分为若干条边及若干个环,它们两两没有公共点,且并起来要包括所有点。每条边给贡献乘上 \(-1\),每个环给贡献乘上 \(2\times(-1)^{\text{inv}}\)

我们在圆方树上 \(dp\),设状态 \(dp[u][0/1]\),表示 \(u\) 的子树已经匹配完成。对圆点来说,\(0/1\) 分别表示 \(u\) 本身未匹配/已匹配;对方点来说,\(0/1\) 分别表示 \(u\) 的父亲未匹配/已匹配。答案即为 \(dp[1][1]\)

对于圆点,若转移到 \(dp[u][0]\),那么它孩子中的方点必须取 \(0\),孩子中的圆点必须取 \(1\);若转移到 \(dp[u][1]\),要么它孩子中的方点恰有一个为 \(1\),要么孩子中的圆点恰有一个为 \(0\)

对于方点,一种情况是取整个环。而如果选择匹配,需要再用一个内层 \(dp\),原理是差不多的,这里就不赘述了。

F. Fruit Tree

题目大意:给出一棵\(n\le250000\)的树,每个顶点有一个数字\(1\le c_i\le n\)\(1\le q\le250000\)次询问,每次问一对顶点\(u\)\(v\)的路径上,是否有一种数字出现次数超过路径长度的一半,如果有,输出这个数字,否则输出-1

题解:先考虑点分治,这样每个询问只在其被分开的分治中心处做一次。分别考虑\(u\)\(v\)到当前分治中心的路径中(假设\(u\)这条路径包括了分治中心,\(v\)没有)出现次数最多的数字\(a\)\(b\),答案只可能是这其中之一,否则就无解。反证法,假设数字\(a\)\(b\)在两条路径中出现的次数分别为\(x\)\(y\),第三种颜色为\(c\),在整条路径的出现次数为\(z\),路径长度为\(k\),则\(z>\frac{k}{2}\)\(x+y\ge z\)\(x+y+z>k\),这显然是矛盾的。为了代码实现方便,求出每个点\(i\)到分治中心路径上(不包含分治中心)的出现次数最多的整数\(f_i\),回答询问的时候只需要检查\(f_u\)\(f_v\)以及分治中心对应的整数是否合法即可。时间复杂度\(O(n\log{n})\).