Contest Info

date: 2019.03.27 16:14-21:14

practice link

Solutions

A. Alice and Path

签到题。

B. John and the Magic Box

题目大意：交互题。定义一种\(50\)位的二进制整数域上的二元运算\(x\odot y\)，满足交换律与结合律。提供一个黑盒交互接口，调用一次可以得到一次运算的结果。给出一个长度为\(n\le2000\)的数列\(0\le a_i<2^{50}\)，给定一个整数\(k\)，满足\(2\le2^k\le n\)，接下来\(q\le n\)组询问，每一组给出\(k\)个不同的整数\(1\le d_i\le n\)，问数列中除这些位置之外的数，经过该二元运算合并起来的结果是多少？要求调用交互接口的次数不超过\(4(n+q+q\cdot k)\).

题解：

因为该二元运算满足交换律与结合律，我们可以先将数列random_shuffle一下，这样所有询问中删去的位置都是随机的。

将数列按长度\(\log{n}\)进行分块，块内预处理前缀和与后缀和，然后用一个分治来维护所有整块的区间和并记录下结果。具体来说，就类似点分治，记录该层每个位置到\(Mid\)的区间和（两边只有一边的和包含\(Mid\)），然后分别去两边递归。这样对于\([l,r]\)的区间和，只要找到\(l\)和\(r\)被分开的那一层，做一次二元运算即可。

接下来分析接口调用次数：预处理时，前后缀一共\(2n\)次；分治时，块总数\(m=\frac{n}{\log{n}}\)，不超过\(m\log{m}\)次，大约是\(n\)次；每组询问，大多数情况，每块最多一个坏点，可以通过预处理好的前缀和与后缀和计算，这里是\(q\cdot k\)次，对于小概率情况，需要最多\(\log{n}\)次暴力计算这一块，先不考虑计算这一部分；整块的区间最多\(k-1\)个，通过预处理好的分治，就\(q(k-1)\)次；然后合并这些数，需要\(q(2k-2)\)次；总共用了约\(3n+4q\cdot k\)次，多余的次数，足够用来处理小概率情况的暴力计算块内的开销。

C. Anti-Distance

题目大意：一个无限的网格，对 \(\forall i,j\in\mathbb{Z},(2i+j,i-2j)\) 有障碍。问两个格子之间的最短路。

题解：我们先把问题规约到从左下角走到右上角，且与 \(x\) 轴成的角度不超过 \(45^{\circ}\) 角，如果不满足，需要沿各个轴翻转一下。

翻转之后，可能会有两种图案：

.*....*....*....*....*....*....*....*...
...*....*....*....*....*....*....*....*.
*....*....*....*....*....*....*....*....
..*....*....*....*....*....*....*....*..
....*....*....*....*....*....*....*....*
.*....*....*....*....*....*....*....*...
...*....*....*....*....*....*....*....*.
*....*....*....*....*....*....*....*....
..*....*....*....*....*....*....*....*..
....*....*....*....*....*....*....*....*
.*....*....*....*....*....*....*....*...
...*....*....*....*....*....*....*....*.

..*....*....*....*....*....*....*....*..
*....*....*....*....*....*....*....*....
...*....*....*....*....*....*....*....*.
.*....*....*....*....*....*....*....*...
....*....*....*....*....*....*....*....*
..*....*....*....*....*....*....*....*..
*....*....*....*....*....*....*....*....
...*....*....*....*....*....*....*....*.
.*....*....*....*....*....*....*....*...
....*....*....*....*....*....*....*....*
..*....*....*....*....*....*....*....*..
*....*....*....*....*....*....*....*....

我们可以看出，有一些从左下到右上的条带。在一个条带内部，或者从一个下方的条带走到一个上方的条带，都可以走出曼哈顿距离。而如果要从一个上方的条带走到一个下方的条带，每跨过一个条带必须多走两步。我们只需计算一下起点和终点分别在哪个条带即可。

