小战CSP 2025

· · 个人记录

在【数据删除】时口胡的，不到半个小时就胡穿了！感觉很牛！

D

板上钉钉的计数DP，想想状态怎么设计。

发现我们真正要关心的只有被放弃面试的 1 的位置，并且一段前缀 1 状态被确认后，每一个 c_i 是否会放弃面试都是确定的。

于是设 f_{i,j,k} 表示前 i 个位置有 j 个放弃面试，且 c_i \le g_{i,j} 中有 k 个已经被选了。其中 g_{i,j} 表示前 i 个位置 j 个放弃面试的情况下会放弃面试的 \max(c_i)。

转移的时候把 1 且不被录取的方案数塞进转移里就行。

十多分钟胡完了 D 感觉自己很牛！

C

串串题。感觉一切尽在掌握！

非常简单的替换模型，发现对于所有字符串都只关心它和它对应串的极长不相同子串。

其实场上胡到这里我就停了因为感觉后面都是 general 的，不过似乎有点过于轻敌。

实际上还要考虑文本二元组是否在询问二元组中出现。具体地，我们将 s_1,s_2 合并成一个极长串，那么只需要满足从极长不相同子串前后各出发的一段前后缀在 t 的极长不相同子串的前后各出发的一段前后缀中出现过即可，这个玩意儿在 trie 树上体现成一个二维偏序的限制，是平凡的。

不到十分钟胡完了我果然还是擅长字符串呃呃呃哼哼哼。

A

然后去看了眼A啊懒得喷没啥意思贪一下就行。

B

我怎么记得见过把边数从 O(m) 降到 O(n) 然后随便做的题？？？

没意思呃呃呃哼哼哼。

总结

题目都很常规啊感觉没啥意思不如NOIP好玩 我还是只会做常规偶爱题

为啥我的退役之战不是这个？？？？？？？