（Ⅰ）Re：转生 JK 的 OI 日记

wxr_ · 2024-07-12 09:12:13 · 个人记录

喜报：此篇文章已被收录进 https://www.luogu.com/article/m6e40fm5。

NKSC\tiny\text{——}\mathbb{N}\text{an}\mathbb{K}\text{ai Secondary School }\mathbb{S}\text{ummer }\mathbb{C}\text{amp } 2024

Week 1

7.8 笛卡尔树

大多数树形数据结构的本质都是分治。

而笛卡尔树的分治是在整体中通过一个代表元确定所有经过它的区间的信息，再将其分为左右两个互不影响的部分分治。

所以一般用于维护最值。相当于双向的可持久化单调栈。

还有就是用来转换 LCA 和 RMQ。

「CERC2019」Be Geeks!

「AGC028B」Removing Blocks

非常好期望题。

「IOI2018」meetings

首先我们发现对于一个询问区间 [l, r] 找出其最值位置 p 后 [l, p - 1] 和 [p + 1, r] 的答案就可以分别独立计算，也就是笛卡尔树上两节点的前后缀信息。

然后对于节点 p 所属区间 [l_p, r_p] 的前缀信息 f_{l_p, i} 就等于 \min(f_{l_p, p - 1} + (i - p + 1) \cdot a_p, f_{p + 1, i} + (p - l_p + 1) \cdot a_p)。

注意到 f_{p + 1, i + 1} \le f_{p + 1, i} + a_p，所以 \min 的两个取值只有最多一个交点，可以李超线段树 二分出来再区间加等差数列就行了。

「NOIP2024」树上查询

主要说一下区间 RMQ 和笛卡尔树的关系。

众所周知，一切嵌套关系都是树。而最值也是嵌套关系。

首先是左右两端点分别在其 LCA 的两侧。

然后是 LCA 的全新求法 考虑 LCA 和 DFS 序的关系，即对于 u,v（dfn_u \le dfn_v）两点找到深度最大的 f 使得 [dfn_u, dfn_v] \subseteq [dfn_f, dfn_f + size_f - 1]。

这个东西求 LCA 属实是没必要，因为要离线后才能做到单 \log。但放到笛卡尔树上可以把区间最小转最大，就能直接求 \max 套 \min_l^r 或 \min 套 \max_l^r。

7.10 基环树

基环树上 DP 相当于树形 DP 然后环形 DP。

破环为链会将前后缀合并问题变为区间问题，复杂度可能变高。

基环树断掉一条环边可以得到基环树的生成树。

「CF875F」Royal Questions

好题。二选一相关题目建图有奇效。

「JSC2021H」Shipping

「CF235D」Graph Game

「CF1270G」Subset with Zero Sum

7.11 djq

%%%

7.12 chx

%%%

7.13

T1 状态差不多，想复杂了，调不出来。

T2 抽象。

T3 板。

T4 没看，原。看了也做不出来。

Week 2

7.15 整体二分

1. 询问的答案具有可二分性。

2. 修改对判定答案的贡献互相独立，修改之间互不影响效果。

3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值。

4. 贡献满足交换律，结合律，具有可加性。

5. 题目允许使用离线算法。

———2013 集训队论文《浅谈数据结构题的几个非经典解法》许昊然

可以处理离线决策单调性。

「CTSC2018」混合果汁

你会注意到这道题实际上可能并不满足「修改对判定答案的贡献互相独立」，但是问题不大，因为整体二分的本质是线段树分治。

7.17 斜率优化 DP

有平面上一点集，每次询问给定一条直线的斜率，求直线至少经过点集中一点时的最小 / 最大截距。

考虑单调栈维护下 / 上凸壳，每次二分查询。如果所询问斜率递增可以单调队列线性维护。

动态维护凸包可以平衡树或李超线段树，也可以离线后 CDQ 分治。

7.18 决策单调性

注意到，然后打个表先。

四边形不等式，整体二分（离线），二分单调队列 / 单调栈（在线），区间 DP。

7.19 ljr

%%%

7.20

T1 均摊不能持久化。

T2 抽象构造。

T3 数学不好。

T4 图论。分治最短路。

Week 3

7.23 CDQ 分治

分治算每两个元素之间的贡献（即一个矩形内的贡献）。

「JOISC2014I」かかし

7.25 gjy

