周总结

· · 个人记录

:::info[2025-12-29]{open} 学习（复习）了可持久化字典树和 AC 自动机。虽然学过，但对可持久化字典树不熟悉。

还有 AC 自动机上 DP，感觉不难。

N 有点意思，没有想到这种树形的可持久化字典树。

要注意，可持久化字典树，插入字符串到最后一个字符不能直接 return，需要继承儿子，不然就过不了洛谷的原题。

组队练习

我写了J、L的奇怪乱搞（只有 45 分、和M的一部分。

K 由于对可持久化字典树不熟，所以没想到。

L 由于专注于乱搞，并且认为数位 DP 常数大过不去，所以是 lsy 写的。最后由于 DFS 实现的 DP 常数大于用循环写的 DP，就没过。

周练

T1 不知道什么贪心方法好，也不会证明最优性，所以随机挑了一个做法，结果 0 分。。

T2、T3都写了对拍，但是 T1 没时间写了（我倒序开题），所以爆炸了。

T4 确实神奇。 ::: :::info[2025-12-22] 这一周主要由何老板带领，训练效率有很大的提升。

12.16小练习

发挥正常。

T2 的正解思路：将离叶子距离为 1、2 等的节点数量与 2k 取 \min 之后求和。这个确实巧妙。

本质上就是求一个上界，然后发现可以达到，就做完了。

当时也没有觉得乱搞能过。想到这个乱搞的原因是之前在融侨见过一道类似的题，但是线路数量足够多并要求输出方案。

分组练习1

G 虽然做出来了，但是式子推的不够好，因为不知道 \sum\limits_{d|n}\varphi(d)=n。然后没注意到 1+\sum\limits_{i=0}^{e-1}(p-1)p^i=p^e。在 p 进制下观察就能推出来了。

F 没有发现其实本质上只有 4 种线路。并且如果保留的种类不对，复杂度就会变成 4^{22}，这个需要注意。

分组练习2

I 由于 double 精度好像只有 16 位，但是这道题小数点前面有 17 位，后面还有 2 位，所以就有问题。

J 还没搞懂。

K 之前见过，但当时太菜了没做出来。使用堆处理最小值的 trick 很常见，但是普通情况下用堆做 MST 复杂度是错的。但这道题里面由于巧妙的特殊性质，所以复杂度是对的。

L 先手必败的奇怪性质需要手动模拟才能发现，这是我比较缺少的。

周练

T1 当时以为 n^3 的做法会 TLE，实际上根本不会，所以选择了难写很多的 n^2\log n 做法。然后因为把一个 r 写成了 l，并且样例过水，以及我一般不写对拍，所以挂了 80 分。（呜呜）

所以如果有时间要写对拍。

T4 由于思考过程中漏掉了算贡献的重要方法，没有做出来。 ::: :::info[2025-10-19]

周考1(NKOJ c3371 M~P)

全都是dp。

T1 基本dp，T2 状压dp，T3 树形dp。过得比较顺利。

T4 一开始读错题了，而且没有想到把之前的直径二分掉的trick，暴力还写挂了，遗憾离场。。。

感觉1h做一道题的策略不够好，容易一开始摆烂，最后没时间写暴力。

周考2(NKOJ c3371 Q~T)

T1 和 T2 顺利通过，只用了1h15min，对着 T3 瞪了1.5h。

T4 一点不会，写了暴力之后写T3。做法是 O(n^6) 的，过不去，但是可以打表。

也是在最后-1min调出来了。交上去结果没有打表出 m=0 的情况，由于捆绑测试直接爆 0 了。

修改后贾柱没算进总成绩里，分数和排名很难看。

abc428

虽然涨了点分，但出现了诸如 multiset.erase(x) 会移除所有的 x、二分上界设小、int 函数没有返回值，+1 和 -1 处理不正确等问题。

还有 F 题有这么难吗？

计数类dp(vjudge 757263 A~E)

难度很大，全都是容斥。

填补了容斥复杂度可以小于 O(2^n) 的知识盲点。由于不知道这个，讲题之前一道都不会。

具体的，如果题目要求一堆条件必须同时不满足，我们可以设 dp_{x,y} 表示在 x 的位置，并且满足了 \ge y 个条件的方案数。统计答案时，ans=dp_{1,i}\times (-1)^y 即可。

chx讲题(vjudge 757263 H~F)

tql，%%%。讲的很清楚。

H：听懂了，大型数据结构+需要维护每个节点原答案+翻转后的答案。

G：观察到这是类似树的结构，然后分讨+前缀和。当时觉得没问题，但是后来想想发现没完全懂。

F：自己想到莫队做法，听的时候枚举答案之后就听不懂了。 ::: :::info[2025-09-15] 继续学习笛卡尔树，和 shl 讨论后三题，思考的方向没有选对。

周练 单调递增练习赛10

T1 折半搜索，T2 字典树，不难想到。

T3 当时想到了接近正解的东西，但是感觉复杂度要爆炸，没有写。T4 我把树边看成无向边，导致完全不会。。。

不应该最后一个半小时只拿5分。

abc423

和晚自习冲突了，没打。 ::: :::info[2025-09-08]

笛卡尔树

虽然结构简单，但是很灵活，可以与 lca，树形 dp，trie 树等结合。

周练

从 400 挂到 275，惨烈。

遇到取模时必须小心，有减法的时候必须加上 mod 再取模。

哈希中随机的指数居然这么弱，害的我挂了 25 分，以后指数要取定值。

arc205

有点简单。

虽然过了 4 道，但是速度慢了，A 这么简单的东西想半天。

对根号分治的理解不够，导致最后一题虽然想到根号分治，但还是没做出来。

abc422

打的还好，没什么可以说的，可以预习一下卷积和生成函数，对abc很有用。 :::