ucup 随机记录

这场打得不错，就记录一下做的题吧，以及随便估个难度。

• 11.9

E. Left Shifting 3 (*800)

签中签，不难发现循环位移的作用只有把原本序列的一段后缀和前缀能形成的 nanjing 拼上，所以移动不超过 $7$ 位，具体实现时开大一点保险。

G. Binary Tree (*1600)

由于只有 $\log n$ 次操作，于是方向就是能否每次确定关键点在一个大小至多 $\frac n2$ 的子树内。想到找重心。考虑询问重心的两个儿子 $x,y$，若返回 $0$ 则在 $x$ 的子树中，若为 $2$ 则在 $y$，否则在整棵树去掉 $x,y$ 的子树中。

由于是二叉树，所以最后一种情况剩下的树大小为子树大小 $+1$。注意当 $siz=\frac n2$ 时会寄，所以一定要将 $siz=\frac n2$ 的子树放在 $x$ 或 $y$ 的位置。以及要特判当前度数为 $1$ 的情况。

感觉做这题时状态极好，居然一发了。

B. Birthday Gift (*1800)

一开始的想法是先把能做的都做了，然后剩下的再处理。然后发现处理剩下那一部分也是困难的。怎么办？手玩一下，发现这个两个相邻的相同的一起消掉，这样的形式实际上不太好。

突然对上脑电波发现可以套路地奇数位反转，然后变成每次选相邻的不同的消掉。这样就之和 $0,1$ 数量有关了。后面的就简单了。

yhd 说他认为这题很困难，事实上我也真忘了是怎么想到奇数位翻转的。

C. Topology (*2400)

被硬控了/ll 首先求拓扑序方案是简单的。考虑怎么确定一个点排名。设 $dp_{u,i}$ 表示已经处理完了除了 $u$ 子树内的所有点以及 $u$，当前 $u$ 的排名为 $i$ 的方案数。考虑如何转移，设 $v$ 为 $u$ 的儿子，则先要插入所有除了 $v$ 之外的 $u$ 的儿子的子树，方案数为这些子树的拓扑序数量乘上一个组合数，前者可以预处理。

设这些方案数为 $w(u,v)$，则转移为 $dp_{v,j}=\sum_{i<j}dp_{u,i}\times w(u,v)$。显然可以前缀和做到 $O(n^2)$。

树形 dp 严重占模。

• 11.16

F. The Hermit (*1700)

考虑对每一个 $i$ 算 $i$ 被删掉的贡献。若 $i$ 被删掉，则 $\forall j<i$ 也要被删掉，并且剩下的数必须全部是 $i$ 的倍数。对于第一个条件，发现把被删掉的 $j<i$ 放进序列 $a_m$ 中，从小到大排序，则一定有 $a_i|a_{i+1}$，于是 $m\le O(\log n)$。于是预处理 $f_{i,j}$ 表示当前 $a$ 的长度为 $j$，$a_j=i$ 的方案数。枚举 $i$ 的倍数转移，复杂度 $O(n\log n\ln n)$。

考虑如何统计答案，先枚举 $i$ 和 $a$ 的长度 $j$，则 $>i$ 的 $i$ 的倍数有 $\left\lfloor\frac ni\right\rfloor-1$ 个，其中要选 $m-j$ 个，乘上个组合数即可。

B. The Magician (*1200)

弱智题，一开始没几个人过的原因大概是题面过长。考虑先只用前四种牌，暴力搜索最后每种花色有多少个，合法的条件是 $\sum c_i=\sum c_i'\wedge c_i'\le c_i+a_i\times 3$，$c_i$ 是该花色数量，$a_i$ 是是否有这种牌。然后考虑剩下两种，本质上都是将一种花色转化为其他任意一种，暴力 $4^4$ 枚举即可。

E. The Chariot (*1500)

大粪分讨。首先大致的策略就是三种：每次都坐 $X$，每次坐 $X+Y$，坐完 $X+Y$ 后一直坐。只需要对最后一段进行分讨，因为有时候最后可能不重新坐车而是直接坐到终点更优。细节不想写了。

D. The Emperor (*2300)

挺有意思的题。考虑一个函数 $solve(i)$，返回值为一个 pair $(x,y)$。$x$ 表示进行完操作 $i$ 的 push $a$ 之后，把 $a$ pop 的操作进行完后到的操作。$y$ 表示这其中经过了多少次操作。

考虑如何求 $solve(i)$。首先考虑 push $a$ 之后到的操作，如果这一步直接可以 pop $a$ 就结束了，否则若 push 一个 $b$，那显然先要把 $b$ pop 出来再考虑下一个操作是否是 pop $a$。这样不断跳直到找到一个 pop $a$ 的操作。注意到若有一个 $b$ 出现多余一次，说明这里进入了循环，无解。所以这样最多跳 $O(n)$ 次。使用记忆化搜索则求所有 $solve(i)$ 的复杂度为 $O(n^2)$。

求答案也是类似的，如果当前操作是结束则结束，否则下一个操作是 push $a$ 则要跳到 pop $a$ 后的位置继续找，直到找到结束位置或者无解。