She got a body like an hourglass,
But I can give it to you all the time
She got a booty like a Cadillac,
But I can send you into overdrive (oh)
Stop and wait, wait for that,
Stop hold up, swing your bat
See anybody could be bad to you,
You need a good girl to blow your mind, yeah
Bang bang into the room (I know you want it)
Bang bang all over you (I'll let you have it)
Wait a minute let me take you there (ah)
Wait a minute tell you (ah)
Bang bang there goes your heart (I know you want it)
Back, back seat of my car (I'll let you have it)
Wait a minute let me take you there (ah)
Wait a minute tell you (ah)
She might've let you hold her hand in school,
But I'mma show you how to graduate
No, I don't need to hear you talk the talk,
Just come and show me what your momma gave (Oh yeah)
Your love gotta be baby, love but don't say a thing
See anybody could be good to you,
You need a bad girl to blow your mind
Bang bang into the room (I know you want it)
Bang bang all over you (I'll let you have it)
Wait a minute let me take you there (ah)
Wait a minute tell you (ah)
Bang bang there goes your heart (I know you want it)
Back, back seat of my car (I'll let you have it)
Wait a minute let me take you there (ah)
Wait a minute tell you (ah)
It's Myx Moscato
It's frizz in a bottle
It's Nicki full throttle, it's oh, oh
Swimming in the grotto
We winning in the lotto
We dipping in the pot of blue foam
Kitten so good
It's dripping on wood
Get a ride in the engine that could
Go, Batman robbin' it
Bang, bang, cockin' it
Queen Nicki dominant, prominent
It's me, Jessie, and Ari
If they test me they sorry
Ride us up like a Harley
Then pull off in this Ferrari
If he hanging we banging
Phone ranging, he slanging
It ain't karaoke night but get the mic 'cause he singing
B to the A to the N to the G to the uh
B to the A to the N to the G to the hey
See anybody could be good to you,
You need a bad girl to blow your mind (your mind)
Bang bang into the room (I know you want it)
Bang bang all over you (I'll let you have it)
Wait a minute let me take you there (ah)
Wait a minute tell you (ah)
Bang bang there goes your heart (I know you want it)
Back, back seat of my car (I'll let you have it)
Wait a minute let me take you there (ah)
Wait a minute tell you (ah)
Bang bang into the room (I know you want it)
Bang bang all over you (I'll let you have it)
I said bang, bang, bang, bang, bang, bang,
Bang, bang, bang, bang, bang, bang, bang
Bang bang there goes your heart (I know you want it)
Back, back seat of my car (I'll let you have it)
Wait a minute let me take you there (ah)
Wait a minute tell you (ah)

JKSC\tiny\text{——}\mathbb{J}\text{yoshi }\mathbb{K}\text{oukousei }\mathbb{S}\text{election }\mathbb{C}\text{ompetition}

Day -?

抵达重庆。

Day -1（7.24）

没有笔试。

主办方不提供宿舍，吃饭还要花钱，差评。

Day 1（7.25）

保龄。

Day 1.5（7.26）

上午复习下午社会活动，没啥好说的。

Day 2（7.27）

保龄。

Week 4

退役了，没有 week4。

8.19 自动机、KMP 与失配树

字符串题之所以是字符串，是因为其主要研究子串间的相等关系（两个序列相等没什么实际意义），所以就有很多可重复利用的信息。

自动机是有向图，因此可以倍增和矩阵快速幂。

Border Theory - Jijidawang - 博客园

8.19 最小表示法

8.20 直面天命

8.20 李超线段树

如果认为线段树没有标记下传也必须要有区间合并的话，那这个东西确实不是原教旨主义线段树。（线段树九宫格.jpg）

利用两个一次函数（或者别的什么函数）最多只有一个交点的性质，每个节点维护一条当前已下放到这个节点的线段中在分界处最优的线段。

所以也是某种意义上的「线段」树。

8.22 Z 函数（扩展 KMP）

就像 excrt 里没有 crt，exkmp 里也没有 kmp。

8.22 回文串与 Manacher

注意到每一个本质不同的回文子串首次出现时都会作为以其结尾为结尾的最长回文子串。

8.23

打成依托巧克力。

T1 KMP 板子写错。

T2 板子。

T3 怎么又是斐波那契。

T4 人类智慧。

Week 5

8.26 动态 DP

显然，广义矩阵乘法满足结合律。

线段树一直是 T0，树剖和矩阵出之后反复大削，但还是 T1。

动态 DP 结合了树剖的代码常数大，线段树的时间常数大，矩阵的空间常数大。

8.27 字典树

维护两个数的异或。

8.28 2-SAT

图论的本质是二元传递关系。

因为原命题等价于逆否命题，所以 2-SAT 图具有一定程度的对称性，即 a \to b \iff b' \to a'。

Week 6

9.2 字符串哈希

可以且仅可以匹配字符串。还可以被卡。

bkdr-hash 函数是多项式，可以用线段树维护以进行修改。

「COCI2020-2021#3」Sateliti

「CF213E」Two Permutations

卡 hash：

A tool for hacking rolling hashes with fixed modulos and bases - codeforces

卡哈希 - cancan123456 - 洛谷博客

「BZOJ3099」Hash Killer III

9.4 集合哈希

rand 又何尝不是一种哈希。

如果两个（可重）集合大小相等，每种权值随机赋值后和相等，那一般就可以认为两个集合相同。

「POI2013」LAN-Colorful Chain

9.6 二分图

二分图最大匹配（匈牙利算法，Hall 定理，Hopcroft–Karp 分层多路增广），二分图最小点覆盖（König 定理）。

Week 7

为什么要收暑假作业。

9.9 二分图

二分图最大匹配（匈牙利算法，Hall 定理，Hopcroft–Karp 分层多路增广，最小字典序），二分图最小点覆盖（König 定理），二分图最大独立集，二分图补图最大团，DAG 最小路径划分（拆点），DAG 最小路径覆盖（Floyd 传递闭包），有向图最小环划分，DAG 最大互不可达点集（Dilworth 定理），二分图博弈。

增广路是始于非匹配点，由匹配边与非匹配边交错而成，终于非匹配点，长度为奇数的路径。

翻转增广路上的匹配状态会使得匹配边数量增加一，并使得起点和终点变为匹配点的同时路径上点依然匹配，所以最大匹配时只需要从每个点开始寻找一遍增广路。

König 定理：二分图最大匹配数等于最小点覆盖数。

对于二分图左部每一个未匹配点，反复从左往右走非匹配边，从右往左走匹配边，并标记所有访问到的点。

因为已经完成了二分图最大匹配，所以此时找出的交错路一定是以匹配边为结尾的不完整增广路。

然后选择左侧的未标记点和右侧的标记点组成最小点覆盖。

简单分讨可以得出每一个选择的点与匹配边一一对应，非匹配边必有至少一个端点被选择。

又因为最小匹配数至少为最大匹配数，得证。

其实直接用最大流最小割定理就证完了。

找最多的互不相连的点，等价于在图中删去最少的点使剩下的点之间没有边，等价于用最少的点覆盖所有的边。

DAG 最小路径划分：把每个点 i 拆成入点 i_1 和出点 i_2，对于每条 DAG 上的边 u \to v，连接 u_1 \to v_2，形成一张二分图。每个点最开始都是单独的路径，一条匹配边相当于将两条路径合二为一，使路径总数减少一，且不会形成环。最终答案即为总点数减去最大匹配数。

「COCI2019-2020#6」Skandi

「CTSC2008」祭祀

「NOI2011」兔兔与蛋蛋游戏

9.11 Day 1

T1 是水题。

T2 是智慧贪心。

T3 是搜索。

T4 是 T4。

9.13 nodgd

「省选联考 2021 A/B 卷」图函数

「WC2021」括号路径

加边！加边！加边！并查集查询！

注意到对于任意合法括号序列的最内层括号，一定是以正向通过 u \to x 边，再反向通过括号种类相同的 v \to x 边得到的。而这样的单层括号也可以加到任意合法序列的任意位置。因此，两个可以通过同种括号边到达同一点的两点等价，可以通过启发式合并缩成一个点，再合并更外层的括号。

「IOI2021」钥匙

Week 8

9.17 Day 2

我常说一句话，当年 gjy 4 点睡觉能拿金牌，我 3 点睡觉拿巧克力，不是问题。

T1 原。

T2 搜。

T3 水。

你能卡我？你能卡掉我？你今天 2.5e5 能把我树剖卡了，我当场，就把这个电脑屏幕吃掉！

T4 智。

9.18 树的同构和计数

树的最小表示，hash，括号序，prüfer 序，拓扑序。

9.19 初赛复习

9.21 CSP-J/S 初赛

你说的对，但是

有符号整数算术运算溢出（结果类型无法容纳它的结果）时，行为未定义，此类操作可能会表现为：

• 按照表示法的规则（典型为补码）发生回绕，
• 在某些平台上或由于编译器选项（例如 GCC 和 Clang 中的 -ftrapv）引发陷阱，
• 在某些时候饱和到最小或最大值（在许多 DSP 上），
• 完全被编译器优化掉。

算数运算符 - cppreference

Week 9

9.24 搜索

搜索分为复杂度正确的和复杂度不正确的。

就算你把数据范围内的数据全跑完了，它复杂度也是不正确的。

双向同时搜索和折半分别搜索一般可以分析复杂度，剪枝、启发式、A 和 IDA 复杂度玄学。

优先选复杂度正确的。

但是 \mathcal{A}^{\star} 真的很酷。

设起始状态为 st，最终状态为 ed，对于状态 x，设从 st 到达 x 的代价为 g_x，从 x 到达 ed 的实际代价为 h^*_x，预估代价为 h_x，每次取最小的 g_x + h_x 进行转移。

A 在 $h_x \le h^_x 时正确性有保证最终状态第一次取出时就是最优解。因为如果 x 在 st 到 ed 的转移路径上，则有 g_x + h_x \le g_x + h^*x = g{ed}$，可以保证其在任何比最优解劣的转移前进行转移。

同理，有最终状态第 k 次取出时就是第 k 优解。

不是，为什么要在搜索作业表里放一个卡掉 A* 的 k 短路啊。

IDA 不是 A，（），是通过估价函数启发式最优化剪枝的迭代加深 DFS。

但是 IDA 比 A 常数更小，还更好写。

fw A*。

状态数比较少时去重，或者直接跑最短路。

棋盘相关搜索可以用康托展开小常数离散化，康托展开用 popcount 可以线性。

数独不知道怎么剪枝，之后再写。

9.25 没有比赛，只是四道题的题解。

困困困，难难难。

T1 水题。

T2 计数。反正不会做，早知道就不看了。可以拉插。

T3 性质题。一点都不显然。

像这种一看就完全不可做的题一般是有奇妙性质的。

证明 from @just_int_mian：如果某探照灯在取到最大高度后减少会更优，那么继续减少减少的肯定更少，肯定更优。

T4 图论和分治。「ZJOI2016」旅行者、「PA2021」Desant 2。

和 DP 没有关系。

Week 10

9.29 zqs，hyx，lyx，ljr

%%%

Week 11

比赛总结要认真写了。

10.5 Day 3

T1 水。

T2 水。傻逼 NKOJ。

T3 不会。

T4 原，但是没做过。

平均数的重要性质：小于等于最大值且大于等于最小值。

10.6 Day 4

T1 神秘卡常 DP。

对于 a_{1 \sim n}，若 \sum a_i \le n，则有 \sum a_i \times a_{i + 1} \le \sum a_i \times n \le n^2。

谁给你评测机一秒跑不过 1e8 的错觉的？NKOJ 吗？

T2 神秘贪心。

至今不会证。

T3 模拟。

容斥想到了，但因为复杂度比较离谱就没仔细想。

实际上可以注意到 DP 状态数只有 4^k 级别，同时容斥状态可以去重，总之就是可以过。

T4 仙人掌板子。杜教锐评其为答辩题。

10.8 Day 5

比赛总结要认真写了，真的。

首先是比赛策略。

由于最近的题目难度比较抽象，所以只分为签到题和不可做题。

因此要拉开区分度要么做出来不可做题，要么打部分分。

而不可做题不管能不能做出来都要花很久，剩下的时间打部分分肯定没别人打得多。（有的人例外。）

所以我们不妨认为自己能做出来不可做题且其他题的部分分全部打完也不会太高。

后者大概率能达到，前者就不一定了。

赌赢了前三，赌输了倒三。

所以出倒三也不难，多打部分分就行，毕竟一般都有人没打部分分或者签到题挂分。

而毕竟这是模拟赛，除了模拟外还是有别的意义的。

建议没进前三的都交总结。

然后是题目。

T2 的快排想不到。主要是因为第一步的转化为区间内部翻转都想不到。

T3 的设定阈值保证无后效性完全想不到。需要对期望和抽！卡！有比较深刻的理解。

证明：[20240922 模拟赛] 抽卡 - Aaron_Romeo - 洛谷博客

10.10 Day 6

上一篇中所发表的暴论大前提是题目抽象。

T1 一眼换根。然后就上数据结构动态维护了（3.5 KB），完全没想直接 DP。

好像唯一的优点是没有那么多细节来给我写挂，毕竟赛后被卡常重写的时候写了一个大样例全过的 WA80 DP。

由于各种原因调了很久。

T2 典中典归并求 k 大值。

由于各种原因调了很久。

然后就因为前两道题调了很久，后两题没时间打部分分了。

总之就是大模拟算是白写了，码力一点没提升。

还有就是正确估计题目难度，选择合适做法。

写之前想好流程，写的时候想好细节。

T3 计数。

二选一相关题目建图有奇效。很没道理。

T4 思维题。

放 div2.C 说不定就都过了。

10.11 dyh

中午睡不着的可以去听一听，听了就能睡着了。

10.11 计数

思维混乱，不会数数。

计数题不能贪心。

计数 DP 不是原教旨主义的 DP。

一般的最优化 DP 是对于单个状态进行转移，计数 DP 需要对状态的集合进行转移。

更不会了。

容斥容斥。

10.12 Day 7

还是慢了。

上次还能解释为 T1 思路逆天，T2 代码难调，这次在前两题思路和代码都都没大问题的情况下还是打不完后两题的部分分。

多练。

T1 因为不会容斥，所以完全没有被误导。一眼状压。

T2 注意到将 a 从小到大排序后，答案一定是 x \times k - (\sum\limits_{i = 1}^{y} a_i) + (\sum\limits_{i = y + 1}^{n} a_i) 的形式。

因此设 DP 状态 f_{i, j} 表示 i 个数中有 j 个数最终变为负数时 k 的最大系数。

具体转移时，还要设 g_{i, j} 表示 k 的最小系数。

好像是 \mathcal O(n^4)，不知道怎么优化。

但是集中注意力，不难注意到 f_{i, j} = \dfrac{2 j - i + 1}{3}，三分即可。

至于为什么，读者自证不难。

注意到对于有 i 个叶子节点的完整二叉树会从有 i - 1 个叶子节点的完整二叉树删除 1 个到根节点距离为偶数/奇数的叶子节点，并增加 2 个到根节点距离为奇数/偶数的叶子节点和 1 个到根节点距离为偶数/奇数的非叶子节点，因此到根节点距离为奇数的叶子节点和距离为偶数的叶子节点之差模 3 意义下不变。

即每增加 1 个到根节点距离为偶数/奇数的非叶子节点，会使得到根节点距离为奇数的叶子节点个数与距离为偶数的叶子节点之差增加/减少 3。

而有一个叶子节点的完整二叉树有且仅有 1 个到根节点距离为偶数的叶子节点，所以到根节点距离为偶数的非叶子节点个数与距离为奇数的非叶子节点之差就等于 \dfrac{(i - (i - j)) - (0 - 1)}{3} = \dfrac{2 j - i + 1}{3}。

得证。

T3 构造题。

树上翻转一条路径上边的存在情况仅会改变路径两端点的度数奇偶性。

图上的就在生成树上做。

T4 数据结构科技之 DFS 序套 BFS 序以同时维护 k 级邻域和子树信息。

具体为从根节点往上建 k 级虚点，再将 DFS 序上每个节点替换为其按 BFS 序排列的 k 级子节点。

这样每个节点的 1 \sim k 级子节点都分别连续，k 级邻域和子树信息都能划分为 k + 1 段。复杂度 \mathcal O(q k \log n)。

既然是 DFS 序，好像还可以套个树剖，比如动态修改路径上的点以及所有与这条路径上的点相邻的点。（即毛毛虫剖分。）

10.13 周总结

传统艺能之不交代码。

实际上当前两题做得异常顺利或是异常不顺的时候还是会考虑交完代码的。

不会数数。

Week 12

10.15

首先是 T1 因为抽象做法调了很久。

位运算首先考虑按位处理。

然后思路就彻底偏了。

还要用线段树维护，复杂度 \mathcal O(T n(\log a + \log n))

又不是不能做。

就算想到正解，还是要想一想有没有更简单好写的做法。尤其是 T1。

其次是顺序开题大失败。

T3 看了一眼，没看懂，然后就没看了。

计数 T3 看着就不太可做。

不是，到底凭什么放 T3 啊。

其实 CSP 题目没按难度排序的概率好像不低来着。主要是 T3T4 可能可做。

唉。

不要太魔怔。

不建议拿你的前途和出题人的马对赌。毕竟出题人的马可以看 30 秒广告复活，你的前途没了就是没了。

唉。

T4 挺好。根号分治调节复杂度都快忘完了。这种询问方式和询问内容还是要优先考虑根号分治的。

正解需要用 dfs 序的一些性质：

• 连续一段 dfs 序所形成的的每个连通块的根的父节点在一条链上向上递增。

• 不存在节点 a，b，c，d，使得 dfn_a < dfn_b < dfn_c < dfn_d 且 fa_c = a，fa_d = b。

  因为 dfn_b < dfn_c 且 fa_c = a，所以 b 必然是 a 的子树中的节点，而 fa_d = b，则有 dfn_d < dfn_c，矛盾。

为什么不给 k 强制在线 的部分分。思维性比 T2 高。

T2 注意到每一行和每一列最多涂一次，再注意到每一个格点都要涂（真的很容易注意到！！！1），所以要么每一行都涂了，要么每一列都涂了。之后的结论证不出来也能猜出来。

性质题确实需要一定的观察。弱智结论也是可能有用的，再怎么也能减少代码量。

唉。

10.17 马拉松

南开的运动会一直都很难开。

在操场淋雨，然后在机房做第一道 T2，第二道 T2 和第三道 T2。

给我一种多学了一年还是做不出来 T2 的绝望感。

如果 T2 考成这样，那考试策略什么的也就无所谓了。

10.18

喝了一瓶东鹏特饮之后还是困。可能是喝太多次之后产生抗药性了。

T1 不是 @just_int_mian 出的原题吗，秒了。

但是他本人用的最小生成树。

T2 看着就不可做。

根据上一场的经验，当 T2 不可做时就应该看 T3 了。

哇，数据结构题。口胡了一个做法直接开写。

复杂度不好说，但是没调出来，所以不重要了。

讲完后发现所有题目不超过普及组大纲，而且写了 6KB 的 T3 假完，玉玉了。

能不能想到是能力问题，想都没想就纯属脑瘫。

主要问题是由于未知原因一直在写 T3 的一眼假错误做法。看得出来确实很困。

显然要离线之后枚举一个端点然后数据结构维护另一个端点。但是可以发现问题可以由「所有 l_i \ge L 的区间可以覆盖 [L, R] 中的所有点」转化为「每个 [L, R] 中的点所被覆盖的区间中存在 l_i \ge L 的区间」。

好像并没有转化任何东西，但实际上是把修改 \mathcal O(n ^ 2) 信息，查询 \mathcal O(1) 信息转化为了修改 \mathcal O(n) 信息，查询 \mathcal O(n) 信息。反正就是可以做了。

很多题目的转换确实没什么道理，反正就是转换完了就可以做，跟数学大题的辅助线一样。但换个角度想总是好的。

T2 这种性质一眼看不出来就是失败的。

没看出来的原因一是不会这种贪心，二是自从上次用差分约束过 T1 之后最近几天就被差分约束搞魔怔了。

每次删除被覆盖次数最多的点显然是错的。序列上就是错的。

有四段区间 [1, 1]，[3, 3]，[1, 2]，[2, 3]，1,2,3 三个点都被覆盖两次，如果第一次删除 2，就还需要把 1 和 3 都删掉。

每个区间至少选一个点的数量最小值，等价于互不相交的区间的数量最大值。

有点像二分图。

当然，不难发现也可以将其转为前缀的差分关系。

最后把序列上的做法放到树上就行了，因为树上两条路径相交则必有一个 LCA 被包含。没做出来的是什么成分不好评价。

T4 给的图上的环还是挺明显的，仔细想一下也不是不可能想到。

唉。

10.19

其实除了赌自己能做出来正解，还可以赌所有人都做不出来正解。

但实际上，无论怎么说，在模拟赛中想正解的意义和收益都是远大于打暴力的。所有题都只会暴力和爆零没有本质区别。

模拟赛几乎是唯一的定时打非专题的套题的机会（线上赛的题目风格和国内比赛差距过大，不予讨论），如果在模拟赛都想不到正解，凭什么相信正式比赛上就能想到正解。

去年 CSP 只会打暴力，今年还是只会打暴力，那这一年不是白学了吗。

但是题太难了，不会就是不会，没什么好谦虚的。

不是，这哪难了。

之前一直觉得有些人打离线会被降智，现在自己也被降智了。

看到这个 T1，这个题面，这个数据范围，这个部分分，看着就像什么运用直径性质的奇妙贪心。比如二分后取前 k 大直径改边之类的。没贪出来。

贪心给 k \le 30 是吧。

容量为 m 的树上背包复杂度是 \mathcal O(n \times m) 的。

首先，多叉树上背包等价于二叉树上背包。

感性证明：每次合并两个子树相当于取左子树的 DFS 序中后 k 个和右子树的 DFS 序中前不超过 m - k 个进行合并，因此合并的都是 DFS 序中连续的长度不超过 m 的区间，共不超过 n \times m 个。

不那么感性的证明：

设点 u 的子树大小为 size(u)，左儿子为 l_u，右儿子为 r_u，时间复杂度为 \mathcal O(\sum \min(size(l_u), m) \times \min(size(r_u), m))。

当 size(l_u) \ge m 且 size(r_u) \ge m 时，单次合并复杂度为 \mathcal O(m ^ 2)，每次合并都发生在所有极小的子树大小 \ge m 的节点所形成的虚树上，这些节点的子树互不包含，最多有 \dfrac{n}{m} 个，总复杂度为 \mathcal O(m^2 \times \dfrac{n}{m}) = \mathcal O(n \times m)。

当 size(l_u) < m 且 size(r_u) \ge m 时，单次合并复杂度为 \mathcal O(size(l_u) \times m)，而 size(u) > size(r_u) \ge m，所以每个 size(l_u) 只会最多被计算一次，总复杂度为 \mathcal O(\sum size(l_u) \times m) = \mathcal O(n \times m)。当 size(l_u) \ge m 且 size(r_u) < m 时同理。

当 size(l_u) < m 且 size(r_u) < m 时，单次合并复杂度为 \mathcal O(size(l_u) \times size(r_u))，相当于在每个极小的子树大小 \ge m 的节点的子树中进行无限制的树上背包，每个点对只会在其 LCA 处被计算，总复杂度为 \mathcal O(m^2 \times \dfrac{n}{m}) = \mathcal O(n \times m)。

T2 图论建模建错了（？），因为不是二分图所以不能最大匹配。

这不显然是二分图。

T3 没怎么想，删除的状态就可以确定牌的顺序还是挺显然的。

不要轻易放弃一个思路，也不要一直对一个思路死磕。

唉。

10.20 周总结

这周打得都挺抽象的，基本没想出正解。

状态好像真的和睡眠时间负相关。

怎么会事呢。

打个 CF 吧。

CF 怎么没有部分分。

upd：因为观点过于激进被约谈了。

所有暴论都仅针对模拟赛啊啊啊啊啊啊啊啊啊可恶。

正式比赛（尤其是 CSP-S）还是要优先保证分数下限的。

下周最后两场模拟赛了。正经打，不整活了。

Week 13

10.21 马拉松

T2T2T2。

明天你是否会想起
昨天未调完的题
明天你是否还惦记
考场写挂的暴力
集训队都已想不起
没能来南开的你
我也是偶然翻 OJ
才想起退役的你

谁羡慕比赛 AK 的你
谁膜拜红名的你
谁看了你的生涯回忆
谁借走你的 RP

小恐龙.flv

你从前总是很小心
对拍后才肯交题
你也曾无意中说起
喜欢在深夜 AC
那时候比赛总很难
rating 总涨得太慢
你总说退役遥遥无期
转眼就各分东西

谁秒了你出的模拟题
谁骂着毒瘤的你
谁看了你的题解笔记
谁传给学妹学弟

同行的日子都远去
我们也终会退役
多年后谁会再想起
定格考场的记忆
谁记得你出的模拟题
谁忘记毒瘤的你
谁学会你的题解笔记
谁教给学妹学弟

好 T2，比 CF 的 T2 和 AT 的 T2 质量高多了。

10.22

没什么好说的。

啊？T2 挂了？

rp += 40。

构造的数据有 40 分 -1，然后全挂完了。

注意细节，注意不到就对拍。

要严谨。细↗节↓，决定成败。

对拍对拍对拍。

T3 可爱计数。还得是容斥。

T4 正解有点科技，但不多。如果每次查询的区间长度相等，可以按查询区间长度分块处理块内前后缀，查询时合并一个后缀和一个前缀，比直接套数据结构少一个拆区间的 log。

10.23 码拉松

今年提高组必不可能考大模拟。

10.24

没什么好说的。

啊？T3 挂了？

rp += 40。

std::vector<int> ans;
std::set<int> set;
for (int j = 1; j <= size; j++)
{
    int k;
    do k = rand() % m + 1;
    while (set.count(k));
    ans.push_back(k);
}

CSP\tiny\text{——}\mathbb{C}\text{ontain }\mathbb{S}\text{ecure }\mathbb{P}\text{rotect }2024

上周降掉的智和这周挂掉的分都是会回来的。

Day -1 + 0.0（10.25 a.m.）

板子。

字符串：KMP，exKMP，最小表示法，Manacher。

图论：欧拉路径，Tarjan，2-SAT，Prufer，二分图最大匹配。

数学：欧拉函数，exGCD，exCRT，exLucas，高斯消元。

数据结构：扫描线，线段树合并，动态 DP。

Day -1 + 0.5（10.25 p.m.）

试机。

参考资料：感性理解 LibreOJ 测评机速度。

-std=c++14 -O2，五次取平均。

仅供参考。

赢赢赢。

Day 1 + 0.0（10.26 a.m.）

1.5h 写完睡觉。

睡了 1h 起来卡 T4 的常，把用几个大样例拼起来的极限数据卡进 1.9s 之后就卡不动了，继续睡觉。

T3 是好题。

Day 1 + 0.5（10.26 p.m.）

暴戾语言（包括但不限于“唐”）。

T3 是神秘线段树优化费用提前计算 DP。

设 f_{i, j} 表示 [j, i] 区间同色，且与 i + 1 和 j - 1 异色时 [1, i + 1] 的最大得分，g_i = \max\limits_j{f_{i,j}}，s_i = \sum\limits_{j = 1}^i a_i [a_i = a_{i - 1}]。

设 T1_{i, j} = \max\limits_{k = 0}^{i} g_k - s_{k + 1} [a_k = j]。

则 f_{i, i} = s_{i - 1} + (a_{i + 1} [a_{i + 1} = a_{i - 1}]) +\max(T1_{i - 2, a_i} + a_i, \max\limits_{j} T1_{i - 2, j})。

两个转移分别用一个线段树维护就行。

然后又被卡常了。

注意到线段树只有单点和全局操作，所以可以只用一个整体的 tag 维护。

然后 T4 就没时间写了。

T3 是好题。

但凡找到一个性质也不至于一个性质都没找到。

upd：辱骂 CCF 后一分没挂。

Week 14

退竞赛了。全面回归综合。

有一种一个月前在学校不做综合作业然后回家一点睡觉的那个强度翻了四倍的美。

要收 \not = 要交，不等式秒了。

11.2 组队赛

退综合了。全面回归竞赛。

Week 15

11.4 DP 特训

因为要投稿，而且依托公式太卡了，所以放到 DP 特训。

11.5 美国总统大选投票暨原定 CSP 成绩发布

会赢的。

https://www.luogu.com/article/w2n1kdya

赢了。

11.6 组队赛

组队赛。

11.8 具有教育意义的短会

遵守闺房的鸡腚。

11.8 集训队互测 #1

退综合了。全面回归竞赛。

好题啊，后面忘了。

不会数树啊。

T4 好题。

CCPC 重庆站

@nb_jzy 端茶倒水，@i_love_xqh 喝茶，我喝水。

赛前到处乱走成功带歪了所有人排的队，使得比赛延迟了 20 分钟。

开场发现不会在 linux 终端粘贴，遂转 vscode。

居然把 easy 做完了，这么有实力。

三个人三小时做不出构造，这么有实力。

Week 16

11.12

省流：困，早点睡。

继续困困困。

想了一中午也没想明白上午为什么要在 T3 想到分治的情况下开神秘计数题。

看了一下 T1，好像不太会，但是暴力有 80，打完跑路。

看了一下 T2，看着就是容斥，跑路。

看了一下 T3，是数据结构，看着就像笛卡尔树分治。但感觉不好写（赛后发现比 T1 的暴力短）。还是看 T2 吧，毕竟容斥题应该都过了。

不想看 T4。

不能再困困困了，一定要在 12 点之前睡。

原来 T2 不是容斥啊，，，

T1 和 T3 再稍微想一下都是能想到正解的。

都是套路题。

除了 T2 都是好题。

T4 曼哈顿转切比雪夫，然后用主席树单 log 实现静态在线二维数点。

转切比雪夫可以上数据结构，转曼哈顿可以横纵坐标分开算贡献。

转化后是整点的原来不一定是整点，所以需要且仅需要对于矩形的角特殊处理。

T2 发现直接 DP 会算重，还不能容斥，所以我们考虑直接统计所有的答案。

DP 套 DP。dp of dp。

和一般的计数题一样，依然是集合的划分和容斥。

但从面向过程的计数改为面向结果的计数。

考虑把所有的答案放到自动机里可以不重不漏地统计，而自动机判定出来的结果数不会很多，所以直接记录在当前阶段中在自动机的每个状态里的答案数量。

自动机上 DP。

2024 年女娲补天事件。

11.14

省流：不怎么困了。

后两题的 25 分暴力大概是不超过 25 分钟的。

速度主要被 T1 的构造部分拖了，想到大致思路又没仔细想正确性来源，就对着样例硬凑。

T3 如果放 DP 特训里过的人应该会多一点。

有三个按右端点排序的区间 [l_1, r_1]，[l_2, r_2]，[l_3, r_3]（r_1 \le r_2 \le r_3），若区间 1 交区间 3 且不交区间 2，则 l_3 \le r_1 < l_2，那么区间 2 必然交区间 3，所以没有后效性。

T4 经典图论建模，细节比较多，需要精细地维护以达到较好的复杂度。粗糙地维护也行。

11.16

省流：节省流量的意思。

比赛策略已经差不多了，打成依托纯粹是实力问题。

为什么开多测。

信什么不好信大样例。

真的不会数树啊。

有标号的完全二分图 K_{n, m} 的生成树数量为 n^{m - 1} \times m^{n - 1}。

考虑其生成树的 prüfer 序的构造过程：每次删除编号最小的叶子节点且在 prüfer 序中加入其对面的点。最后剩下的是两侧各一个点。

所以 prüfer 序中有 m - 1 个左侧点，n - 1 个右侧点，数量为 C_{n + m - 2}^{n - 1} \times n^{m - 1} \times m^{n - 1}。

但这个柿子实际上算的是有 n + m 个点且可以作为二分图的生成树的树的个数，即区分图上除了最后剩的点外每个点，所以还要除以 C_{n + m - 2}^{n - 1}。而 T3 中真的区分 n + m 个点，所以不用除。

不会，摆了。

https://www.luogu.com/article/qg2v7pxp

https://www.cnblogs.com/A-zjzj/p/17526938.html

密度大的部分放到 11.16 考试总结、周总结、半期总结 防止沉底。

Week 17

11.19

省流：应该是补不完题了。

好像是最近第一次开出计数题。泪目了。

MLE 挂完。这下真的泪目了。

100 遍 1024MB：

1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 1024MB 1024MB 1024MB 
1024MB 1024MB 

还有一个 1024MB 在评论区。

好像除了 T2 因为数组开大挂了 100 而且在剩下的将近两个小时内完全没有注意到以外并没有特别大的失误。

这下双赢了。不仅做出了题，还避免了以后犯低级错误。

唉。

https://www.luogu.com/article/pei2biw2

并不高级的挂分原因：

-1. CE/FE

-Wall -Wextra -O2 -std=c++14 -Wshadow -Wconversion

0. any

静态查错 + 对拍 + 手动构造特殊/极端数据。

如果没有时间打暴力对拍，也要构造极端数据。

1. WA

没删调试。数据类型。多测没清空。n，m 写反。取模。

虽然好像一般过不了大样例。

各种数据。

2. RE/TLE

数组开小。没用快读快写。没卡常。

极限数据。

3. MLE

可能是大样例并不弱的情况下唯一在本地不容易看出来的的错误。而且可以一次挂掉 100。

解决方法大概就是注意特殊的空间限制以及开大数组的时候更加警觉。

静态空间：输出地址。 windows 下，在 cmd 中输入 size xxx.exe 查看某可执行文件的的静态空间大小，以 Byte 为单位。

动态空间：如果空间比较极限就少用 64 位指针和 STL。但反正不会挂完，无所谓了。

upd：可以用资源管理器查看动态空间。

T3 是奇妙题。

首先，有繁衍公式 x = \sum\limits_{i = 1}^{\infty} [i \le x] (x \in \mathbf{N})。

把较难处理的序列比较转为 01 序列比较。

所以有 \sum\limits_{i = x}^y a_i = \sum\limits_{i = x}^y \sum\limits_{V = 1}^{\infty} [a_i \ge V] = \sum\limits_{V = 1}^{\infty} \sum\limits_{i = x}^y [a_i \ge V] = (\sum\limits_{V = 1}^{\infty} \sum\limits_{i = x}^r [a_i \ge V]) - (\sum\limits_{V = 1}^{\infty} \sum\limits_{i = y + 1}^r [a_i \ge V])。

对于 \sum\limits_{V = 1}^{\infty} \sum\limits_{i = p}^r [a_i \ge V]，也就是原区间的一段后缀，不难发现其取值为

又发现 \sum\limits_{i = p}^{\min(p + k - 1, r)} [b_i < V] 随 V 的增大而增大，\sum\limits_{i = l}^{p - 1} [b_i \ge V] 随 V 的增大而减小，取两者较小值的分界点算贡献可以二分。

设当 V \le v 时，\sum\limits_{i = p}^{\min(p + k - 1, r)} [b_i < V] \le \sum\limits_{i = l}^{p - 1} [b_i \ge V]，那么答案就是

启发大概是比较大小可以转成更直观的 01。再就是转成 01 不一定是二进制。

T4 更是奇妙题。

既然求的是 \sum f(w, b) \cdot w \cdot b，说明真的要把 f 都算出来。

不妨设 w \ge b。

如果某个点的所有子树（无根意义下）的大小都 < w，那么这个点必然一定是白色。反之，如果某个点存在子树的大小 \ge w，那么这个点必然不一定是白色。

设必然是白色的的点集为 S。

如果 S \not = \varnothing，那么将重心作为根，S 构成包含根的连通块，f(w, b) 就是删去 S 后大小 \ge b 的子树个数。

如果 S = \varnothing，那么 f(w, b) 取值 1 或 2。f(w, b) 取 1 当且仅当存在一个节点的子树中有两个大小 \ge w，且另有一个 \ge b。

启发大概是 T4 想不出来就别想了，是想不出来的。

11.20 ARC187 补题

A 题冒泡。注意到允许操作次数极多，而且交换两个数再交换回去可以使两个数都加 k，所以乱搞就行。

B 题计数。注意到 f(A) = 1 + \sum\limits_{i = 1}^{n - 1} [(\min\limits_{j = 1}^i a_j) > (\max\limits_{j = i + 1}^n a_j)]，所以算贡献就行。

C 题冒泡计数。注意到是紫题，所以不会做。

11.21

省流：不知道。

T1 瞪了半天不会。

看 T2，很板啊。

询问所有长度为 k 的区间时，考虑对于每种颜色分别统计其在多少个区间中出现。

再考虑容斥。对于每个长度为 l 的没有这种颜色的极长区间，会包含 l - k + 1 个长度为 k 的区间，使这些区间不出现这种颜色。

再发现所有颜色的没有出现的极长区间个数的总和是线性的，所以可以对所有颜色同时统计，答案就是 (n - k + 1) \times n - \sum\limits_{l \ge k} l - k + 1，完了。

考完发现和别人做的好像不是同一个 T2。

再看 T1，还是不会。

然后决定打部分分，然后会了。

然后后面 2.5 小时罚坐。

T3 好像是觉得有容量限制，所以不能贪心，就一直在想图论，比如曼哈顿转切比雪夫再优化建图。倒是最后乱搞的想法和正解有点关系。

11.23 集训队互测 #2

对不起，jzy 错了。

获得奖励的请在期限内找出题组兑奖。过期无效。

最终解释权归出题组所有。

李超线段树维护二次函数

Week 18

稍息立正站好 请报到 第一眼微笑
抬头挺胸收腰 别尖叫 胸口怦怦跳
灯光镜头前摇 准备好 倒数前三秒
脸上红晕朵朵 管不了
你最最最重要

11.25 ARC188 补题

A 题不会。

11.26

T2 还是觉得是神秘数论/超纲知识（Pollard Rho？），就没怎么想。但正解也没那么神秘。

经典问题了。问题在于应该先仔细想再判断会不会，而不是觉得不会而且放 T2 就不想了。即使真的不会，多想一想总是好的。

造成这种情况的原因好像是过于相信自己的直觉了。毕竟我一眼没思路的题一般都没什么人做，谢罪。

还有就是 T2 一般是不会给 75 分暴力的。然而这并不是 T2。

T3 写了一个错解后发现不会。

DP 套 DP 做少了，只做板子显然是不够的。虽然这道题也很板。再就是 DP 也做少了。

T4 思路好像比较明显，而且其他题都不太可做，就开始写。但是 \operatorname{mex} 不会，导致异或也不会。

任何比赛策略上的失误都是由于对个人能力和题目难度认知不清晰导致的。

比如我应该知道我两个小时写不出 T4 的。

想都想到了，不写就亏了。暴力打满又进不了省队，正解不写就后悔一辈子。

但在明知自己大概率写不完的情况下应该先把思路实现出来，再考虑数据结构。

T3T4 的部分分还是有不少的。甚至比 T4 的双 log 还高。

说到底还是实力问题。

反正今年 NOIP 打得再好也进不了省队，况且一段时间内也打不了正式比赛了，在接下来的一年里提升实力才是正经事。

但实力的提升也不该只是寄希望于时间和套路的积累。

因为从上一次定目标到现在一场 CF 都没打，所以目标还是 2000。

冬令营争取拿约。如果能进的话。

四道题两道树上问题是跟我学的吗。

至少题出的是近几年 S 组和 NOIP 最好的一次。特批肚子的的马复活一个月。

押题得分和估分一样怎么办。

有一个重要的启发，就是数据结构题一定要先打暴力，以免做法假掉或调不出来，心态爆炸遗憾离场。

还有一个重要的启发，就是需要用部分分打区分度的比赛是失败的，因为没有打部分分被区分的选手是失败的。

Week 19

退竞赛了。

I said certified freak, seven days a week

后面忘了。

12.7 组队赛

组队赛。

字数统计：28936 字符。