Contest Info

practice link

Solutions

A. Tile Painting

签到题。

B. 0-1 MST

签到题。

C. Sum Balance

不 wa 就是签到题。

D. Number Discovery

给定一个正整数 \(k\ge2\)，按下面的方法构造一个无限数列 \(s\)：

1. 开始时 \(s\) 为空
2. 找到最小的 \(k\) 个不在 \(s\) 中的正整数 \(t_{1},\cdots,t_{k}\)，并将它们按顺序加入 \(s\) 中
3. 将 \(\sum_{i=1}^{k}t_{i}\) 加入 \(s\) 中
4. 回到 \(2\)

给出 \(1\le n\le10^{18}\)，求出 \(n\) 的位置。

题解：我们证明一个结论：对于每个 \(i\ge0\)，区间 \([(k^{2}+1)i+1,(k^{2}+1)(i+1)]\) 中恰有一个数是和。

使用归纳法。对于 \(i=0\) 的情况，\(\frac{k(k+1)}{2}\) 是一个和。下一个和至少是 \(\frac{k(3k+1)}{2}>k^{2}+1\)。

假设命题对 \(i<t(t>0)\) 成立，\(i=t\) 时，容易观察出，下一个和应该是第 \(\lfloor\frac{i}{k}\rfloor\) 个区间的第 \([(i\bmod k)k+1,(i\bmod k)k+k+1]\) 中的 \(k\) 个数的和。

计算可知该区间为 \([ik+\lfloor\frac{i}{k}\rfloor+1,ik+\lfloor\frac{i}{k}\rfloor+k+1]\)。因此和的范围为 \(\frac{(2ik+2\lfloor\frac{i}{k}\rfloor+k+1)k}{2}\le\text{sum}\le\frac{(2ik+2\lfloor\frac{i}{k}\rfloor+k+3)k}{2}\)。由于 \(\frac{(k+1)k-2(i\bmod k)}{2}\ge1\)，\(\frac{(k+3)k-2(i\bmod k)}{2}\le k^{2}+1\)。因此我们在该区间中找到了一个和。如果 \(k>2\)，可以同样证明 \(i+1\) 在下一个区间中，归纳证明完成。如果 \(k=2\)，那么 \(i=1\) 时无法归纳证明 \(i+1\)，因此需要从 \(i=1\) 为起点进行归纳。

之后算法就可以简单地在 \(\mathcal{O}(\log_{k}n)\) 的复杂度下解决了。

E. Planar Perimeter

题目大意：给定长为 \(f\) 的序列 \(a_{1},\cdots,a_{f}\)，要求你构造一个连通平面图，使得每个有限区域的边数分别是 \(a_{1},\cdots,a_{f}\)，并且使无限区域的边数最小。

题解：\(f=1\) 时，答案显然为 \(a_{1}\)。\(f=2\) 时，若 \(a_{1}=a_{2}\)，则最优解是将一个正方形的左上和右下角用 \(a_{1}-2\) 条边连接起来，答案为 \(4\)。否则不妨设 \(a_{1}>a_{2}\)，我们用多边形 \(1\) 的 \(a_{2}-1\) 条边和一条新边拼成多边形 \(2\)，这样答案是 \(a_{1}-a_{2}+2\)。下面讨论 \(f\ge3\) 的情况。

首先注意到答案的奇偶性和 \(\sum a_{i}\) 的奇偶性相同，我们分别讨论。另外设 \(a_{i}\) 从大到小排好了序。

假如答案为奇数，那么答案最小可能是 \(3\)。首先如果所有 \(a_{i}\) 都是 \(3\)，那么可以取到 \(3\)，因为你可以把一个三角形拆成三个小三角形。

否则的话，假如 \(a_{1}-\sum_{i=2}^{f}(a_{i}-2)>3\)，我们来证明最优解只能是上述值。取到这个值很简单，我们可以用 \(f=2\) 的方法，只不过是多操作几次。同样这个方法每次操作都达到了局部最优。

否则，我们证明一定可以构造出 \(3\)。首先利用三角形的 \(2\) 条边，加上另外 \(a_{1}-2\) 条边拼出多边形 \(1\)，然后我们在另外这个 \(a_{1}-1\) 边形中构造剩余 \(f-1\) 个多边形。假设我们已经构造了前 \(i\) 个多边形，设当前我们在一个边数为 \(x_{i}\) 的多边形中构造剩余的，我们需要始终保证 \(x_{i}-2\le\sum_{j=i+1}^{f}(a_{j}-2)\)，并且有 \(x_{f}=a_{f}\)（否则最后一个多边形没法构造）。\(x_{1}\) 时显然满足。考虑 \(\Delta_{i}=x_{i}-2-\sum_{j=i+1}^{f}(a_{j}-2)\)，构造方法简单的说就是：当 \(\Delta<0\) 时尽可能地让它增大，\(\Delta=0\) 时就让它保持为 \(0\) 即可，可以证明一定能构造出来，这里就不赘述了。

答案为 \(4\) 的数值分析和上面基本相同。

需要特别注意，边数为 \(3\) 时容易构造出重边，要想办法避免。