Contest Info

date 2017.08.24 12:00-17:00

practice link

Solutions

A. Admiral

题目大意：给定一个三角形棋盘的结束状态，每次询问一个初始状态，问是否可以在 \(20\) 步之内到达。

题解：对局面 hash，然后 meet in the mid，先预处理从结束状态逆向 \(10\) 步以内可以到达的状态，然后每次询问直接搜索即可。

B. Array Challenge

题目大意：略。

题解：见官方题解，感觉凑数字挺没意思的。猜到是线性递推以后可以用 BM 算法直接莽。

C. Boring Game

题目大意：给你一个 \(n\times n\) 的网格，每个格子中有一枚硬币，硬币的朝向以 \(m\) 个矩形的方式给出（矩形内的硬币朝上）。两人轮流操作，每次操作选取一个右下角硬币朝上的矩形，把这个矩形中所有硬币翻面，不能操作者负。问先手胜还是后手胜。

题解：这道题需要用到 nim积的结论。

根据一个显然的结论和 Tartan 定理，一个局面的 \(sg\) 值等于所有朝上格子单一存在时的 \(sg\) 值的 nim 和，而每个格子的 \(sg\) 值等于一维情况下它的行和列分别的 \(sg\) 值的 nim 积。由于全体非负整数在 nim 和和 nim 积下成一域，所以这道题我们就可以跟普通的矩形面积并一样用扫描线 + 线段树做了。一维情况下是 Ruler 博弈，第 \(i\) 个格子单一朝上时的 \(sg\) 值是 \(\text{lowbit}(i)\)。

再考虑求 \(\bigoplus\limits_{i=1}^{n}\text{lowbit}(i)\)。\([1,n]\) 的 \(\text{lowbit}\) 中 \(2^{j}\) 出现的位置为 \((2t+1)\cdot 2^j(0\leq t)\)，那么出现奇数次也即 \((2\cdot (2k)+1)\cdot 2^j\leq n < (2\cdot (2k+1)+1)\cdot 2^j\)。综上， \(2^j\) 的个数为: \[ \begin{cases} \text{odd}, &(2^{j}\le (n\text{ mod }2^{j+2}) < 3\cdot 2^{j})\\ \text{even}, &(\text{others})\\ \end{cases} \]

也就是说，有奇数个 \(2^{j}\) 等价于 \(n\) 的第 \(j+1\) 位和第 \(j\) 位有且仅有一个 \(1\)，故所求为 \(n\oplus \lfloor\frac{n}{2}\rfloor\) 。

D. Brother and Sister

题目大意：给你一个 \(n\) 个点的有向图，所有点的出度为 \(1\) ，和另外一个特殊的孤立点标号为 \(0\) 。每次等概率在剩下的点中随机选取一个点，把这个点能走到的所有点删除，如果选到 \(0\) 就结束。问期望删除了多少个点。

题解：设随机变量 \(X_{i}=1\) 表示 \(i\) 被删除， \(X_{i}=0\) 表示 \(i\) 未被删除，则答案为 \(\sum_{i=0}^{n}E_{i}\) 。设 \(S_{i}=\{能到达i的点\}\cup\{0\}\) ，\(X_{i}=0\) 等价于 \(S_{i}\) 中第一个被删除的点是 \(0\) ， \(X_{i}=1\) 等价于 \(S_{i}\) 中第一个被删除的点不是 \(0\) 。由于每次选点是等概率的，故 \(P(X_{i}=1)=\frac{|S_{i}|-1}{|S_{i}|}\) ，故答案为 \(\sum_{i=0}^{n}\frac{|S_{i}|-1}{|S_{i}|}\) 。

ps: 这道题真的很原题啊，但是 Z 居然看都没看一眼，简直智障。题目找不到了，和这题的区别在于没有特殊点 \(0\) ，所以把所有点删完才结束，然后问的是选点次数的期望。那个题的答案是 \(\sum_{i=1}^{n}\frac{1}{能到达i的点的个数}\) ，证明就略了。

E. Cube Summation

题目大意：求一个正整数的所有划分方案的集合大小的立方和。

题解：首先可以很容易的用递推式 \(\mathcal{O}(n\sqrt{n})\) 求出 划分数 。

