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})\).