CuteCube Garden - Testing Round 1 题解

A. Common Tangents

初中几何结论

首先两个圆有无穷多条切线当且仅当两圆完全重合，即 $(x_1,y_1,r_1)=(x_2,y_2,r_2)$ 。

记两圆圆心距 $d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$ ，有下面的结论：

$d \le \left| r_1 - r_2 \right|$ ，内含， $0$ 条公切线。
$d = \left| r_1 - r_2 \right|$ ，内切， $1$ 条公切线。
$\left| r_1 - r_2 \right| \le d \le r_1 + r_2$ ，相交， $2$ 条公切线。
$d = r_1 + r_2$ ，外切， $3$ 条公切线。
$d \ge r_1 + r_2$ ，外离， $4$ 条公切线。

但是 $d$ 的计算有浮点运算，怎么办？

$d$ 别开根号，把 $r_1 + r_2$ 和 $\left| r_1 - r_2 \right|$ 平方了再比较。

B. Max-flow on a Grid

观察 +bfs

首先注意到，答案肯定不会大于 $2$ 。

哪怕是一个障碍都没有的网格，也能这么放:

.#...
#....
.....
.....
.....

所以，答案只有 $0$ ， $1$ 或者 $2$ 。现在的问题是， $0$ 很好判断，到不了右下角就行。 $2$ 待会再说， $1$ 怎么判断。

目前我自己能想到的比较可行的做法应该只有下面这种：

如果一个网格被截断，说明对于障碍物来说，存在一条从左边或者下边 八连通 到右边或者上边的通路。

举几个例子：

.....
.####
#....
.##..
..#..

这就是左边或者下边八连通到右边或者上边，答案是 $0$ 。

.....
...##
#....
.##..
..#..

这种显然答案是 $1$ ，怎么找到具体的格子呢？

从左边和下面所有格子开始第一次八向 bfs，标记所有遇到的障碍为 $1$ 。

从右边和上面所有格子开始第二次八向 bfs，标记所有遇到的障碍为 $2$ 。

然后枚举每个空格子，看它周围八格 $1$ 和 $2$ 是不是齐的。

.....
...22
1....
.11..
..1..

有了这个方法，一开始也不用对空格 bfs 看能不能走到右下角，在第一次做八连通 bfs 时就可以看障碍有没有直接到右边或者上边。

如果枚举空格后没有周围 $1$ 和 $2$ 齐的点，那么答案就是 $2$ 。此时只要往 $(1,2)$ 和 $(2,1)$ 一放完事。（答案为 $2$ 时，这两个点肯定是空的。）

C. Dig Two Treasures

按位确定

$20$ 次就是 $2$ 次 $log1000$ 。

首先，既然只有刚好一次才能获取信息，我们想的是，应该去找那种两个 $1$ 不会在一起的下标。什么信息两个 $1$ 会不一样呢？两个 $1$ 下标是不一样的，所以至少有一位不一样。

第一步：我们枚举每个位置，把所有第 $1$ 位是 $0$ （或者 $1$ ，随意）、第 $2$ 位是 $0$ 、……、第 $10$ 位是 $0$ 的下标全部拉出来问，如果回答是 $0$ ，说明这两个下标这位是一样的；否则就不一样。

肯定有一位不一样，但是不要 break，先全部问完。

第二步：举个例子说明：比如第 $3$ 位两者不同，然后那么所有第 $3$ 位为 $0$ 的下标一定有且只有一个 $1$ 。我们在 这堆下标 里继续问，把第 $1$ 位是 $0$ 的下标、第 $2$ 位是 $0$ 、……、第 $10$ 位是 $0$ 的下标再拉出来问一下（第 $3$ 位无所谓是否再问一遍）。

如果回答是 $1$ ，由于最多一个 $1$ ，说明这个 $1$ 下标的这一位是 $0$ ，否则这一位就是 $1$ 。

这样我们相当于把一个 $1$ 按位确定了，但是另外一个怎么办？此时第一次问完的作用体现了：我们知道了每一位这两个下标相同还是不同。

D. Flipping Chess

博弈 dp+ 状压

首先这么复杂的规则排除贪心。

那么考虑状压，用每一位表示这个棋子是否还存活。

对于博弈的过程，我们本身不需要考虑这么多，由于数据小，直接枚举选的棋子，按照规则然后看去掉相对应的棋子是否是对于对手来说的必败态。

那这里就要注意了，这里平局补偿规则导致了双方是不对称的，所以我们必须 dp 的时候再套一层维度：用 $01$ 表示当前操作的玩家（或者理解为先后手）。

时间复杂度： $O(t \cdot 2^{n+m}nm)$

E. Average Depth of a Random Tree

推一下式子：

先定义添加的第 $i$ 个节点的期望深度为 $E_i$ 。前面所有的节点期望深度总和为 $S_i$ ，平均为 $A_i$ 。

E_{i+1}=A_i+1

E_{i+1}=\frac{S_i}{i+n}+1

S_{i+1} - S{i}=\frac{S_i}{i+n}+1

S_{i+1}=\frac{S_i(i+n+1)}{i+n}+1

\frac{S_{i+1}}{i+n+1}=\frac{S_i}{i+n}+\frac{1}{i+n+1}

A_{i+1}=A_i+\frac{1}{i+n+1}

这个结论异常简洁，每加一个点，新树的深度增加量是 $\frac{1}{\left| T' \right|}$ ，其中 $\left| T' \right|$ 是新树的节点数。

然后 $A_1=\bar{D}(T)+\frac{1}{\left| T \right|+1}$ ，意思就是说第一个新节点的增加量是原树的节点数 +1 分之一。

一路递推下去，记 $A_0$ 是原树平均深度：

A_m=A_0+\frac{1}{n + 1}+\frac{1}{n + 2}+\cdots+\frac{1}{n + m}

记 $H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$ ：

A_m=A_0+H_{n+m}-H_n

最终式子就是这么简单，预处理 $H_n$ 。

至于 Easy version，把暴力一路 dp 的做法放过去了。

F. CuteCube’s Challenge 1:Data Structure

时间戳线性基 + 高斯消元正交化

假设看这题的都会常规的线性基。

线性基有个加强的用法：时间戳线性基，在每次加入元素之后，记录加入的顺序，调整每个基直到它是最新的元素。

然后要再知道怎么高斯消元（或者叫正交化），高斯消元后按位贪心一路下来，用了哪几个基就是第几小。

有没有 0 的话，看是不是线性相关，看情况答案 +1。

~~反正会的人自然会，出题人不想自己介绍了~~

复杂度： $O(nL+qL^2)$ ，其中 $L$ 是线性基的大小。

Dashboard - CuteCube Garden - Round 2 (Div. 3) - Codeforces

A

C

把行列奇偶分开看，4 组，每组最多是国际象棋黑白染， $\lceil \frac{r c}{2} \rceil$ 。

H

一个 $p\to(p+A_{p})$ 的内向基环树森林，多次查询一个点向后延伸若干步的不同的点权数量。

倍长后断环为链，那么这个内向基环树森林就退化为一个森林。

在树上处理是容易的。

将所有查询离线存储，挂载在较深的节点 $v$ 上。
使用一个数组 pos[c] 记录颜色 $c$ 目前在链上最深所在的深度。
使用 BIT 维护每个深度上是否包含某个颜色的最深出现。如果是，该深度的值为 $1$ ，否则为 $0$ 。
遍历挂在节点 $v$ 上的所有查询 $(u, v)$ 。此时树状数组中 [dep[v]-k, dep[v]] 区间和，就是这段路径上不同颜色的数量。
回溯的时候删掉。