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

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

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

所以我们特判 $n=4$ 的情况。先询问 CCCHCOHO。如果 $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$ 跑一遍即可。

代码

最后修改:2020 年 10 月 24 日 04 : 43 PM