做题记录

徒留浅痕，为证永存。

突然想起来有个东西叫做 做题记录。
完了，啥也没写（虽然第一次知道这玩意已经是快要高二了，根本来不及写）。现在开始写应该不晚吧？
总之在退役之前才开始写做题记录。应该没有人像我一样抽象。

2024.11.14

UVA12983 The Battle of Chibi

rz 题，我也不知道为什么我要写。随便搓个 $3$ 维 dp 然后 BIT 优化一下就过了。

P2375 [NOI2014] 动物园

重温经典。想了一下当时的作法并且重新打了一遍。至少对于字符串有点手感了。

P9026 [CCC2021 S4] Daily Commute

ez，bfs 求距离然后拿 set 或者优先队列（延迟删除）记录答案。唯一比较唐的地方是单向边建成双向边导致样例没过（雾。

2024.11.15

生病请假。

2024.11.18

回归。

P9326 [CCC 2023 S3] Palindromic Poster

非常有意思的构造题。分讨一下即可。

P9606 [CERC2019] ABB

kmp（复制一遍、翻转并扔到最前面直接 kmp） / manarcher（直接做） 解决。神秘串串题。

P8085 [COCI2011-2012#4] KRIPTOGRAM

有一个非常有意思的 trick 转换。直接把相邻字符之间的距离拿来当串跑 kmp，比较有意思。

2024.11.19

P11069 「QMSOI R1」 生熏鱼

rz 背包题。不知道为什么卡了那么久。

P10449 费解的开关

bfs 爆搜。md 本来只用全局做一次的，我非得 T 组数据跑 T 次，结果自然是 T 飞。不知道为什么卡了这么久。

P11012 「ALFR Round 4」B 颜料

有意思的双指针。感觉 $O(n)$ 的写法有点奇妙，值得消化理解。

2024.11.20

P10403 「XSOI-R1」跳跃游戏

st 表维护区间 gcd，然后套个双指针即可。
发现题解区全是神秘二分，顺便写了篇 题解。

P9402 [POI 2020/2021 R3] Droga do domu

一个神秘的分层图。把路线当作链单独建点处理，然后直接 dp 即可（因为是链）。细节比较复杂，最好还是看代码多理解一下。

2024.11.24

P9374 「DROI」Round 2 单图

搞清楚符合题意的两种情况后，直接组合数计算即可，没有任何优化。

P9235 [蓝桥杯 2023 省 A] 网络稳定性

建完 kruskal 直接跑树上 lca 即可。怎么这么板？还是个蓝的。

P11323 【MX-S7-T1】「SMOI-R2」Happy Card

分讨，将 4 的情况拆成 3+1，然后尽量多 3 带，贪心 + 分讨。

2024.11.25

P11324 【MX-S7-T2】「SMOI-R2」Speaker

有点意思。
首先首尾的利润和路上必经边的路费和可前缀和计算，实际上要求的是 $z$ 的利润减去 $2$ 倍的 $z$ 到 $x$ 至 $y$ 这条路径的路费（来回，所以两倍），这部分考虑特殊处理。
对于每个点 $u$ 求出最大的 $dp_u = c_v-2\times disw(u\ to\ v)$，换根可求出。那么路径 $x$ 到 $y$ 的答案即该路径上所有 $dp_u$ 的最大值。（实际上最优方案一定在其中，且最优方案的为最优点 $z$ 到路径上距离最短的点的 $dp$ 值）。这里可以思考一下为什么，这个 trick 有点妙，有点常见。
然后换根和倍增处理完所有就可以做完了。

2024.11.26

多少还是得写点题。

P4116 Qtree3

树剖，然后拿 set 维护重链，查询时跳链即可。

P5838 [USACO19DEC] Milk Visits G

可以树剖和 set 维护，也可以树剖和主席树，但我选择暴力建 $n$ 棵树然后动态开点。
（听说还有 $O(n+m)$ 的神秘线性做法？我 ds 学傻了）

P5836 [USACO19DEC] Milk Visits S

上面那玩意的弱化版，Ctrl C+V 过了。

P3313 [SDOI2014] 旅行

树剖 and 动态开点。不知道为什么是个紫的。

其他

乱打了一些板子，就当是康复训练了。

2024.11.27

实际上今天没有写题，但是考试考了 $330pts$，奖励自己一天。

2024.11.28

P4551 最长异或路径

水题。树上差分 and Trie 树秒了。

2024.12.9

中途一直学 whk，现在回来补 OI。

P1533 可怜的狗狗

整体二分板子。打了一下发现不难理解。

P3527 [POI2011] MET-Meteors

整体二分典中典。二分时间可得。比较恶心的是这个阴间题目有几个数据点会爆 long long，有人说边加边特判，我听不懂直接 __int128。
10 min 后打脸了。luogu 上时限给的 2s，所以过了。ybtoj 上给的 1 s，所以被卡常了。被迫用 long long 写了个特判才过。

P3242 [HNOI2015] 接水果

写了将近半天（中午耽误太久了）。
首先考虑将路径的包含问题转化为 dfn 序的大小问题（即每个点记录 $L_u$ 和 $R_u$ 表示子树内 dfn 序的区间），然后根据路径一个端点是否是另一个端点的祖先分讨，可以得到两个偏序关系，即二维平面上的一个矩阵。
可以使用树套树，但是直接扫描线会更好。套个整体二分解决事情。
调了这么久主要是注意二维区间的两个维度不能轻易交换，发现矩阵的两个维度的区间不相交，故钦定 dfn 序小的为第一维（大的同理），然后做扫描线。
代码不长，注意一些细节：空间和离散化问题。

P3332 [ZJOI2013] K大数查询

比较板的题。整体二分随便艹一下就能过。由于不会区间加的树状数组，所以被迫写线段树。
调了 30min 的整体二分发现是线段树写锅了（雾。

P1527 [国家集训队] 矩阵乘法

整体二分板子。但是套二维树状数组。

2024.12.10

上午的考试

烤焦了。

Test 12.10 T1

简述一下：一张 $n$ 点 $m$ 边的图，每个点有点权 $P_u$，初始占领 $s$。你可以占领 $u$ 当且仅当：

• 所有已占领的点权和 $\leq P_u$。
• 存在一个已被占领的点 $v$ 满足边 $(u,v)$ 存在。
  你需要对所有点都求出其作为 $s$ 时，在开始需要多少额外兵力才可占领所有点。

实际上不是很难，想复杂了。
考虑每条边的边权设为 $max(P_u,P_v)$，当前连通块的点权和大于该边则可以直接通过，否则就要加额外兵力，那么实际上实在建生成树。
建出 kruskal 重构树，对于非叶子节点（点权为 $w_u$），左右两棵子树内部的点要互相到达，左子树内的点权和 $sl$ （sum in left subtree）必须大于该节点的边权限制，否则左子树内部的点的答案需对 $sl-w_u$ 取 $max$，右子树同理。
代码很好写。

Test 12.10 T2&&T3

T2 省流：维护二维区间内一次函数最大值，用 扫描线+线段树套李超树解决。考场想到了，但那又有什么用呢？
T3 省流：什么玩意的五维 dp，不会，点 这里 跳楼。

然后发现有人试图用 O(n^2) 瞎几把过 T2，好像卡卡常还真能过？

改题

然后今天一天都在红温，瞎几把改。

2024.12.11

上午考试

喜提爆零。

Test 12.11 T1

神秘算法，乱几把建图然后跑有向图最小树形图。关键还需要左偏树/平衡树优化。

Test 12.11 T2

不会 dp 套 dp。最近怎么这么多 dp 套 dp？

Test 12.11 T3

斐波那契好题。后面的数据结构不会维护。

P11364 [NOIP2024] 树上查询

NOIP T4。
搞了半天终于做懂了。
考虑区间 lca 为区间内每两点之间的 lca 中深度最浅的那一个，那么我们可以建出笛卡尔树（不建也行，只要找到每两个点之间 lca 为最小值对应的极大区间 $(x,y)$ 即可，权值为 $dep_{lca(i,i+1)}$）。那么询问即为与给定区间 $[l,r-1]$ 相交至少为 $k-1$ 长的区间中最大权值。
两种情况分讨即可：

• $y\geq r-1 \wedge x\leq r-k+1$。
• $y-x+1\geq k-1\wedge l+k-1\leq y\leq r-1$。
  然后就把修改（初始化的所有区间视作添加）询问扔一块，分别扫描线：前者按照 $r/y$ 从大到小排序做，后者按照 $(k-1)/(y-x+1)$ 从大到小排序做，注意修改需在询问前做的限制。
  然后两种情况取最大值，$k=1$ 时单独处理，就做完了。根本不需什么树上启发式合并的抽象玩意。

P10614

模拟赛考了两次 dp 套 dp，故写了板子题。

2024.12.12

上午

听讲。啥都没听懂。

P4590 [TJOI2018] 游园会

还是 dp 套 dp 板子。

2024.12.13

模拟赛 T1 && P5863 [SEERC2018] Numbers

改了题。还算好写吧。

AT_abc261_h [ABC261Ex] Game on Graph

老师要求的题单里的一道。有向图博弈中比较经典的一类。稍微有些变式。
dp 方程转 dijkstra 比较巧妙，我这样的菜逼没接触过。

2024.12.16

闲话

前几天放假，耍水，只字未动。

AT_abc264_h [ABC264Ex] Perfect Binary Tree

树形动态 dp。实际上暴力修改都行，而且复杂度正确。
但是 rz 数组越界卡了我 30min，不望周知。

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

莫队二次离线，比较有意思的一个科技。
字面意思，将莫队的查询再离线下来，使用值域分块之类解决。
小细节写出问题了，被硬控一天。

2024.12.18

AT_abc283_h [ABC283Ex] Popcount Sum

中间在摆烂。
类欧，不会，学了一下，公式还是背不住，不背了，摆大栏。

2024.12.26

不要在意时间。

AT_abc313_h [ABC313Ex] Group Photo

将 ab 数组从大到小排序后连续段 dp，新加入一个数实际上就是考虑合并的一些问题，包括新开一个连续段、放在已有的连续段的左右两边、合并两个连续段。竟然比较简单。

CF1965C Folding Strip

可以考虑一个贪心：遇到相邻的就折。非常粗暴，关键是还是对的。

2025.1.4

woc 在复习物理合格考的时候被赶回来学 OI。

P3690 【模板】动态树（LCT）

重新写了一遍。现在总算会用了。

P3203 [HNOI2010] 弹飞绵羊

LCT 裸题。甚至不用换根，所以断边有一种非常巧妙的写法。
实际上这种情况的断边就是 splay 上取消联通性。加边直接连轻边即可。

2025.1.5

P1501 [国家集训队] Tree II

同板子。
调了 0.5h，原因是区间加没有乘上 $sz$。
我唐完了。

2025.1.6

P2486 [SDOI2011] 染色

可以用树剖，而且这样直接暴力思路就行。
但是合并区间很麻烦，不如写 LCT。
考虑转边权。两端点颜色不同，为 1；否则为 0。
答案即为路径边权和再加 1。
注意结点需维护 splay 子树内最左和最右的颜色；warning：区间取反时需要把这个也取反（没取反调了 10min）。
然后轻松过。

LCT 学习链接

有点好用。

P7219 [JOISC2020] 星座 3

考虑建笛卡尔树，发现这样比较复杂，所以不建了（雾）。
考虑反悔贪心，也比较麻烦，所以不考虑（大雾）。
如果从下往上考虑，可以直接贪心：当前的星星与下面的一坨星星冲突，那么要么舍弃当前，要么舍弃下面那一坨，则有贪心：直接舍弃权值较小的那一方。看起来很扯淡，但是是对的。感性理解吧。
实际上是一个笛卡尔树合并的过程。由于大区间必然覆盖掉子树内所有小区间，所以这样是对的。
非常妙。从下往上，用并查集和树状数组来维护冲突的价值和。

P1195 口袋的天空

我也不知道我为什么写这个黄题。估计是想爆切水题了。

2025.1.7

P4219 [BJOI2014] 大融合

LCT 可以考虑维护子树和之类的问题了。
比如子树和：具体做法就是每个点维护 $si$ 表示虚儿子的子树和。只需要在 access、link、cut 三个操作的时候同时更改即可（因为其他的操作不会改变儿子的虚实），pushup 的时候记得加上 $si$，其他部分不变。
这个题这么做就完了。

2025.1.10

P2619 [国家集训队] Tree I

wqs 二分板子。学了一下发现非常简单。所以要多学。

2025.1.11

CF375D Tree and Queries

树上启发式合并板子。我太喜欢板子了。表白板子。

2025.1.17

P3804 【模板】后缀自动机（SAM）

后缀自动机。理解成 parent tree+Trie(有向图) 即可。

P8368 [LNOI2022] 串

下届为 $\frac{n}{2}$，考虑更优：
逆向思考：对于 S 串，逆向变化为：$[i,j]->[i-1,,j-2]->[i-2,j-4]…$。
那么对于初始串 $S[i,j]$，下界为 $min(\frac{n}{2},i-j+1)$。
观察到有一个性质：对于一个出现了两次及以上的子串 $[i_1,j_1],[i_2,j_2]$，那么我们从 $[i_2,j_2]$ 开始，然后不断变化，当左端点跳到 $i_1$​ 时，我们跳回到 $i_2$​ 即可。
一次，我们可以实现两个串之间来回跳，答案为 $r−l+1+(n−r)/2$。
所以记录每个节点最靠左的右端点和串的个数，取最大值即可。
说的很抽象，建议看代码和题解。这里仅用作帮助回忆。

AT_abc272_f [ABC272F] Two Strings

考虑断环为链。串 $A$ 变为 $AA$，$B$ 同理。
然后非常妙的思路是直接将两个拼接在一起。
注意应该是这种形式 $AA+极小字符+BB+极大字符$，原因是题目中要求 $A$ 小于等于 $B$。
然后直接用 SA 数组，求前缀和即可。

P6139 【模板】广义后缀自动机（广义 SAM）

加了一点特判，其余部分照旧。
在线做法应该只有我写的这一种是对的，其他的正确性伪了。
当然也可以考虑一下其他离线做法。

P4770 [NOI2018] 你的名字

PS：（哮喘！）（喘气~）（窒息）（拼命呼吸！）你的名字！
我觉得比较神仙。
先考虑对于所有询问，$l=1,r=|S|$ 怎么做。
建出 $S$ 的后缀自动机，然后让 $T$ 在上面跑匹配，得出 $T$ 上每个结点能在 $S$ 匹配的最长后缀长度 $lim$，答案为 $max(0ll,len-max(lim, len))$。
接下来考虑带 $l, r$ 怎么做。
我们发现我们在匹配时，只需要保证匹配到的 $S$ 子串为 $S[l,r]$ 的子串即可，即 $endpos$ 在 $[l+|S’|, r]$ 之间（$S’$ 为匹配到的子串）。
那么用线段树合并来维护每个点上的 $endpos$ 集合，在保证区间能匹配的情况下继续走，否则直接跳 parent tree，最后正常统计答案。
妙啊。

P6292 区间本质不同子串个数

考虑扫描线。用线段树统计区间，LCT 模拟右端点右移的变化。其他的懒得说，SAM 套LCT上线段树+扫描线。

P6335 [COCI2007-2008#1] STAZA

说是跟圆方树相关。实则有做法不用。
由于每条边只能经过一次，那么考虑两个状态：$f_u,g_u$ 分别表示 $u$ 往下走但是最终回来、$u$ 往下走一去不回。
如果走在一条非环边上，则只会对后者造成贡献；否则遍历这个环，对环进行统计。
有个思路就是 $u$ 尽量多走一些环然后回来，最后一去不回（但是不一定把该点上的所有环跑完，可能有一个环走到一半出去了）。那么有 $g_u=f_u+mx$，计算 $mx$ 最大值即可。
太水了，那天重新学习一下圆方树。

P8339 [AHOI2022] 钥匙

每个颜色建虚树，考虑钥匙和宝箱实际上是括号匹配，相当于从钥匙处 dfs，其他钥匙能开的宝箱它就不造成贡献，只有没有其它钥匙了才开。那么转化到 dfn 序上实际上就是一个二维贡献问题，扫描线+BIT 可以过。
注意细节。

P8329 [ZJOI2022] 树

容斥吧。
设计状态 $dp_{i,j,k}$ 表示当前第 $i$ 个数，$[1,i]$ 中有 $j$ 非叶子结点，$[i+1,n]$ 中有 $k$ 个非叶子结点。
但是发现这样容易出问题：如果当前点是叶子结点那是没有问题，问题在于非叶子结点一定有儿子吗？
$O(n^3)$ 复杂度顶天，不可能 $O(n^5)$ 每棵树多记一维状态，那么容斥吧。
实际上实现很简单：比如这个点假设扔给第一棵树当叶子，第二棵树非叶子，那我们用上面的式子减去强制第二棵树是叶子的情况就好了，即 $dp_{i,j,k}=dp_{i-1,j,k+1}\times j\times (k+1)-dp_{i-1,j,k}\times j\times k$（这个系数是乘法原理），反之同理。
然后容斥下来记答案即可。
其实我现在都不是很懂这个题。

AT_arc150_d [ARC150D] Removing Gacha

妙妙期望题。不想写做法了，懒。

后记

留下回忆之处，触着碰着，都是带刺的花。