Contest Info

date: 2017.10.04 13:15-18:15

practice link

Solutions

A. 2016

题目大意：定义一个正整数 \(x\) divisorful 当且仅当满足 \(y<x\) 且 \(\sigma(y)>\sigma(x)\) 的正整数 \(y\) 不超过 \(1\) 个，求第 \(k\) 个 divisorful 的正整数。若它大于 \(10^{18}\) ，则输出 \(-1\) 。

题解：感觉这样的数很少（实际上也就 \(1000\) 多个），我们只需要把 \(10^{18}\) 以内所有这样的数求出来就好了，下面给出标程的求法。

我们只考虑由前若干个质数组成的数，那么开始时我们只有 \(1\) 。然后依次把 \(2,3,5,7,\cdots\) 添加进去。例如，我们添加 \(2\) 之后，就得到了 \(1,2,4,\cdots,2^{59}\) 。注意在添加质数的时候，我们可以顺便计算出每个数的约数个数。添加完了以后，我们把这些数从小到大排序，然后枚举来删去不合法的数。具体来说，如果一个数 \(x\) 的约数个数 \(\sigma(x)\) ，比当前已经枚举过的，约数个数第二大的 \(y\) 小，就将它删去。之后我们再以剩下还没被删的数为基础，添加下一个质数。如果添加某个质数后集合没有发生变化，就可以结束程序了。

B. Airports

题目大意 ：求曼哈顿距离最大生成树的最小边。

题解 ：Manhattan 距离转 Chebyshev 距离。我们将点 \((x,y)\) 变为 \((\frac{x+y}{2}, \frac{y-x}{2})\) ，那么后者的 Chebyshev 距离为：

\[ \max\left(\left|\frac{x_1+y_1-x_2-y_2}{2}\right|,\left|\frac{y_1-x_1-y_2+x_2}{2}\right|\right)\\ =\frac{1}{2}\max\left(\left|(x_1+y_1)-(x_2+y_2)\right|,\left|(x_1-y_1)-(x_2-y_2)\right|\right) \]

我们知道前者的 Manhattan 距离是上式的两倍。那么我们将所有点按照 \(x+y\) 从小到大排序，然后枚举每个点，将它与最小的点，和最大的点连边。再对 \(x-y\) 也做一次同样的操作。我们只需要在这些边上做一次最大生成树（正确性？）就可以了（或者二分答案验证）。证明大概就是，如果需要使用中间两个点 \(i,j(i<j)\) 的边，那么这两个点一定已经通过 \(i\to n\to 1\to j\) 连通了。

C. Jump

题目大意 ：给定一个无限的数轴上的 \(n(n\leq 200)\) 个整点 \(\{a_i\}(0\leq a_i\leq 10^4)\) 。给出 \(Q(Q\leq 10^5)\) 次询问，每次询问给出两个点 \(s,t\) ，问最少经过多少次操作从 \(s\) 到达 \(t\) 。一次操作定义为选择一个 \(i\) ，然后从当前位置 \(x\) 跳到位置 \(2a_i-x\) 。

题解 ：假设我们选择了操作序列 \(i_1,i_2,\dots,i_k\) ，初始位置为 \(s\) ，容易写出经过这些操作之后的位置 \(t\) 满足：

\[ 2\big(a_{i_1}-a_{i_2}+a_{i_3}-\cdots+(-1)^{k-1}\cdot a_{i_k}\big)=s+(-1)^{k-1}\cdot t \]

也即：

\[ \sum_{j=1}^k(-1)^{j-1}\cdot a_{i_j}=\begin{cases} \frac{1}{2}(s-t), &k \text{ is even}\\ \frac{1}{2}(s+t),&k \text{ is odd} \end{cases} \]

显然有 \(s,t\) 不同奇偶的时候无解。那么有解的时候，我们就是要找到最小的 \(k\) 使得上式成立。我们将步数分为奇偶两类，然后对左边用 bfs 求一个最短路即可。

D. Merge

题目大意：给你两个 \(1\) 到 \(n\) 的排列，将它们合并成一个长度 \(2n\) 的数列。每次任选两个排列中一个非空的，从它的左侧取出一个数，放到新数列的右端。问最后的数列有多少种可能。

题解：原题 。给出题解的做法。

这题的关键之处其实就在于如何去重。我们称一个数列是 good 的，当且仅当它可以用两个相同的子排列合并得到，并且它的任何一个前缀都不满足该条件。从这个定义我们很容易发现，一个数列是 good 的，那么它显然既是极大的，也是极小的。考虑它被合并得到的过程，发现我们可以交换两个子排列的选择顺序，于是它会被计算 \(2\) 次。

