CHX(AT)XJTU

去往无穷的彼端

一个平凡的博客

VP20260821 - 2026 icpc Hong Kong

H 脑筋急转弯题. 首先注意到 $t_{n-1}$ 和 $t_n$ 的前 $n-2$ 个字符完全相同,所以 $$\operatorname{lcp}(t_{n-1},t_n)\ge n-2.$$另一方面,每个 $t_i$ 的长度都是 …

2026-08-19

B 比较板的在自动机上DP. 我们首先考虑如何判断一个给定了的串是不是合法的. 我们钦定从前向后扫描, 由于每个 c 和 p 在每个子序列中只出现一次, 所以它们就贪心去附加在已有的子序列后面就可以了, 但是相对而言困难的是决定 u 是 …

2026-08-08

吃瘪了, 打完感觉彻底燃尽了. I 签到题,按照题意模拟即可.不过有个铸币把 continue 的位置写错了,导致输入还没读完程序就开始运行,平白吃了一大堆罚时. M 同样是模拟题.枚举完种子后,只需要利用全概率公式计算第 $i$ 个种 …

2026-08-08

沟槽的黑冰茶出题组,这么喜欢构造是吧,吃nm的构史去吧. E 看上去和构造没什么关系,但实际上充分性需要手动搓出一个调整方案. 一开始很容易观察到,每次操作都会令总和增加或减少 $2$,所以总和的奇偶性不变. 不过手玩一下会发现一个更强 …

2026-08-06

是在参加南京大学办的计算理论之美活动期间和舍友随机跳题跳到的, 结果这一段时间一直在想到现在才想清楚. 简述题意题意给定一个有 $n(\le 8000)$ 个节点, 树高不超过 $m(\le 800)$ 的有根树 $T$ , 树根是 …

2026-08-04

D 普通的 DP 题,不过需要稍微考虑一下实现,不然复杂度很容易写假. 将 0,1,? 分别编码成三进制位 $0,1,2$,并令 $f_s$ 表示三进制状态 $s$ 对应的广义子集和. 对于不含问号的状态,其每一位已经唯一确定了一个二进 …