设 \(P(x)\) 表示划分数的生成函数， \(\Sigma_{0}(x),\Sigma_{1}(x),\Sigma_{2}(x)\) 分别表示约数个数函数、约数和函数、约数平方和函数的生成函数。

我们先说明如果把立方和改为一次方和，答案就是 \([x^{n}](P(x)\Sigma_{0}(x))\) 。对于每个划分，它的每个元素给答案贡献了 \(1\) ，考虑一个划分中的第 \(i\) 个 \(j\) ，它在 \(\sigma_{0}(ij)\) 中恰对应了一个 \(1\) ，而这个划分也恰好对应了 \(p(n-ij)\) 中的一个划分（即去掉前 \(i\) 个 \(j\) 后的那个 \(n-ij\) 的划分）。

用同样的方法考虑，一个划分中，三个不同的数给答案贡献了\(6\) 倍它们个数之积，两个不同的数给答案贡献了 \(3t_{1}^{2}t_{2}+3t_{1}t_{2}^{2}(t_{1},t_{2}是它们的个数)\) ，一个数给答案贡献了个数的三次方。\(P(x)\Sigma_{0}^{3}(x)\) 正好贡献完了三个不同的数，给两个不同的数贡献了 \(\frac{3t_{1}(t_{1}-1)}{2}\cdot t_{2}+\frac{3t_{2}(t_{2}-1)}{2}\cdot t_{1}\) ，给一个数贡献了 \(\frac{t(t-1)(t-2)}{6}\)(t为个数)的答案。 \(3P(x)\Sigma_{0}(x)\Sigma_{1}(x)\) 给两个不同的数贡献了 \(\frac{3t_{1}(t_{1}+1)}{2}\cdot t_{2}+\frac{3t_{2}(t_{2}+1)}{2}\cdot t_{1}\) ，给一个数贡献了 \(\frac{t(t+1)(t-1)}{2}\) 。\(P(x)\Sigma_{2}(x)\) 给一个数贡献了 \(\frac{t(t+1)(2t+1)}{6}\) 的答案，这样正好贡献完了所有的答案，所求即为 \([x^{n}]\left(P(x)(\Sigma_{0}^{3}(x)+3\Sigma_{0}(x)\Sigma_{1}(x)+\Sigma_{2}(x))\right)\) 。

F. Function Counting

题目大意：求满足下列条件的函数 \(f(x)\) 的个数：

• \(f:M\to M,(M=\{0,\pm1,\dots,\pm n\})\)
• \(\forall x\in M,f_k(x)=-x,\left(f_0(x)=x,f_i=f(f_{i-1})(i=1,2,\dots)\right)\)
• \(\forall x\in M,\left| (|f(x)|-|x|) \right|\leq 2\)

单组数据 \(n\cdot k\leq 10^9\)，\(\sum n\cdot k\leq 4\cdot 10^9\)

题解：我们构造一个有向图，将 \(x\) 向 \(f(x)\) 连边，显然每个点的出度为 \(1\)，还要满足题目的第二个条件，不难发现图的每个联通块是一个环。显然有 \(f(0)=0\) 是一个自环。我们考虑在某个环中，\(\forall x\) 走 \(a\) 步会第一次到达点 \(-x(a\mid k,\frac{k}{a} \text{ is odd})\)，那么环长显然为 \(2a\)。结合第三个条件，我们将环分为几类：

• \(a=1\)，只有 \(1\) 种连边方案，（\(x\to -x\)）。
• \(a=2\)，此时的环可能为 \(x\to x-i\to -x(i=1,2)\)。当 \(i=1\) 的时候，\(x,x-1\) 是连续的两个绝对值，有 \(2\) 种连边方案。当 \(i=2\) 的时候，我们可以考虑四个连续的绝对值（例如1,3;2,4），一共有 \(4\) 种连边方案，此时 \(a=1\) 一定不满足 \(\frac{k}{a}\text{ is odd}\)。
• \(a\geq 3\)，其中有两对相邻点的绝对值之差为 \(1\)，其他均为 \(2\)，对应 \(2\cdot \frac{2^a}{2!} = 2^a\) 种连边方案，形如（1,2,4,6,8,10,9,7,5,3,-1 和 1,3,5,7,9,10,8,6,4,2,-1）。

