「Diary & Solution Set」January 2026 岁月不居，时节如流
2026.1.1
新的一年。不对啊为什么我又失语了，一定是停课导致的罢。虽然 whk 学习并没有用掉整个 12 月，但是找了一堆理由拖到 1 月再写，机智如我。
现在看来过去的一年发生了好多事情，随便甩一个形容词都能荡漾一笔，甚至不需要是形容词——但毕竟飘风不终朝，也不便再谏过往。已经忘了过去这一年有没有许下什么愿望定下什么目标，正好也不用再纠结实现的问题。时间的破碎感愈发严重，现在我已很难完全静下心海。或许任由其波纹荡漾也是一种静，我不知道。
我思我在我的彼方
抒写我 关于我的真相
1.2
QOJ4218 Hidden Graph
就…就我不会 Brooks 定理和 Welsh–Powell 算法呗。
CF1630F Making It Bipartite
就…就 NOIP 前才看了偏序集宽度求法学了几周 whk 又忘了呗。
1.3
今早跟 yzq 随手翻了几下前几场 ABC 的题。已被 ABC 严肃击杀。
复健之路道阻且长，其实还有一种可能是原本就只有这个绿题做不起的水平😓。
晚上 ABC 光速通过 A~E，然后对着 F 发呆了 5min。随后发现好像大脑没开机，找到充要条件树状数组优化一下就过了，总共花了 27min 没吃罚时，感觉还行啊。随后一直做 G，基本上会了但是因为不会 Power Projection 一直红温到结束😅。
ABC436E Minimum Swap
大脑响应时间小于 NOIP T1，已经赢了。
这是经典问题，但是大脑没开机。过了几分钟想起来最小交换次数为 \(n\) \(-\) 置换环个数，方案数等于各置换环内部完全图生成树个数之积。然后推广一下就做完了。
ABC436F Starry Landscape Photo
看错了两遍题，建议先回去把英语提升至 145。大脑响应时间约等于 NOIP T1，输麻了。
看懂题之后相当简单啊，一个方案对应到极小的 \([l,r]\) 和 \(b\) 就做完了。
ABC436G Linear Inequation
欸是原题不会做环节。记 \(V=\sum A\)。
-
\(M\) 贼大，\(V\) 贼小。从低到高二进制按位考虑每个物品选的个数，就可以做容量为 \(V\) 的 01 背包，做到 \(O(NV\log M)\)。
-
如果不会上面的做法怎么办呢，观察到这个东西的 OGF 是类似付公主的背包状物，但是 \(M\) 很大没法直接卷，只好严肃学习 Bostan-Mori。核心思想是对于 \(\dfrac{P(x)}{Q(x)}\) 上下同乘 \(Q(-x)\) 消去分子奇次项然后分讨 \(m\) 的奇偶性递归。相信自己要用的时候一定会推罢。
AGC038F Two Permutations
最小割模型上边 \((u,v,w)\) 的意义：若 \(u\in S, v\in T\)，则有 \(w\) 的代价。
ABC437G Colorful Christmas Tree
这为啥评黑。
每个点作为某个颜色出现的次数是确定的，对于每个点及其相邻点来说是一个匹配问题，跑出完美匹配即有解。由于 \(O(\sum n^2)\) 可过，构造直接暴力枚举模拟题意即可。构造的存在性由完美匹配可以构造性地证明。
此外在题解区看到了 \(O(n)\) 做法：考虑 dp，\(dp_{u,c}\) 表示以 \(u\) 为根的子树内部全部删去，且提前钦定删去 \(u\) 与父亲时 \(u\) 的颜色为 \(c\) 是否合法。转移时是做一个左部点 \(O(1)\) 右部点 \(O(d)\) 的匹配，直接 Hall 定理即可，构造也是简单的。
ABC438E Heavy Buckets
简单倍增没秒。
ABC439G Sugoroku 6
场上好像差的不是一点，连怎么快速算第 \(i\) 轮赢的概率都不会（后半部分倒是差不多做出来了）。还是菜了，以此作为深入学习生成函数乃至数学甚至高中数学的契机叭。
令 \(f_i\) 为前 \(i\) 轮还没有赢的概率。对一轮骰子摇出来点数的概率，有生成函数 \(F(x)=\dfrac{1}{M}\sum\limits_{i=1}^M x^{A_i}\)，\(F^i(x)\) 即表示 \(i\) 轮后走到某个位置的概率。于是 \(f_i=\sum\limits_{k=0}^{N-1}[x^k]F^i(x)\)，乘上前缀和算子 \(\dfrac{1}{1-x}\) 变为 \([x^{N-1}]\dfrac{F^i(x)}{1-x}\)。这是 Power Projection 的形式，只不过多乘了一个 \(\dfrac{1}{1-x}\)，将其展开为 \(\sum\limits_{i=0}^{N-1}x^i\) 放到分子上照常做 Bostan-Mori 即可求出 \(f\)。
后半部分比较简单，是对每个 \(i\) 计算 \(\sum\limits_{k=1}^N (f_{k-1}-f_k)f_k^{i-1}f_{k-1}^{L-i}\)。考虑到对 \(1\leq i\leq L\) 都要求答案，又有个求和的 \(k\)，所以大致的思路是写出这东西的 GF \(G_k(x)\)，\([x^i]G_k(x)\) 表示 \(k\) 对 \(i\) 的贡献，这样所求即为 \([x^i]\sum\limits_{k=1}^N G_k(x)\)。将关于 \(i\) 的式子处理成一项：\(\sum\limits_{k=1}^N (f_{k-1}-f_k)f_{k-1}^{L-1}\left(\dfrac{f_k}{f_{k-1}}\right)^{i-1}\)，答案可以表示成：\([x^{i-1}]\sum\limits_{k=1}^N \dfrac{(f_{k-1}-f_k)f_{k-1}^{L-1}}{1-\frac{f_k}{f_{k-1}}x}\)，分治卷一起（维护分式可以保证项数与区间长度同阶）就完了。
时间复杂度 Power Projection 与分治卷积均为 \(O(\mathsf{M}(N)\log N)\)。
1.4
ARC147D Sets Scores
是我喜欢的映射。考虑一个数 \(x\) 在一个方案下，如果 \(S_i\) 与 \(S_{i+1}\) 的对称差为 \(\{x\}\)，\(x\) 的存在状态就会翻转。如果在 \(S_1\) 中翻转 \(x\) 的存在状态，可以得到一个方案使得 \(x\) 在两个方案中出现次数总和为 \(n\)，且其它数出现次数相同。由于任何一个方案对于一个 \(x\) 都可以找到一个对应的方案，在对称差确定的情况下所有方案价值之和为 \(n^m\)。而对称差有 \(m^{n-1}\) 种，于是答案为 \(n^mm^{n-1}\)。
[CERC2015] Frightful Formula
边界上的贡献是简单的。主要是对 \(\sum\limits_{i=0}^{n-2}\sum\limits_{j=0}^{n-2}\dbinom{i+j}{i}a^ib^j\) 的处理。第一反应是卷积，但是模数不是 NTT 模数，一点也不优雅。
考虑 GF 写递推或通项，\(F(x)=\sum\limits_{i=0}^{n-2} \dfrac{a^ix^i}{i!},G(x)=\sum\limits_{i=0}^{n-2} \dfrac{b^ix^i}{i!}\)，令 \(H(x)=F(x)G(x)\)，所求即为 \(\sum\limits_{i=0}^{2n-4} i![x^i]H(x)\)。
两边同时求导得：
代入 \(f_i=i![x^i]H(x)\) 化为递推式：
于是做完了。
ARC139D Priority Queue 2
第一想法是对于每个值统计贡献，但是后来加入的值不好处理初始排名。
纯求和涉及到排名的问题，可以考虑拆贡献，对 \(v\in[1,m]\) 统计最后 \(\geq v\) 的数个数。
然后是 Ad-hoc 部分，如果当前个数多于 \(n+1-x\) 个，加入 \(<v\) 的数会减少；如果少于 \(n+1-x\) 个，加入 \(\geq v\) 的数会增加；如果等于 \(n+1-x\) 个，则无论如何不会产生影响。
发现答案只与初始状态和选了多少次 \(\geq v\) 的数有关。枚举选了 \(i\) 次 \(\geq v\) 的数，带系数 \(\binom{k}{i}(m-v+1)^i(v-1)^{k-i}\)。
CF1097G Vladislav and a Great Legend
我咋不知这个 trick。直接做怎么做都是 \(O(nk^2)\)。\(n\) 贼大 \(k\) 贼小，这东西长得又不像可以插值的多项式，考虑普通幂转下降幂：\((f(X))^k=\sum\limits_{i=0}^k\begin{Bmatrix}k\\ i\end{Bmatrix}\dbinom{f(X)}{i}i!\)。
转变为对 \(\sum_X\dbinom{f(X)}{i}\) 计数，这东西的组合意义是从斯坦纳树里面选出 \(i\) 条边，看起来很好树上背包。容易做到 \(O(nk)\)。
1.5
AGC045D Lamps and Buttons
哇，是远古银牌题。
起手式似乎是最难的一步。因为不知这个排列，所以一开始肯定是任选，然后顺着一个置换环走下去，继续任选。这样看起来有可能会有运气因素，但是由于排列均匀随机，只要策略固定概率就是固定的。不妨以从小到大摁作为策略（做完之后回看，以各种策略计数的结果是一样的）。
观察样例解释，如果摁到了 \([1,A]\) 里面的自环会输，\((A,N]\) 里有自环也会输。考虑什么情况下会摁到 \([1,A]\) 里面的自环。假设最小的自环在 \(p\)，那么摁完 \([1,p)\) 还没有赢就会摁到 \(p\) 然后输掉。
可以得出赢的充要条件：\([A+1,N]\) 所在的置换环都满足环上最小值 \(<p\)。考虑对这个结构计数，枚举 \(p\in[1,A]\)，再枚举有多少个置换环——然后得到了带自环限制的第一类斯特林数状物，根本做不了——置换环的个数并不重要，反而徒增了限制。
但是这启发我们考虑第一类斯特林数的递推过程，当前元素可以接在任何一个前面元素的后面或者新开一个环。对于 \((A,N]\) 的部分是非常自然的，因为要求所在置换环最小值 \(<p\)，所以不可能新开一个环；\((p,A]\) 的部分也很自然，对其没有任何限制。但是对于 \([1,p)\) 的部分，不知道新开一个环后面会不会有元素接上来，而这一部分是不能有自环的。
所以考虑对自环的限制容斥，钦定 \([1,p)\) 里有 \(i\) 个自环，先带上 \(\binom{p-1}{i}\) 的系数选出自环，容斥系数是 \((-1)^i\)，这样对于一个实际上有 \(k\) 个自环的方案满足 \(\sum\limits_{i=0}^k(-1)^i\binom{k}{i}=[k=0]\)，达到容斥的目的。这样不用考虑自环的限制，先对 \(p-1-i\) 来说没有限制地选插入的位置或者新开一个环，对于 \((A,N]\) 选一个插入的位置，最后对于 \((p,A]\) 同样没有限制地选插入的位置或者新开一个环。
最后还要加上全局没有自环的方案数，只不过限制变成了 \((A,N]\) 所在置换环最小值 \(\leq A\) 且 \([1,A]\) 没有自环，同样容斥。
CF1821F Timber
第一次做这个题是两年前刚刚系统学习容斥。但是时至今日已经 GF 做魔怔了。
首先考虑判定，很简单的贪心，能向左倒就向左。考虑基于这个判定做 dp，\(dp_{i,j}\) 表示上一个被占的位置为 \(i\)，放了 \(j\) 棵树的方案数。如果向右倒，\(dp_{i,j}\rightarrow dp_{l+k,j+1},i+1\leq l\leq i+k\)；如果向左倒，\(dp_{i,j}\rightarrow dp_{l,j+1},l>i+k\)。
诶呀这个转移好丑，交换两维并统一贡献方式方便写 GF：\(2dp_{i,j}\rightarrow dp_{i+1,l},j+k<l\leq j+2k\)，\(dp_{i,j}\rightarrow dp_{i+1,l}，l>j+2k\)。这样进行一轮转移相当于乘上 \(2\sum\limits_{i=k+1}^{2k}x^i+\sum\limits_{i=2k+1}^{\infty}x^i\)。容易写成封闭形式：\(\dfrac{1}{1-x}+\dfrac{1-x^{2k+1}}{1-x}-2\dfrac{1-x^{k+1}}{1-x}=\dfrac{2x^{k+1}-x^{2k+1}}{1-x}\)。答案为 \(\sum\limits_{i=0}^{n}[x^i]\left(\dfrac{2x^{k+1}-x^{2k+1}}{1-x}\right)^m=[x^n]\dfrac{1}{1-x}\left(\dfrac{2x^{k+1}-x^{2k+1}}{1-x}\right)^m\)。
此时直接暴力卷积即可通过。考虑这个 GF 是朴实无华的二项式，有 \([x^i]\dfrac{1}{(1-x)^{m+1}}=\binom{i+m}{i}\)，\([x^{i(k+1)+(m-i)(2k+1)}](2x^{k+1}-x^{2k+1})^m=2^i(-1)^{(m-i)}\binom{m}{i}\)，可以做到 \(O(n)\)。
1.6
省选模拟赛。
看题，T1 应该比较简单，T2 \(n=10^9\) 神秘排列计数，T3 怎么连 \(O(nq)\) 暴力都不会。
做 T1，并没有意识到直接颜色段均摊就完了啊还以为不构成颜色段均摊（一定是没睡够的原因😅），胡了一个巨丑无比的线段树做法，写到一半放弃了发现可以颜色段均摊，然后思考了一会儿 ODT 怎么写，醒来发现已经 10:00 了才过 T1，怎么蓝题做了 2h。
骗你的和 NOIP 一样已经提前推过一遍 T2T3 了。T2 已经摸到正解结论的前一步了但是觉得这个应该不普适放弃了思考（一定是没睡够的原因😅）然后试图拼暴力发现只会 10pts，直接跳了。T3 虽然看起来暴力都不可做但是我会平面向量和解析几何气势上不能输，先想暴力怎么做，正交分解吼，不等式吼，不会了吼。发现可以贪心+调整法找到最优解，于是我会了 25pts 暴力，但是我还想拿更多分。这个 A 性质怎么这么水，怎么给这么多，那我这个暴力还有没有区分度了。开始写代码，还挺难写，好在写完了，45pts，但是 T2 没时间写了。
要是这是省选不就趋势了吗，哦不对省选好像没这么简单。那么 T2 死于磕 T3 去了，T3 死在哪里呢？
考虑这样一个问题：给定 \(n\) 个平面向量 \(\boldsymbol{v}_i\)，有 \(n\) 个实数 \(\lambda_i\in[0,1]\)，请问 \(\lambda_1\boldsymbol{v}_1+\lambda_2\boldsymbol{v}_2+\cdots+\lambda_n\boldsymbol{v}_n\) 的落点构成什么图形？
我：曲线围成的封闭图形。
于是完犊子。
但是怎么数学考试的时候遇到我就能反应过来（一定是没睡够的原因😅）。
中午在路上碰到上学期的语文老师然后走过了旁边的同学说她在跟我打招呼那我咋没看到没有回礼我的良心严重受损而且我以为没有几个老师认识我就像我之前以为生物老师不认识我一样看来存在感还是太强了翻遍表情包我还是只能用这个😅。
发现自己的比赛策略似乎相当有问题。在中档甚至简单题上卡壳喜欢直接往后跳然后把后面的题做到卡壳再回来。这样的结果是中档/简单题在比赛中期甚至后期通过，难题的时间分配也不合理，会出现做完关键步骤但是只能含泪打暴力的情况，思维跳跃和推性质推着推上瘾了会浪费很多时间。比如联合省选 2025，D1 recall 卡住了就跑去做 graperm，结果 graperm 会了 \(52\) 打了 \(8\)，recall 会了 \(100\) 打了 \(88\)；比如 CSP-S2025，T2 卡住了（这都能卡的吗）就跑去做 T3T4，结果 T3T4 都被小学生都会的步骤卡了，到后面就不知为何一点时间没有了，T4 含泪拼包；比如 NOIP2025，T2 卡住了就跑去做 T3T4，T3 画了一堆自己一会儿就忘了的性质，要不是这个 T4 有点直觉把复杂度卡低了点再加上狗运和 CCF 少爷机，就凭这个 3h+ 才过 T2 就可以埋了，T3 最后会了 \([56,68]\) 打了 \(48\)。
一方面专注力和认知能力下降严重，另一方面 2025 的正赛总是能卡简单题，也不知为何。经常是突然发现比赛时间要没有了然后回顾自己的做题过程思维一片混乱。这下不得不加训 ABC 和 CF Div.2 了。
[COTS 2025] 数好图 / Promet
好家伙，嘴上说着训简单题跑来做啥了。不说了，图计数一生推，这个题真的挺好玩。
图计数，考虑如何划分子结构。直接 dp 难以同时确定 \(1\rightarrow x\) 与 \(x\rightarrow n\) 的连通性，但是只确定 \(1\rightarrow x\) 或 \(x\rightarrow n\) 的连通性是好做的。
假设除了 \(1,n\) 已经选出了 \(k-2\) 个点满足同时存在 \(1\rightarrow x\) 与 \(x\rightarrow n\) 的路径并且知道了这么做的方案数，考虑将剩下不满足这个条件的点加进去。这里感觉和我出的那个题有点异曲同工之妙，假设选好的 \(k\) 个点为 \(V\)，然后连出去一个集合 \(S\)，最后还有一个不与 \(1\) 相连集合 \(T\)，那么 \(V\cup S\rightarrow S,T\rightarrow \{1,2,\cdots,n\}\)。这样可以分两步统计贡献，只要我在计数的时候记录了 \(|S|,|T|\)。
由于 \(i<j\) 边的限制，一个点的出入边方案数与这个点的编号有关，因此 dp 时记录的信息类似于考虑编号 \(1\sim i\) 的点，集合大小为 \(j\)，转移是简单的。
最后再考虑 \(V\) 内部的贡献。怎么这也和我那个题有异曲同工之妙。充要条件是只有 \(1\) 入度为 \(0\)，只有 \(n\) 出度为 \(0\)，对出度为 \(0\) 进行容斥即可。
做完这个题感觉我出的那个题跟上了时代潮流！
1.7
巨大无比头疼，困死了。还要做 ds，还要学习超级无敌可爱的树上问题，我以为燃烧的呐球已经很厉害了。这个教室睡不着体质真纯纯 debuff 吧，浪费一上午+下午还是好困。
VP 了 Edu186，感觉人要死了，F 写不清楚细节好难受，其他题还好。晚上要不要打 Hello2026 啊，好难决断啊，明天还有语文早读，感觉不妙。怎么感觉除了计数其它都是普及组水平，如此状态，如何省选。
1.8
谷雨从 8:00 做到 17:07，真是美好的一天。
不想写题了，先去把之前那个题的数据造了，然后看论文。
1.9
模拟赛。
浓浓的找性质+数据结构味，应该是除了计数我最擅长的内容（能不能有数据结构优化计数 dp）。T1 是不太会性质题，T2 是串串，T3 的暴力是经典反悔贪心。
T2 画了一下会了 \(O(n^2)\)，好像 SA+线段树合并可以简单做到 \(O(n\log n)\)，在 1h 时过了，测自己造的极限数据发现跑得有点慢，同时发现需要开 __int128。好像不好优化，先放了。
然后在 T1T3 间反复横跳没有任何进展，只是发现 T3 暴力其实有 \(80\)（赛后发现数据给的 \(60\)）。花了一些时间写 T3 暴力，都基本忘了怎么打（结果最后特殊性质没过挂成 \(40\) 了，不知为何）。
T1 中间几个小时想出的思路是二分答案，然后贪心是不好用数据结构维护的所以考虑 Hall 定理，这样问题转变为对后缀和的判定，可以用 ST 表维护。但是感觉一个点修改后的影响不好维护所以卡住了。最后半个小时发现其实一个点只会受到到根路径上最小值的影响所以影响总量是 \(O(n)\) 的。怎么又被普及组难度卡了，掐一下自己开始 rush，还剩 10min 时 rush 出来了，跑得有点慢，把 vector 改成数组快多了。
最后 T2 被卡了一个点的常，发现其实写的是双老哥。官解是什么调和级数，没看懂。
T3 在题面提示如此明显的情况下居然没有将反悔贪心与凸性联系起来，感觉要严肃复习凸优化。
今天下午体锻好像有谁谁谁的批斗大会，可惜我作为 victim 去不了现场。
USACO 晚上 9:00 开放，发现新号在 Silver，犹豫是否今天开。
1.10
模拟赛，但是名曰期末考试。
T1 是比较好想的哈希，T2 是比较简单的找性质+线段树优化 dp。T3 是困难图论 Ad-hoc，但是因为是最优化被乱搞创飞了。写了和正解比较有联系的树性质，拼了状压打不过乱搞，怎么我树性质做法和题解不太一样呢。
1.11
ARC 被 D 创飞了，C 在错误的方向上做了好久，推翻思路很快就过了。这把降智掉大分。
专注力训练&心态恢复：
-
先将手头的事情全部做到可以暂时扔掉的地步。
-
冥想。
-
定时开 ABC/CF Div.2 等较为简单但是需要注意力的比赛，或者做数学卷子等；但是如果是专注力训练不建议进行文学艺术类活动。
-
冥想。
-
进行复盘总结。
注意事项：
-
冥想的作用是调整状态，回归宁静。最好有一个安静的环境，配轻音乐/白噪音，没有外放条件可以舍去/找天然的白噪音，但是一定不要戴耳机。过程中放松全身，以最舒适的姿态，注重于感受身体，感受呼吸。进行深呼吸，吸气时脊柱向上延伸，呼气时沉肩，过程中一定要放松。保持注意力在身体上，一旦察觉到思考尘世因果，迅速回到状态并给予积极的心理暗示。可以以音乐结束作为结束的标志，如果没有条件可以随意，尽量不要让上课铃声这种 deadline 强制性唤醒。
-
排除外界干扰是主要目的，一旦察觉被干扰迅速回到状态并给予积极的心理暗示，保持冥想带来的宁静，遇到思维卡壳灵感枯竭等情况，给予积极的心理暗示并从全局重新审视问题。
-
完成活动后利用冥想尽快抛弃适才的因果，忘记刚才可能令人愤懑令人难过的事情。冥想结束后再进行复盘总结，防止情绪化的总结不够客观真实。
因为这是我瞎编的，实测还不够完善，不排除心态更加炸裂的情况。
1.12
CF1810G The Maximum Prefix
说来惭愧，这个题做过无数遍今天才写代码。
经典 trick：最小/大前缀和的刻画方式；反向贡献系数；类似转移不同初值考虑通过转化放在一起转移。
CF1175G Yet Another Partiton Problem
决策单调性证不出来，很经典的 CDQ + 斜率优化就做完了。此外由于贡献与最值有关，可以最值分治，但是需要分讨，代码比较难写。
[JOIST 2023] 曲奇 / Cookies
这题为啥评黑。
考虑充要条件，贪心不好判定考虑 Hall 定理，然后就做完了，需要 bitset 优化。
ARC212E Drop Min
你说得对，但是我场上被 D 创飞没时间做这个小清新题了啊。
发现只要一个数两边有比它大的就能删掉，建出笛卡尔树，则左子树或右子树被删完之后这个树能被删。不过这要求左/右子树删完之后旁边不是边界。分讨一下，如果左子树能删，有 \(\binom{L+R+1}{L+1}\) 的贡献，如果右子树能删，有 \(\binom{L+R+1}{R+1}\) 的贡献，如果都能删，要容斥掉在最后的方案 \(\binom{L+R}{L}\)。其中 \(L,R\) 表示左/右子树大小。
1.13
[USACO23FEB] Watching Cowflix P
经典。
考虑其实有两种刻画答案的方式：一个是确定 \(k\)，一个是连通块个数。但是直接上数据结构/凸优化都是不好维护的。但是发现 \(k\) 与连通块个数的乘积是 \(O(n)\) 的，所以可以根号分治，处理 \(k\leq B\) 与连通块个数 \(\leq \dfrac{n}{B}\)，可以做到 \(O(n\sqrt n)\)。但是这题卡空间，所以需要用重剖继承的方式优化树上背包。
此外由于 \(k\) 与连通块个数的乘积是 \(O(n)\) 的，一个很厉害的观察是可以将距离 \(\leq k\) 的关键点全部缩一起，然后建虚树是 \(O(\frac{n}{k})\) 级别的，总复杂度 \(O(n\log n)\)。
[JOIST 2023] 议会 / Council
作为集幂糕手怎么差点没做出来。
考虑去掉议长之后出现次数恰好为 \(\lfloor\frac{N}{2}\rfloor\) 的那些议案是危险的，记它们为 \(S\)。再记一个议员支持的集合为 \(A_i\)，即对 \(1\leq i\leq N\) 求 \(\min_{j\not=i} |S_i\cap A_j|\)。
考虑只有一个 \(A\) 但是多次查询怎么做，可以做一个高维超集 \(\min\) + 高维子集 \(\min\) 状物，但是对于 \(A\) 的子集这玩意会错误贡献，那考虑取个补集就可以了。变成多个 \(A\) 也是一样的，细节是由于不能算议长所以要处理次小值。
[集训队互测 2024] 树上简单求和
考虑括号序，左括号加一右括号减一，则一条根链可以被表示为一段区间。可以描述为经典问题：区间加，区间查询 \(\sum\limits_{i=l}^r a_{p_i}\)，这个大力对 \(i,p_i\) 分块维护贡献即可。
1.14
接着 1.6 的一个问题说两句。
考虑这样一个问题：给定 \(n\) 个平面向量 \(\boldsymbol{v}_i\)，有 \(n\) 个实数 \(\lambda_i\in[0,1]\)，且满足 \(\sum\limits_{i=1}^n \lambda_i=1\)，请问 \(\lambda_1\boldsymbol{v}_1+\lambda_2\boldsymbol{v}_2+\cdots+\lambda_n\boldsymbol{v}_n\) 的落点构成什么图形？
如果 \(n=2\)，这是高中数学必修二里面提到的等和线。扩展到 \(n>2\) 的情况，可以发现这是这些向量所代表的点形成的凸包。
[蓝桥杯 2024 国研究生组] 生成树问题
相当于对 \(2\sim n\) 每个点选一个选一个父亲 \(fa_i<i\)，然后发现可以 \(O(n\sqrt n)\) 预处理边权为一的边，将其作为一次项系数，边权为零的边作为常数项分治卷积就可以了，复杂度 \(O(n\log^2 n)\)。
1.15
谁懂读完题就知道出题人想干啥但是写代码比希望还难受的救赎感。心想为什么一个板子会评黑，结果实现起来一大坨分讨，虚树上点分治优化三维树上依赖背包还卡二次排序，稍微偷一下懒就要被卡常。真的是“炽热的心渐渐被失望浇灭/冰凉的脸渐渐拂去融雪”，只是 CQ 主城不可能有雪而已。
晚上应援同学打了下核桃彩虹周赛。被 C 卡了一会儿，但是大力启发式合并就能过，脑瘫了。F boruvka 板子，但是写+调还是花了不少时间。E 感觉是高妙数据结构，虽然我剩了一个小时的赛时，但是感觉写不出来就放弃了。
CF2170F Build XOR on a Segment
首先答案上界是 \(\log V\)，因为 \(\log V\) 个线性无关的向量就能覆盖整个空间。考虑离线扫描线，然后对每个 \(x\) 维护用 \(i\) 个数表示出 \(x\) 左端点最大需要有多少，可以做到 \(O(nV\log V)\)。
CF2169E Points Selection
好像被原题击杀了。
问题等价于求保留一些点，问圈住这些点的最小矩形周长减去这些点权的最大值。
考虑表示出周长，然后由于非法解不优，直接状压记录四个方向边界是否确定 dp 即可。
[JOISC 2021] ボディーガード
怎么想到在坐标系上考虑的，感觉很 educational。怎么物理必修一还在追我
考虑到 \(N\) 比较小但是贡献条件比较难刻画，尝试用 \(x-t\) 图像刻画每个 VIP 和保镖，则坐标重合表示它们走在一起。所有 VIP 走的都是斜率绝对值为 \(1\) 的线段，而可以证明保镖走斜率绝对值为 \(1\) 的折线是不劣的，因为时间是实数范围，在原地停留可以看作是反复横跳。
那么将坐标轴转正，所有行动都可以看作是横坐标单调或纵坐标单调。以所有 VIP 带来的点扩张成网格图，然后可以在网格图上做 \(O(N^2)\) dp。每次查询是凸包状物，可以离线后维护。
1.16
模拟赛。
T1 是简单计数，但是不在状态做了有一会儿，而且一个容斥式子是通过 GF 直接暴力展开得到的，写出来才发现有容斥的组合意义。T2 往错误的方向想了一会儿，T3 除了知道 Hall 定理就啥都不会了，后来发现状态不在线。最后一个小时发现 T2 直接贪心是对的，写了个暴力验证结论，然后就开始写线段树哈希，发现是双老哥只能多过 20，而且不知道为什么大样例过了最后分比暴力还少。
原来核桃周赛那个 E 直接势能线段树就可以了，可以用均值不等式分析。
1.17
因为高二学考放了一天，但是这不好，因为这样明天就要上学，但是今晚有 CF。
晚上 CF 经典降智，D 枚举做法做了一百万年，然后因为脑抽几个字符的事情调了一百万年。感觉真实水平只有 2100，如此状态，如何省选。
CF2190D Prufer Vertex
首先手玩容易刻画充要条件：\(P(T)\) 是 \(n\) 的邻接点且在 \(n\) 到 \(n-1\) 的路径上。然后可以进行分讨。
如果 \(n\) 和 \(n-1\) 在一个连通块，只有一个点会有答案，答案就是总方案数。
如果 \(n\) 和 \(n-1\) 不在一个连通块，假设对点 \(i\) 求答案：
-
\(i\) 和 \(n\) 在一个连通块，此时要求 \(i\) 是 \(n\) 的邻接点才有答案。然后要求以 \(n\) 为根时 \(n-1\) 在 \(i\) 子树内。因为 \(n\) 连通块内每个点等价，所以里面的每个点均分总方案数，也就是所有 \(n\) 的邻接点（事实上还有一个 \(n\)）以子树大小之比分总方案数。证明可以考虑构造双射，如果一个方案 \(n\) 到 \(n-1\) 路径上最后一个在 \(n\) 连通块内的点为 \(x\)，把连接 \(x\) 的边全部移到另一个 \(n\) 连通块内的点 \(y\) 上也是合法的方案。
-
\(i\) 和 \(n\) 不在一个连通块，首先将 \(i\) 与 \(n\) 连边。然后如果 \(i\) 和 \(n-1\) 不在一个连通块，和上面的情况是类似的；如果 \(i\) 和 \(n-1\) 在一个连通块那就已经满足限制，就是在 \(i\) 和 \(n\) 之间连边后的答案。
1.18
非常好离线做交互题，因为昨晚打 CF 直接大脑退化了，孩子再也不打 CF 了。
打省选模拟赛，集幂糕手被集幂 T1 创飞了。
1.19
CF1442D Sum
首先需要观察性质，key observation 是最多只有一个序列不会被选满，证明考虑反证+调整法。
然后就随便做了，直接套线段树分治即可。
AGC054D (ox)
经典，但是放到现在看有点过时了。
容易发现无论如何把 ox 删去之后左右括号必须匹配，那可以先贪心调整至匹配状态。然后 o 可以随意插入，x 要在一对匹配括号的内部，容易以此设计 dp。
[BalticOI 2022] Stranded Far From Home (Day2)
好像 ABC 有个序列版本。考虑如果当前某个颜色说服了共 \(x\) 个人，那么只经过 \(\leq x\) 的点就能到达的点都可以被说服，这个过程做 \(O(\log V)\) 轮。每轮这个操作用 Kruskal 重构树维护即可。
不过本题只需要判断能否吃掉全局，序列版本还有个做法是建笛卡尔树，然后逐层爬上去。对于本题也可以依葫芦画瓢。
1.20
我们的模拟赛怎么难度严格小于 NOIPlus。
T1 简单容斥，T2 简单树性质缝合题。T3 感觉是不难的分讨+数据结构维护题，但是我写完了发现我手玩玩不出来最后一个样例。
[CEOI 2022] Homework
好像 WC 有个类似的题。
需要注意到答案是连续段，即求答案最大最小值，可以在表达式树上 dp，转移贪心即可。
[CEOI 2010] alliances (day1)
如果没有人类的限制，就是板的二分图最大匹配。
人类的限制可以拆点为上下选一个和左右选一个。
[CEOI 2023] The Ties That Guide Us (incursion)
这题有点好玩（？）。
首先第一遍其实只能对每个点进行黑白染色。
考虑 Sub2 那个度数为 \(2\) 的点，第一遍染色的时候把关键点到那个点的路径全染成黑色，然后第二遍先往那个点走，直到碰到黑点。然后需要解决怎么在只碰到白点 \(30\) 次之内的情况下往黑色儿子走。由于有儿子个数小于等于二的性质，考虑重链剖分，每次优先往重儿子走，由于最多有 \(\log n\) 次需要走轻儿子（也就是重儿子不是黑点），可以发现容错次数是 \(2\log n\) 级别。
接着考虑原题，发现以重心为根就解决了。
[CEOI 2019] Magic Tree
记录下之前模拟赛因为不会下传标记被创飞的线段树合并做法。
这题的转移里面有个区间取 \(\max\) 操作，由于需要线段树合并是不好直接做的。在本题中由于 dp 数组单调不降，可以转化为区间覆盖，然后线段树合并遇到空节点不能下传标记，否则会 T 飞。考虑将区间覆盖转为区间删除子树+区间加，则可以标记永久化维护。还有一个写法是维护区间 \(\min,\max\)，如果相等表明这个节点可以没有左右儿子，可以直接参与合并。
1.21
[TJOI2009] 排列计数
诡异邻项限制排列计数，考虑连续段 dp。假设填到了 \(x\)，只需要知道 \([x-k,x-1]\) 的位置，以及开头结尾是否已经确定，所以状态数可以做到 \(O(nk!)\)，每次转移找插入的位置 \(O(k)\)，总复杂度 \(O(nk\cdot k!)\)。
1.22
交互，构造，欸你知道我要说什么的。
我的小清新 counting 呢？我的小清新 data structure 呢？我的小清新 dp 呢？
偏偏在这种时候意志动摇了。只好摆，躺，学 whk。
luogu 随机跳题在 20 次以内跳到了两次同一个题，而且跳到的题要么太简单要么做过，感觉被做局了。
[COI 2011] 卡车 / KAMION
读题的时候不要忽略题目背景。打破惯性思维。
搞清楚装货卸货是一个栈。考虑到直接做 dp 需要记录这个栈，这不好。考虑减少状态数，发现可以只记录路径端点，然后看两边是否匹配。可以做到 \(O(n^2k)\) 状态 \(O(n^2)\) 转移。
[清华集训 2014] 玛里苟斯
随题随到的 P11713，考察对线性基的理解，不过看到这个题号我想发起无奖竞猜 P11714 是什么（雾）。
用线性基替换 \(S\) 是等价的，因为当异或构成的值确定时，不构成线性基的元素确定选或不选后线性基里面的元素有且仅有一种方案，因此所有值异或出来的概率是一样的。
对于异或和 \(k\) 次方的问题，由于 \(k\) 较小容易想到二进制位拆贡献，直接 \(O(\log^k V)\) 爆搜可能的贡献形式，带一个很小的常数。而里面的计算也是容易的。
CF1830C Hyperregular Bracket Strings
记录一下这个 trick。
问题在于如何判断一些位置的覆盖方案相同。这个等价类问题可以通过异或哈希解决。
虚树
我：这玩意儿 ddp 一下就好了。
woc 怎么是单点独立修改。
1.23
模拟赛，但是睡了一个上午，懒得写代码。
期末考试的语文物理都特别难，信息类文本第一题因为太困了花了一些时间才发现逻辑谬误。材料如下：
这是因为，辩证唯物主义所说的真理是客观真理，是人的思想相对于客观世界及其规律的正确反映。因此，作为检验真理的标准，就不能到主观领域内去寻找，不能到理论领域内去寻找，思想、理论自身不能成为检验自身是否符合客观实际的标准。
选项如下：
思想、理论等之所以不能成为检验真理的标准，是因为它们并非对客观世界及其规律的正确反映。
此处的原因应该是“思想、理论等主观的内容不是客观世界及其规律”，而非“并非对客观世界及其规律的正确反映”。材料中的“正确反映”一句是在对“真理”做概念界定，摆明“真理”要从客观的事物中来。这个逻辑谬误从材料最后一句出现的两个“自身”也可以看出来，材料强调的是“真理”本身作为思想、理论，不能检验自己的正确性，而选项对其进行了偷换。
1.24
模拟赛，得分 T1 < T2 < T3 嘟嘟嘟。
T1 感觉会了但是实际上想写代码的时候脑子就短路嘟，只好看 T2T3 嘟。发现 T2 长得像模拟赛频繁出现的凸优化嘟，但是我从来没有获得过大于暴力的分数嘟。T3 看起来是可做的字典序题嘟，发现 \(k\) 很大所以不好做虽然好像 \(k\) 与 \(n\) 同阶也不会嘟。想了一下 T3 可以逐位确定嘟，二分+线段树维护双老哥 1e5 2.5s 感觉随便过嘟。细节好多加上专注度不够思维断断续续导致写了 2h 嘟。中途尝试了 T2 暴力不会嘟，这时发现单调队列优化做 \(O(n^2)\) 嘟，同时敏锐地发现并证明了段数与段长限制之积是 \(O(n)\) 的所以可以阈值分治嘟，阈值分治的另一部分也可以单调队列优化做到 \(O(n\sqrt n)\) 嘟。最后拼了一个 T1 暴力嘟。
最后 \(40+70+100\) 嘟，发现大家都过了 T1 都没过 T3 是为什么呢嘟。T2 一个点不是 4pts 吗这个分怎么来的嘟嘟嘟。
1.25
ARC 被 B 创飞了，但是终于能以正常状态开始复健了。
[ROIR 2018] 大数据处理 (Day2)
题目给出合法的一段覆盖是线段树上的一个区间，而覆盖顺序一定是按深度从小到大，没有后效性，考虑在颜色段形成的结点数为 \(O(nk)\) 的动态开点线段树上 dp。令 \(dp_{u,i}\) 表示如果 \(u\) 的祖先覆盖到 \(u\) 子树的颜色为 \(i\)（没有则 \(i=0\)），\(u\) 子树至少还要多少次覆盖才能满足 \(u\) 子树内部的要求。由于除了 \(u\) 子树之内的颜色都可以看作 \(0\)，状态总数是 \(O(nk)\) 的。
1.26
根号 lxl 数据结构，不过难点全部在于卡常，嘟嘟嘟。
CF1822G2 Magic Triples (Hard Version)
枚举中间项，对 \(\leq B=V^{\frac{2}{3}}\) 的部分暴力枚举约数，\(>B\) 的部分暴力枚举 \(b\)，做到 \(O(nV^{\frac{1}{3}})\) 是简单的。
枚举约数 \(O(\sqrt B)\) 也太 low 了，考虑加速枚举约数的过程。线性筛 \(O(B)\) 预处理最小质因子，这样分解一个数 \(x\) 就是 \(O(d(x))\) 的，其中 \(d(x)\) 是 \(x\) 的约数个数，然后乱调一下块长快到飞起。
1.27
更困难（更卡常）的 lxl 根号数据结构。写了点东西。
QOJ1851 Directed Acyclic Graph
DAG 可达性统计，1e5 5s，根号 + bitset，难道你是……
我常常追忆过去。
于是根号重构 + bitset 啪地一下就上去了，很快啊！
考虑到这个可达性修改很难做，先考虑静态怎么做。跑一遍可达性统计记录每个点最晚的覆盖时间，然后统计之后的取 \(\min\) 操作。查询这个取 \(\min\) 操作的最小值是查一段时间轴的后缀，那么考虑对时间轴分块，每个块跑一遍可达性统计求出这个块内每个点取 \(\min\) 操作的最小值，查询的时候散块暴力整块取预处理的答案就可以了。
然后再考虑动态怎么做，发现套用时间轴分块很简单，然后就做完了。令块长为 \(B\)，时间复杂度 \(O\left((n+m)\dfrac{B}{w}\cdot\dfrac{q}{B}+q(B+\dfrac{q}{B})\right)\)，取 \(B=\sqrt q\) 取得 \(O\left(\dfrac{(n+m)q}{w}+q\sqrt q\right)\)。
实际上取 \(B=512\) 并手写 bitset 会很快，1s 不到。
[Ynoi Easy Round 2019] 黑川赤音
考虑静态一个集合怎么做，可以直接莫队维护 \(F(S,* )\)，由于出现次数的种类数根号，单次查询可以双指针做到 \(O(\sqrt n)\)，这题有类似的地方，可以参考。
静态莫队动态化考虑时间轴分块，对于每个集合每加入 \(B\) 个点跑莫队重构一次，每次查询 \(O(B)\) 暴力修改散的点。如果说一个集合剩了一些询问还没有处理就需要合并的话也需要重构一次，直接重构复杂度肯定炸了，所以考虑启发式合并，每次合并的时候将更小的那个集合重构。这一部分参与重构的元素个数总量是 \(O(n\log n)\)，询问总数是 \(O(q)\)，时间复杂度不会超过 \(O(n\log n\sqrt q)\)。
考虑其它部分的时间复杂度，由均值不等式最坏情况下 \(O(\frac{n}{B})\) 次重构均摊询问次数，故最坏情况下跑一轮莫队有 \(O\left(\dfrac{q}{\frac{n}{B}}\right)\) 次询问，时间复杂度为 \(O(n\sqrt \frac{qB}{n})\)，算上单次查询的 \(O(B)\) 修改和 \(O(\sqrt n)\) 查询，总复杂度 \(O(q(B+\sqrt n)+\frac{n}{B}\cdot n\sqrt\frac{qB}{n})=O(q\sqrt n+qB+n^{\frac{3}{2}}q^{\frac{1}{2}}B^{-\frac{1}{2}})\)。\(B=nq^{-\frac{1}{3}}\) 时取到理论最优 \(O(q\sqrt n+nq^{\frac{2}{3}})\)。这里单次莫队元素个数全都视为 \(O(n)\) 显然偏大了，加上会有一些常数因素，所以实际上 \(B\) 可以开定值开小一点。
最后实现上有一点，在启发式合并时和最后有的集合可能没有满 \(B\) 个元素，也需要跑一次莫队，所以莫队的实现要精细，块长最好按照实际上参与莫队的元素个数 \(N\) 与实际的询问次数 \(Q\) 开成 \(\frac{N}{\sqrt Q}\) 做到理论最优 \(O(N\sqrt Q)\)。
1.28
整点凸包顶点个数是 \(O(V^{\frac{2}{3}})\) 级别。
绷不住了为什么我接了一个验 std 30k 构造题的活，什么心态啊。
[PA 2025] 吃树叶 / Liście
记 \(a\) 的值域为 \(V=10^6\)。观察数据范围可能要搓一个 \(O(\sqrt{nmz})\) 的东西，虽然感觉这个很诡异。而且这个题应该是不存在 \(\text{polylog}\) 做法，前几天问了 yzq 一个类似的问题发现被规约了。
静态问题是一个二维偏序，但是搬到动态上特别不好做。考虑以 \(B\) 为块长时间轴分块，先考察块内修改的贡献，是 \(n\) 个点 \(Bz\) 次询问的二维数点，可以 \(k_1\) 叉线段树平衡复杂度，做到 \(O(nk_2\log_{k_1} V+Bz\log_{k_1} V)\)。
再考察整块的贡献，每次重构做 \(n\) 个点的二维数点，总共 \(\frac{nm}{B}\) 个点 \(z\) 次询问，可以 \(k_2\) 叉线段树平衡复杂度，做到 \(O(\frac{nm\log_{k_2} V}{B}+zk_2\log_{k_2} V)\)。
总复杂度 \(O(nk_2\log_{k_1} V+Bz\log_{k_1} V+\frac{nm\log_{k_2} V}{B}+zk_2\log_{k_2} V)\)，当 \(B=\sqrt{\dfrac{nm\log_{k_2}V}{z\log_{k_1}V}}\) 时取得理论最优 \(O(nk_2\log_{k_1} V+zk_2\log_{k_2} V+\sqrt{nmz\log_{k_1}V\log_{k_2}V})\)。最后那一坨根号显然太大了，不妨取 \(k_1=k_2=V^{\frac{1}{3}}\) 做到 \(O((n+z)V^{\frac{1}{3}}+\sqrt{nmz})\)，此时 \(B=\sqrt{\frac{nm}{z}}\)。
1.29
模拟赛，这个 T3 没过感觉太难绷了。
T1 是简单计数，但是要线段树维护，30min 过。T2 长得就像决策单调性优化，然后尝试描述贡献，发现是三维偏序，但是经过 Ernd 以及树上查询的诈骗，发现其实是二维偏序，2h 的时候过了。T3 是新定义串串，花 15min 证了一下新定义满足 border 理论，但是脑抽把模板串和询问串想反了，甚至都做好了可持久化线段树维护 kmp 自动机的准备，结果最后想哈希做法只能做到根号老哥。哇赛后发现 AC 自动机就做完了啊。
浙公网安备 33010602011771号