E. Coin Tournament

题目大意：有\(n+m\)个人排成一行，当剩余人数大于\(1\)时进行一轮游戏，每轮游戏，处于当前编号最大的位置\(k\)的人要和\([\frac{k}{2}]\)位置的人进行比赛，有\(\frac{1}{2}\)的概率获胜，\(\frac{1}{2}\)的概率失败，败者退出，胜者占据\([\frac{k}{2}]\)这个位置，问后\(m\)个人获得最终胜利的概率之和。

题解：建出比赛的胜者树，每个叶子获胜的概率为\(2^{-depth}​\)，对每个叶子单独计算求和即可。

F. Fizz and Buzz

签到题。

G. Game on Tree

题目大意：给定一棵有根树，两个人在上面玩游戏。先手每次可以选择一个非根的叶子结点，将它打上标记；后手每次可以走一步到相邻节点（也可以不走，起始在根）。后手如果走到一个未标记的叶子节点，那么获胜。

题解：显然后手不会停住不走，每一步一定是朝着叶子的方向走，不会走回头路。定义 \(dp_i\) 表示后手在 \(i\) 点的时候，先手要获胜至少需要预先删除的叶子节点的个数。那么叶子结点的 \(dp\) 值为 \(1\)。其余点的 \(dp\) 值为儿子节点的 \(\max(0,\sum dp-1)\)。如果根的 \(dp\) 值为 \(0\)，那么先手获胜。

H. Jack and Jill

签到题。

I. Laws

题目大意：你有一个数 \(x\)（\(1\le x\le 10^9\)）。你每次可以将其加 \(1\)，或者除以 \(2\)（如果能整除），或者除以 \(3\)（如果能整除）。现在让你用最少的加 \(1\) 操作将其变为 \(1\)。

题解：bfs 求最短路。注意除以 \(2\) 和除以 \(3\) 是边权为 \(0\) 的点，所以要 push_front。并且每次扩展边权为 \(0\) 的时候，不能只枚举 \(\frac{x}{2}\) 和 \(\frac{x}{3}\)，而是要枚举所有的 \(\displaystyle \frac{x}{2^a3^b}\)。最短路至多是 \(\mathcal{O}(\log x)\) 的，每次扩展 \(\mathcal{O}(\log^2 x)\) 个点，总复杂度 \(\mathcal{O}(\log^3 x)\)。

J. Cubic Path

题目大意：定义一个 \([0,2^{n})\) 中的整数组成的序列 \(\{x\}_{1}^{m}\) 合法，当且仅当该序列的每个元素互不相同，且对每个 \(1\le i<m\)，\(x_{i}\) 和 \(x_{i+1}\) 恰有一个二进制位不同。定义一个序列 \(x\) 是好的，当且仅当它合法，且不存在另一个合法的真子序列，开头结尾与 \(x\) 相同。求最长的好序列。\(n\le6\)。

题解：我们证明，一个序列是好的，当且仅当它任意两个不相邻的元素不同的二进制位数不为 \(1\)。这个条件显然是必要的，否则我们只要把这两个元素中间的序列删去，仍然是一个合法的序列。对于充分性，我们从 \(x_{1}\) 只能走到 \(x_{2}\)，\(x_{2}\) 只能走到 \(x_{3}\cdots\)。利用这个性质暴搜即可。

K. Red-Black Tree

题目大意：有一个\(n\le3000\)个点的二叉树（每个点最多两个儿子），并且认为每个节点空的儿子指向一个哨兵节点void。每个点可以是红色和黑色两种颜色，void节点固定为黑色。问是否有一种染色方案，使得不存在一条边两端的点都是红色，并且void到根的每条路径上的黑色节点个数相同。

题解：令dp[0/1][i][j]为\(i\)的颜色为0/1，子树中所有void到\(i\)的路径上的黑色节点数为j的可行性布尔状态。则枚举左右儿子的颜色和黑色节点数转移即可。