可以发现，除了 \(a=2\) 且 \(i=2\) 的时候，其余情况均为连续的一段绝对值，于是我们可以写出 dp 方程：\(\displaystyle dp[i]=\left(\sum\limits_{a\mid k,\frac{k}{a}\text{ is odd}}dp[i-a]\cdot 2^{a-[a\leq2]}\right)+dp[i-4]\cdot 4\cdot [\frac{k}{2}\text{ is odd}]\)。最终的答案即为 \(dp[n]\)。直接 dp 的复杂度为 \(\mathcal{O}(n\tau(k))=\mathcal{O}(n\sqrt k)\)。用矩阵快速幂加速递推的复杂度为 \(\mathcal{O}(k^3\log n)\)，我们根据输入判断用哪种方法即可。

tls 说矩阵快速幂的时候可以做到 \(\mathcal{O}(k^2\log n)\)，还没弄明白。

G. Jacana Number

题目大意：比较 \(n\uparrow\uparrow a\) 和 \(m\uparrow\uparrow b\) 的大小。\(1\leq n, a, m, b \leq 10^9\)。

题解：为方便起见，我们只考虑 \(2\le n<m,a>b\) 的情况。

• \(n\ge10\) 时有： \[ \begin{aligned}\\ n^{n}&\ge 10\cdot m\\ n^{n^{n}}&\ge n^{10\cdot m} =(n^{10})^{m}\\ &\ge(10\cdot m)^{m}\\ &\ge 10\cdot m^{m}\\ &\end{aligned}\\ \]

依此类推。故此时 \(n\uparrow\uparrow a>m\uparrow\uparrow b\) 。

• \(3\le n \le 9\) 时有：
  • 若 \(a-b\ge2\)，由于 \(3^{3^{3}}>7\times10^{12}>1000\cdot 10^{9}\)，此时答案为大于。
  • 若 \(a-b=1\) 且 \(a=2\) ，可以直接暴力计算。
  • 若 \(a-b=1\) 且 \(a>2\) ，求出 \(p = \frac{n^{n^{n}}}{m^{m}}\) ，若 \(p<1\) ，易证有 \(n\uparrow\uparrow a<m\uparrow\uparrow b\) 。打表可知不存在 \(p=1\) 的情况，若 \(p>1\) ，打表可知 \(3\le n\le 5\) 时，有 \(p>30\)，\(6\le n \le 9\) 时，有 \(p>15\) ，此时答案为大于。
• \(n=2\) 时有：
  • 若 \(a-b\ge 4\)，由于 \(2^{2^{2^{2^{2}}}}=2^{65536}>1000\cdot10^{9}\)，此时答案为大于。
  • 若 \(a-b=3\) ，若 \(a=4\) ，可以暴力计算。若 \(a>4\) ，由于 \(2^{2^{2^{2^{2}}}}<5298^{5298}\) ，此时答案为小于，而 \(2^{2^{2^{2^{2}}}}>100\cdot5297^{5297}\) ，此时答案为大于。
  • 若 \(a-b=2\) ，若 \(a=3\) 或 \(4\) ，可以暴力计算。若 \(a>4\) ，由于 \(2^{2^{2^{2^{2}}}}<6^{6^{6}}\) ，此时答案为小于，而 \(2^{2^{2^{2^{2}}}}>1000\cdot 5^{5^{5}}\) ，此时答案为大于。
  • 若 \(a-b=1\) ，若 \(a\le 4\) ，可以暴力计算。若 \(a>4\) ，由于 \(2^{2^{2^{2^{2}}}}<3^{3^{3^{3}}}\) ，此时答案为小于。

H. Monkeys

题目大意：给你一棵 \(n\) 个点的树，和 \(k\leq n\) 只猴子，每个点最多有一只猴子。现在可以删除一些边，问最少留下多少条边，使得存在一种放置猴子的方案，且没有任意一只猴子在孤立点上。