我们设 \(f[i][j]\) 表示合并 \(A[1:i]\) 和 \(B[1:j]\) 的答案。最后我们要求的便是 \(f[n][n]\) 。那么有：

\[ f[i][j]=f[i-1][j]+f[i][j-1]-\sum_{k=1}^{\text{lcs}(A[1:i],B[1:j])}g[k]\cdot f[i-k][j-k] \]

其中，\(\text{lcs}(s,t)\) 表示 \(s,t\) 的最长公共后缀长度。我们在枚举转移之后，再通过枚举 \(k\) 来枚举末尾长度为 \(2k\) 的 good 数列，以此来达到去重的目的。这里的 \(g[k]\) 表示长度为 \(2k\) 的 good 数列个数，它的计算方法如下：

设 \(G[i][j]\) 表示两个 \(1\sim i\) 的排列，合并得到不同的长度为 \(2i\) 的 good 数列，且第一个排列的 \(i\) 在数列第 \(j\) 个位置的方案数。同时还要保证每个数字都是先从第一个排列中选取。初值为 \(G[1][1] = 1\) ，\(2\leq i\) 时转移为：

\[ G[i][j]=\begin{cases} &\sum\limits_{k=1}^{j-1}G[i-1][k],&j<2i-1\\ &0,&j\ge2i-1\\ \end{cases} \]

注意为了保证满足 good 数列的定义，\(j\) 不能取到 \(2i-1\) 。而 \(g[k]=\sum_{j=1}^{2k-2}G[k][j]\) 。

coldwater’s comment

\(g[n]\) 的另外一种求法：首先不考虑前缀不是 good 数列的限制，那么这样的序列就相当于一个 \(1\sim n\) 的合法入队出队序列（第一个子排列的数字表示进队，第二个表示出队，例如 \(1,2,x,x,3,x\)）。它的方案数是 Catalan 数 \(C_{n}\) 。然后我们用归纳法证明，考虑前缀不能为 good 数列时，答案为 \(C_{n-1}\) ：

• \(n=1\) 时显然成立。
• \(n>1\) 时， \(g[n]=C_{n}-\sum_{i=1}^{n-1}g[i]C_{n-i}=C_{n}-\sum_{i=0}^{n-2}C_{i}C_{n-i-1}=C_{n-1}\) 也成立。

E. Mirror Rice Cake

签到题

F. Number Cards

题目大意：你有无限张卡牌，编号从 \(1\) 到无穷。现在有 \(n\leq 20\) 张卡牌的颜色被限定了。问满足下列条件的 \(M\) 有多少个：编号在 \([1,M]\) 内的卡牌颜色都相同， \([M+1,2M]\) 内的颜色都相同且和 \([1,M]\) 内的颜色都不相同， \([2M+1,3M]\) 内的颜色都相同，且和 \([1,2M]\) 内的颜色都不相同，\(\cdots\)

题解：不妨把所有位置的序号减一。若给定的卡片颜色完全相同，显然 \(M\) 有无限种可能。若存在两张相同颜色的卡片，它们中间有一个异色的卡片，那么 \(M\) 没有符合条件的取值。否则，一对相邻的 \((a_{i},c_{i})\) 和 \((a_{i+1},c_{i+1})\) 满足：

\[ \begin{cases} &\lfloor\frac{a_{i}}{M}\rfloor=\lfloor\frac{a_{i+1}}{M}\rfloor,&c_{i}=c_{i+1}\\ &\lfloor\frac{a_{i}}{M}\rfloor<\lfloor\frac{a_{i+1}}{M}\rfloor,&c_{i}\neq c_{i+1}\\ \end{cases} \]

由于对每个数 \(a_{i}\) ，我们可以在 \(\mathcal{O}(\sqrt{a_{i}})\) 的时间内知道它除以每个数的商的情况（整除），所以我们只要暴力地求解（不）等式就好了。

G. Paint

题目大意：对一行长为 \(n\le10^9\) 的白色格子进行 \(k\le4\) 次操作。第 \(i\) 次操作选择连续的 \(a_i\le n\) 个格子，将被选中的格子全部染成黑色。求 \(k\) 次操作后可能有多少种不同的局面，模 \(10^9+7\) 输出。

题解：先把 \(\{a_i\}\) 进行划分，然后对划分之间进行排列。每一个划分表示一段连续的黑格子，显然这段黑格子可行的长度范围是一个区间，下界为划分中最大的 \(a_i\) ，上界为 \(\min(\sum_{a_i\in s} a_i,n)\) 。不同的划分表示的黑格子段不可以相邻。

