Div1

Div2

从一月份一直咕到现在的一场比赛 /kel

ConneR and the A.R.C. Markland-N

暴力往两边找即可。

代码

JOE is on TV!

显然每次淘汰掉刚好一个人是最好的。

答案即为 $\sum_{i=1}^n\frac{1}{i}$。

代码

NEKO's Maze Game

维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即可。

代码

Aroma's Search

因为数据点的坐标增长很快，所以我们完全可以把 $10^{16}$ 内的数据点都找出来。这样子只需要模拟一遍即可。

代码

Xenon's Attack on the Gangs

首先要求的东西实际上等于
$$
\sum_{i=1}^n\sum_{1\leq u<v\leq n}[\operatorname{mex}(u\to v)\geq i]
$$
后面的东西的意思就是路径上恰好包含 $0\cdots i-1$ 这些数的路径数。

不难发现一个性质，即最优方案中 $0\cdots i-1$ 一定构成一条路径，且成一个单谷序列。

考虑 DP。设 $dp_{i,j}$ 表示 $i\to j$ 路径上放了 $0\cdots len-1$ 这些数时答案的最大值。

记 $f_{i,j}$ 为以 $i$ 为根时 $j$ 的父节点，$sz_{i,j}$ 为以 $i$ 为根时 $j$ 的子树大小，不难得到转移
$$
dp_{i,j}=\max\left\{dp_{f_{j,i},j},dp_{i,f_{i,j}}\right\}+sz_{i,j}\times sz_{j,i}
$$
直接记搜即可，复杂度 $\mathcal{O}(n^2)$。

代码

Chaotic V.

显然可以将 $k_i$ 相同的点放在一起处理，则点数变为 $5000$ 级别。

考虑如何从 $1$ 走到 $n!$。将 $n!$ 质因数分解并把所有质因数从大到小排序，然后依次乘过去即可。

既然要计算树的重心，考虑从 $1$ 开始走，每次向 $size$ 最大的子树移动，直到 $maxsize\leq \frac{n}{2}$。

现在的问题是如何计算每个点在哪颗子树中，显然在它的最大质因子对应的子树中。

实现时需要求出 $n!$ 的每个质因子的次数，做一个前缀和即可；然后对每个数维护一个指针表示最大质因子即可。

代码

Rin and The Unknown Flower

首先查一下 CC、CH、CO、HO、OO。这样子我们就能确定 $[2,n-1]$ 中所有字符（没有确定的位置一定是 H）。此时如果 $1$ 没有确定，则它不可能是 C；如果 $n$ 没有确定，则它不可能是 O。这样子只有 $4$ 种情况，做 $3$ 次长度为 $n$ 的查询即可。

这样子总花费是 $1.25+\frac{3}{n^2}$ 的，当 $n\geq 5$ 时可以过。

所以我们特判 $n=4$ 的情况。先询问 CC、CH、CO、HO。如果 $2,3$ 已经确定，而 $1,4$ 未被确定，则 $1$ 不可能是 C，所以只有 $6$ 种情况，做 $5$ 次查询即可，花费为 $1.3125$；否则我们再查询 OO，即可确定 $2,3$：如果 $2,3$ 是 HH 则再询问 HHH 即可得到 $1,4$，花费约为 $1.36$，否则 $1$ 和 $4$ 一定确定了一个，做 $2$ 次查询即可，花费为 $1.375$。

代码

Nora's Toy Boxes

如果 $a_i|a_j$，则从 $i$ 向 $j$ 连一条边。于是我们可以对每个弱连通块算方案数，然后用组合数合并。下面均是对弱连通块讨论。

一个显然的性质是如果 $a_i|a_j$，$a_j|a_k$，则 $a_i|a_k$。那么某次删除操作中的点 $i$ 一定可以是一个没有入度的点。我们把没有入度的点记做集合 $S$，有入度的点集记做集合 $T$。

现在先考虑最多能删掉多少个点。显然没有入度的点是删不掉的；其次，$T$ 中的点一定可以被删成只剩下任意一个点。证明略。

然而这个删点并不是很好做。我们反过来，看成一开始只有 $S$ 中的点和 $T$ 中的一个点，每次可以选点 $i,j$，如果同时存在边 $(i,j)$ 和 $(i,k)$ 则可以加入 $k$。

再转化一下，看成一开始 $S$ 中的点都没有标记，每次可以选择一个 $T$ 中的点并把所有能到达它的 $S$ 中的点打上标记，然后向 $T$ 中加入一个有标记的 $S$ 能到达的点。

然后我们来考虑 $S$ 的大小。首先显然 $S$ 中的数都 $\leq 30$，否则无法构成弱连通图；其次，$S$ 可以看成反链，而我们可以构造出 $(1,2,4,8,\cdots),(3,6,12,\cdots)$ 这样的 $15$ 条链覆盖整个图，所以有 $|S|\leq 15$。

于是可以考虑状压 DP。设 $dp_{i,j}$ 表示 $i$ 中的点有标记，已经加入了 $j$ 个点的方案数。转移有两种：

• 加入了一个能到达它的点都被标记了的点：我们需要预处理出 $c_i$ 表示能被到达的点集是 $i$ 的子集的点数，转移即为
  $$
  dp_{i,j}\times(c_i-j)\to dp_{i,j+1}
  $$

• 加入了一个能到达它的点没有都被标记的点：直接枚举这个点即可。

一个暴力是枚举一开始在 $T$ 中的点，然后跑上面这个 DP；然而完全没有必要，我们只要把 $dp_{0,0}$ 设为 $1$ 跑一遍即可。

代码