题解：为了使留下的边尽可能少，我们先对树做一次最大匹配，设匹配数为 \(\text{cnt}\)。那么我们可以用 \(T=\min\{\text{cnt}, \lfloor \frac{k}{2} \rfloor \}\) 条边来装 \(2T\) 只猴子。剩下的猴子，每只连一条边在已有的联通块中即可。那么总答案为 \(T+(k-2T)=k-T\)。

求树上最大匹配我们可以用 dp。\(dp[u][0/1]\) 表示以 \(u\) 为根的子树，点 \(u\) 未选/已选的最大匹配。那么有：

• \(dp[u][0]=\sum\limits_{p[v]=u}\max\{dp[v][0],dp[v][1] \}\)
• \(dp[u][1]=\max\limits_{p[v]=u}\left\{dp[v][0]+\sum\limits_{w\neq v,p[w]=u}\max\{dp[w][0],dp[w][1]\}\right\}\)

I. Rotating Line

题目大意：平面上有 \(n\) 个点，开始时有一条和 \(y\) 轴重合的直线，以 \((0,0)\) 为旋转中心逆时针旋转这条直线，每当这条直线碰到了一个新的点，就把当前的旋转中心变为它在这条直线上的位置对称的那个点（如1，2，3，1号变3号，可能不变），然后继续旋转，问第 \(q\) 个旋转中心。

题解：给这条直线的初始方向定为 \(y\) 轴正向，先说明旋转过程中，直线左侧的点数，加直线上面旋转中心下侧的点数不变：在旋转中没有碰到新点时显然所有点的上下左右相对位置不变，碰到新点时，现在直线上旋转中心上侧的点原先在直线左侧，下侧的点原先在直线右侧。容易发现把旋转中心对称过去正好抵消了这个变化（变化都产生在直线上面）。所以如果按照离直线从左到右，再从下到上排序（以当前直线为新的 \(y\) 轴排序）的话，每次的旋转中心的相对大小都不变。

具体实现的时候，我们可以按照初始坐标 \((x,y)\) 的 pair 排序，然后依次考虑每个有效的斜率，按照当前斜率依次改变点的相对位置。每转到一个斜率 \(k\) 时，我们画图可以发现以 \(k\) 为斜率且经过至少两个点的直线，它上面的点的相对位置是连续的一段，正好要被 reverse 一次。并且如果该直线经过了上一个旋转中心，那么就要更新旋转中心，否则不用。我们只用计算一个 \(2\pi\) 周期内的斜率。这样的直线的条数不会超过点对的数目，所以复杂度是 \(\mathcal{O}(n^{2})\) 的。

J. Schedule

题目大意：有 \(n\) 件任务和若干台机器，第 \(i\) 件任务的起始和终止时间分别为 \(s_i\) 和 \(e_i\)。两个时间冲突的任务不可以在同一台机器上进行。对于每台机器，它的工作时间定义为最后一个任务的终止时间 \(e_{last}\) 与第一个任务的开始时间 \(s_{first}\) 的差 \(e_{last}-s_{first}\)。求最少需要多少台机器，在此前提下，最小化总的工作时间。

题解：我们离散化所有的时间点，然后维护每段时间被任务覆盖的次数（维护 \([s_i,e_i]\) 的差分序列）。显然我们取最大的覆盖次数，就是最少需要的机器数量，设为 \(\text{cnt}\)。

剩下的就是求最少的总工作时间。我们贪心地考虑，一定在当前的机器数量不能满足的时刻，我们打开一台机器，并且在不需要的时刻，关闭一台机器。也即，我们要对 \(\forall i \in [1,\text{cnt}]\)，求出 \(S_i\) 等于第一个覆盖次数大于等于 \(i\) 的时刻，\(E_i\) 表示最后一个覆盖次数大于等于 \(i\) 的时刻。那么答案为 \(\sum\limits_{i\in[1,\text{cnt}]}(E_i-S_i)\)。

K. Two Paths

题目大意：裸的求次短路。

题解：

法一：A*暴力一下。

法二：用 spfa 来 dp，用最短路更新次短路的时候，判断一下有没有更新过最短路，有就不行。然后再正常地最短更新最短，次短更新次短。

Replay and Summary

Replay

原来金策工业综合大学真的是朝鲜人啊，还以为是金策的粉丝们呢。

朝鲜人出题真难啊。