3rd ucup 济南站 记录/题解

· · 题解

单挑的一场，但是太菜了。赛后发现有好多题我应该要做出来的。五个题只有铜。

还在补题，应该会把除了计算几何题和高精题以外的题都补了，所以持续更新。

当前进度：

A

清纯白毛小清新签到萝莉。

拿出第一个串，然后依次匹配，把失配的个数记一下，如果是 1 那么输出失配串即可，否则输出 1 1。

复杂度 O(nmk)。

J

赛时看题看了十分钟，鉴定为被榜上开局过了一车的 F 误导导致的。

因为是 \max，所以删去一个数后，密度可能发生改变的点应该与被删的点的密度相同。

所以对于一次询问 k，相当于要把密度 \le k 的点全删掉。

记录每个点的密度后排序，询问时 lower_bound 即可。复杂度 O(n \log n)。

I

有刺无刺！

简单环的本质是链加一条边，所以相当于要把树分成若干条链，使得每条边都在一条链上且链长 \ge 2。

先考虑钦定一个根后自底向上贪心构造，即对于每个节点，如果能以它为 \operatorname{lca} 构造合法的链就直接构造然后删去，直到不可构造为止。此时发现一个点最后的状态与它的儿子数量有关，如果儿子数量是偶数，那么这个点子树内的边就都在合法的链上了，否则一定会只剩下一条链，并与当前节点接在一起继续向上递归。

看到儿子数量，考虑对度数分讨。容易发现如果一个点的度数是偶数，那么令它为根做上述构造一定能构造出合法解。如果一切点的度数都是奇数，那么无解，这个很好用归纳法证明。

以偶数节点为根 dp，对每个点记录其子树删完合法链后的最深节点，然后枚举到一个点时将其子树暴力匹配即可。复杂度 O(n)。

B

官方题解有高妙做法，但是我场上没想这么多，我直接爆搜的。

注意到状态数看着就非常少的样子。注意到如果我们获得了一个 flush，那么直接用上这个 flush 一定很优。

所以直接爆搜，在爆搜的任意时刻如果出现了一种牌构成了 flush 就令其数量减少 5 即可。复杂度 O(\text{能过})。

F

场上总是要有一道 \gcd 题的嘛。

先容斥，考虑要删多少个数。把集合视作有序的，当成数列看。那么每次删的一定是最小值。

考虑一个数会被删除的条件。将集合排序后，要满足比 x 小的数有序成倍数关系（S_1 | S_2, S_2 | S_3, \dots），且比 x 大的数都为 x 的倍数。

定义「删除序列」为可能出现的被删除的数组成的有序序列，有删除序列的长度是 \log 级别的。

那么考虑直接 dp。设 f(i, j) 表示前 [1, i] 个数中 i 必被删除，删除序列长度为 j 的方案数。

很好转移，有 f(ki, j + 1) \leftarrow f(i, j)。

算出这个后统计答案。若存在以 i 结尾的长度为 j 的删除序列，那么 i 的倍数可任选，因为无论怎么选 i 都会被删去。这里的贡献是 \dbinom{\left\lfloor\frac {m}{i}\right\rfloor - 1}{n - j}。贡献累加后用总方案数减一下就能得到答案。复杂度 O(n \log n)。

以上是场切掉的题，虽然还剩一个半小时的时候去吃饭弃了，但是我也不确定最后这点时间我还能过几个题。

C

造计算机！

看数据范围大概是两 \log，因此考虑二进制拆分相关。

首先，除了最后一次操作以外，栈中元素肯定入栈一次出栈一次，所以操作数肯定是奇数。

忽视最后的 HALT，加强下条件，要求在第 i 行的命令入栈的元素必须在第 i 行出栈。然后令 n \leftarrow (n - 1) /2 ，此时 n 的意义就是除了停止指令外，经过的指令数。

然后开始造机子。下面造机子的基础为当前经过了 x 条指令，尝试用新的指令对 x 的变换。

先造加法机。若当前行数为 i，显然可以通过 POP i GOTO i + 1; PUSH i GOTO i 做到 x \leftarrow x +1。

然后尝试造乘法机。

手玩了一会发现比较难直接实现 \times 2。但是用指令 POP i GOTO i + 1; PUSH i GOTO 1 做到令 x \leftarrow 2x + 1。

有了这两种机子已经够了。现在问题为：初始有个 x = 0，每次可以令 x \leftarrow x + 1 或 x \leftarrow 2x + 1，最后要让 x=n 且操作次数尽量少。

被这里硬控了一会，感谢 @BlckCrw 救命（）

把操作倒过来，操作变成自减和自减后除以 2。那么如果 n 是偶数就让 n 自减，否则折半，这样最多两步就能令 n 减半，所以操作次数是 2\log 级别的。符合要求。模拟一遍后倒序输出操作即可。

最后输出一行 HALT; PUSH 100 GOTO 1 即可。时间复杂度 \log n。

D

为 C 写模 998244353 意义下的 SPJ。

考虑记忆化搜索。设 f(u, a) = (cnt, v) 表示以栈顶为 a 进入指令 u，最后会在 cnt 步后弹出 a 并进入指令 v。a = 0 代表空栈进入（此时 cnt 的意义是停机步数），v = 0 表示停机。在搜索的过程中记录搜索栈。

首先如果 u 是停机指令并且 a = 0 则直接返回 (1, 0)。

设 u 的前半部分是 POP c GOTO d，如果有 c = a 则返回 (1, d)。

否则要进行压栈操作。设后半部分 PUSH x GOTO y。

首先，如果二元组 (u, a) 在未弹出时又被压入栈，那就死循环了，程序不停机，直接判掉即可。

如果 (u, a) 之间搜过了，返回 f(u, a) 即可。

剩下情况按以下步骤得到 f(u, a)。

先搜索 (y, x)，得到 f(y, x) = (c_1, v)。如果 v = 0 则 f(u, a) = (c_1 + 1, 0)。

否则继续搜 (v, a)，得到 f(v, a) = (c_2, w)。则 f(u, a) = (c_1 + c_2 + 1, w)。

执行上述步骤即可通过本题。时间复杂度 O(n^2)。