对于每一个划分方案以及排列，它的合法的方案就被转换为了下面这个方程的非负整数解：

\[ x_1+y_1+x_2+y_2+\cdots+x_k+y_k+x_{k+1}=n\\\big(x_1,x_{k+1}\ge0,x_2,\cdots,x_k\ge1,y_i\in[\text{low}_i, \text{up}_i]\big) \]

其中，\(y_i\) 表示第 \(i\) 个划分的黑格子长度。上式的难点在于下界，我们可以替换变元来去掉下界，将其转化成下面的方程：

\[ x_1+y_1+x_2+y_2+\cdots+x_k+y_k+x_{k+1}=n-k+1-\sum\limits_{i=1}^{k}\text{low}_i\\\big(x_1,\cdots,x_{k+1}\ge0,y_i\in[0, \text{up}_i-\text{low}_i]\big) \]

然后我们对其中的上界条件的满足状态进行容斥（容斥不满足限制条件的情况，然后又可以通过替换变元来去掉下界），就可以转化为简单的隔板法计算了。

但是，即使是不同的方程，也会有一些相同的解，如果直接计算就会重复。因此，我们要在最外层首先对方程进行容斥。虽然方程的数量可能很多，但是满足多个方程的约束条件的状态会很少，所以这层容斥直接用搜索来写就可以了。

H. Random Walk

题目大意：在无限大的网格上，一个人开始在原点 \((0,0)\) ，之后他要随机走 \(n\) 步。每一步等概率地选择上下左右一个方向走一步。问被他经过的点数的期望乘以 \(4^{n}\) 取模。

题解：本题重点还是在去重。不考虑重复的答案显然是 \(4^{n}(n+1)\) 。注意到，重复经过某一个点，相当于从这个点出发绕一圈又回到该点。并且一个圈（我们要求这个圈内没有其它重复的点）和一次重复是一一对应的。

考虑一个长度为 \(i\) 的圈，对于所有走 \(n-i\) 步的 \(4^{n-i}\) 种方案，再考虑每种方案上的 \(n-i+1\) 个落点，依次假设从每个点开始绕圈。这样我们会得到不同的方案，于是对于长度为 \(i\) 的每种圈，我们的答案应该减去 \(4^{n-i}(n-i+1)\) 。之后对于每个 \(i\) ，我们计算长度为 \(i\) 且没有其它重复点的圈的种数，设为 \(g(i)\) 。先考虑允许有重复点，设为 \(f(i)\) ，那么：

\[ f(n) = \sum\limits_{i=0}^{n/2}\frac{n!}{i!i!(\frac{n}{2}-i)!(\frac{n}{2}-i)!} \]

上式就是一个广义组合数，通过选择 \(n\) 步中走上下左右的步数得到。再考虑去掉非法的方案，我们枚举最后一个没有重复点的圈的大小，那么：

\[ g(n) = f(n)-\sum_{i=1}^{n-1}f(n-i)g(i) \]

最后答案为 \(4^{n}(n+1)-\sum\limits_{i\text{ is even}}g(i)4^{n-i}(n-i+1)\) 。

I. Robots

题目大意 ：平面上有 \(n\) 个沉睡的机器人，每个机器人由坐标 \((x_i,y_i)\) 和一个方向 \(\text{dir}\) （上下左右）表示。时刻 \(0\) 编号为 \(1\) 的机器人将会被唤醒，机器人被唤醒之后将会沿着 \(\text{dir}\) 的方向匀速运动。如果运动的机器人经过沉睡的机器人，那么沉睡的机器人也将会被唤醒。求时刻 \(T(T\leq 10^{18})\) 时每个机器人的位置。

题解 ：用优先队列模拟每个事件即可。注意每次事件过后，如果被唤醒的机器人与当前机器人同向，那么可以忽略被唤醒的机器人，否则会超时。之后的每次事件也同理，如果该方向已经有机器人在前方，那么可以忽略当前的机器人。

J. Ropes

题目大意 ：给定 \(n\) 个点的度数 \(\{d_i\}(d_i\in[1, 3])\)，问有多少种连边的方式让它们形成一棵树。

题解 ：Prüfer sequence 。对于点 \(i\) 来说， \(d_i-1\) 就是其在 Prüfer sequence 中出现的次数，我们的答案即为：

\[ {{n-2}\choose {d_1-1,d_2-1,\cdots,d_n-1}}=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!} \]

注意判断 \(\sum\limits_{i=1}^n (d_i-1)\neq n-2\) 时无解。

K. Stains

