做题记录

发表于 2024-11-14 更新于 2025-03-04 分类于 OI 阅读次数： 20 本文字数： 8.6k 阅读时长 ≈ 16 分钟

徒留浅痕，为证永存。

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

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$ 求出最大的 $d p_{u} = c_{v} - 2 \times d i s w (u t o v)$ ，换根可求出。那么路径 $x$ 到 $y$ 的答案即该路径上所有 $d p_{u}$ 的最大值。（实际上最优方案一定在其中，且最优方案的为最优点 $z$ 到路径上距离最短的点的 $d p$ 值）。这里可以思考一下为什么，这个 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

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

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$ 时，在开始需要多少额外兵力才可占领所有点。

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

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)$ 即可，权值为 $d e p_{l c a (i, i + 1)}$ ）。那么询问即为与给定区间 $[l, r - 1]$ 相交至少为 $k - 1$ 长的区间中最大权值。
两种情况分讨即可：

$y \geq r - 1 \land x \leq r - k + 1$ 。
$y - x + 1 \geq k - 1 \land 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，原因是区间加没有乘上 $s z$ 。
我唐完了。

2025.1.6

P2486 [SDOI2011] 染色

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

LCT 学习链接

有点好用。

P7219 [JOISC2020] 星座 3

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

P1195 口袋的天空

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

2025.1.7

P4219 [BJOI2014] 大融合

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

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] \dots$ 。
那么对于初始串 $S [i, j]$ ，下界为 $m i n (\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$ 变为 $A A$ ， $B$ 同理。
然后非常妙的思路是直接将两个拼接在一起。
注意应该是这种形式 $A A + 极小字符 + B B + 极大字符$ ，原因是题目中要求 $A$ 小于等于 $B$ 。
然后直接用 SA 数组，求前缀和即可。

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

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

P4770 [NOI2018] 你的名字

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

P6292 区间本质不同子串个数

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

P6335 [COCI2007-2008#1] STAZA

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

P8339 [AHOI2022] 钥匙

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

P8329 [ZJOI2022] 树

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

AT_arc150_d [ARC150D] Removing Gacha

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

P4638 [SHOI2011] 银行家

开始写网络流了。
实际上主要就是建图吧，比较巧的是客户之间连边，可以多想一想。
总之网络流只要不是太炸裂就不是很担心复杂度。

2025.2.13

P7519 [省选联考 2021 A/B 卷] 滚榜

60pts 的爆搜很好想。实际上加一个爆搜转状压再加一个贡献提前计算就行了。
比较好写。

CF14E Camels

由于不能有相邻相同的，可看作：“峰谷峰谷峰谷峰”的形式。
随便做即可，可优化到 $O (n m V^{2})$ ，其中 $V$ 是值域即为 $4$ 。

2025.2.14

P4655 [CEOI 2017] Building Bridges

李超线段树优化斜率 dp。

CF372C Watching Fireworks is Fun

两个方向各一次单调队列优化 dp。

P1792 [国家集训队] 种树

wqs 二分，当然也可以链表维护反悔贪心。

P6246 [IOI 2000] 邮局加强版加强版

普通版随便过。一次加强版用上了决策单调性（即四边形不等式）。
二次加强版考虑 wqs 二分，代价与邮局的个数的函数是有凸性的（意会一下，实在不行打表），那么考虑 wqs 二分。
于是变成了一维决策单调性，还是满足四边形不等式的。那么直接做即可。

[TJOI2017] 可乐（数据加强版）

矩阵加速，直接把图的邻接矩阵拿去跑矩阵快速幂即可。

P3216 [HNOI2011] 数学作业

矩阵加速，脑残点在于要开 unsigned long long 不然会爆炸。

2025.2.15

P3502 [POI 2010] CHO-Hamsters

kmp 加矩阵加速，注意字符串之间不会包含。

CF165E Compatible Numbers

高维前缀和。做完了发现以前写过…无效学习+1。

CF449D Jzzhu and Numbers

高维容斥。钦定一下就比较好做。

AT_arc137_d [ARC137D] Prefix XORs

考虑把这个转化为一个二维上的 dp，发现前面对后面项的贡献次数有组合意义下的化简式子。
由于是异或，所以贡献要对 $2$ 取模，用卢卡斯，发现 $Misplaced &$ ，即 $Misplaced &$ ，用高维前缀和做即可。

P4644 [USACO05DEC] Cleaning Shifts S

若至题。写来凑数。

P3565 [POI 2014] HOT-Hotels

可以写一个 $O (n^{2})$ 暴力，然后你发现空间 $n^{2}$ 被卡爆。
写长剖就过了。

P5904 [POI 2014] HOT-Hotels 加强版

跟上题一模一样，空间开大点就过了。

2025.2.16

CF739E Gosha is hunting

很有意思的费用流。可能被卡精度。当然也可以使用 wqs 二分。

P3426 [POI 2005] SZA-Template

好玩的 kmp+dp。

P5829 【模板】失配树

失配树板子。

P3193 [HNOI2008] GT考试

失配指针套矩阵快速幂。

2025.2.17

P5496 【模板】回文自动机（PAM）

回文自动机板子。

2025.2.19

CF1083F The Fair Nut and Amusing Xor

写了一天。唐完了。

P3806 【模板】点分治 1

复习板子。

P2396 yyy loves Maths VII

简答状压。记得用 lowbit 优化枚举过程防止超时。

2025.2.20

全在复习。再不复习就似了。

P2150 [NOI2015] 寿司晚宴

对素数状压。注意每个比 $22$ 大的素数最多有一个，那么可以按照这个大素数进行分组 dp。
注意合并的细节。

2025.2.23

P2617 Dynamic Rankings

整体二分。

2025.2.25

P5631 最小mex生成树

考虑一个权值如若不在生成树的边权集合中出现，那么可以作为 mex。
于是线段树分治，从小到大枚举权值判断即可。

2025.2.26

P8365 [LNOI2022] 吃

很容易想到一个 $\frac{b}{a - 1}$ 的贪心，只是是假的。真正该比较的应该是 $\frac{s u m + b}{a}$ ，但这个是可能变化的。
然后瞪一下样例，发现除了 $a = 1$ 的情况必定选择加，至多会有一次加操作。
很好证，当然我直接猜结论了。然后直接找到最大的那一次直接做即可。

2025.2.27

P8360 [SNOI2022] 军队

“扫码了，卡nm一天！”
逆天分块硬控我一天，实力不够导致的。并查集只会乱写了。

2025.2.28

P9166 [省选联考 2023] 火车站

2022 联合省选 D1t1。酒店里写了 1h 唐麻了。

后记

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