题目大意：给你平面上的一些整点，问你最少添加多少点能形成一个正方形网格。一个 \(K\times K\) 的正方形网格是指，满足 \((a+ci+dj,b+di-cj)(0\le i,j<K)\) 的所有点组成的图形。

题解：显然这 \(n\) 个点两两之间的差向量要满足：它们可以表示为同一组模长相等的正交基下的整系数线性组合。

​要让添加的点尽量少，就要让这组正交基的模长尽量大。我们可以按任意顺序求出相邻的 \(n-1\) 个差向量。然后用类似求 gcd 的方法来求，能用整系数同时表示两个向量的最长正交基：用两个向量中长度较小者和它对应的法向量，来尽可能（扩大若干倍）地减（或者被减）长度较大的那个向量在两个方向上的投影。目的是使得差向量的模长尽可能小。然后递归地进行下去，直到其中一个变成零向量。求出这个向量后就很简单了，我们求出这组正交基两个方向的跨度，它们的最大值就是正方形网格的边长。

L. String Modification

题目大意 ：给定两个字符串 \(s,t\) ，询问是否可以通过若干次操作，使得串 \(s\) 变为串 \(t\) 。一次操作定义为选择 \(s\) 中的一个字母，在它右边插入一个和它不同的字母。

题解 ：首先我们要注意到一个事实。假设 \(s_i\) 在 \(t\) 中对应 \(t_j\) ，那么只要 \(t_{j+1}\neq t_j\) ，我们就可以在 \(s_i\) 的后面添加任意长的任意字符。例如串 e 可以变为串 eggeeggabcd ，因为我们只需要每次选择合适的字符，在其后面添加新的字符。

考虑动态规划。我们定义 \(f[i][j]\) 表示 \(s[i...n)\) 是否可以变为 \(t[j...m)\) 。那么答案即为 \(f[0][0]\) 。再定义：

\[ g[i][j]=\bigcup_{k=j}^{m}f[i][k] \]

显然 \(g[i][j]\) 直接从 \(g[i][j+1]\cup f[i][j]\) 转移而来。当 \(s_i=t_j\) 的时候，我们考虑 \(f[i][j]\) 从何转移而来。我们可以不添加字符，那么从 \(f[i+1][j+1]\) 转移而来。添加字符的时候，需要满足 \(t_{j+1}\neq t_j\) ，那么可以从 \(g[i+1][j+2]\) 转移而来。

初值为 \(f[n][m]=1,g[n][i]=1(0\leq i\leq m)\) 。

M. Team Competition

题目大意：给 \(n(n\leq 1000)\) 个人安排训练计划。要求如下：

• 天数 \(t\in [1, n^2]\)
• 每天恰好有三个不同的人参加训练
• 令 \(f(p,q)\) 表示编号为 \(p\) 和编号为 \(q\) 的人一起训练的天数，要求对 \(\forall p,q\) 有 \(f(p,q)\) 相等

题解：当 \(n\) 为奇数的时候，我们将 \(n\) 个人放在一个环上。枚举所有的等腰三角形，我们会得到 \(n \choose 2\) 天的训练计划。容易发现，对 \(\forall p,q\) 有 \(f(p,q)\equiv 3\) ，显然每对 \((p,q)\) 会作为等腰三角形的腰 \(2\) 次，底 \(1\) 次。

当 \(n\) 为偶数的时候，情况稍微复杂一点。我们先将 \(n-1\) 个人按照上述方案安排训练。但是我们还需要给第 \(n\) 个人安排训练，显然最后的 \(f(p,q)>3\) ，再注意到现在使用的天数只有 \(n-1 \choose 2\) ，所以我们可以猜想最后 \(f(p,q)\equiv 6\) 。

这样分析之后，我们可以选择将长度（横跨的边的数量）为 \(1,2\) 的边再使用几次。我们将 \(n,i,i+1 (1\leq i < n)\) 这个三角形训练两次，将 \(n,i,i+2(1\leq i<n)\) 这个三角形训练一次。现在对于每条新加的边，它的 \(f\) 为 \(6\) 。对于之前已有的长度为 \(1\) 的边，\(f\) 增加了 \(2\)；对于之前已有的长度为 \(2\) 的边，\(f\) 增加了 \(1\) 。现在我们还需要将长度为 \(1\) 的边 \(f\) 增加 \(1\) ，将长度为 \(2\) 的边 \(f\) 增加 \(2\) ，以及将其他长度的边 \(f\) 增加 \(3\) 。要做到这一点，我们只需要枚举所有腰长度大于等于 \(2\) 的等腰三角形即可。这样，长度为 \(2\) 的边会作为腰两次，而不会作为底出现。长度为 \(1\) 的边会作为底一次。