持久化区间修改区间查询线段树：
SP11470 TTM - To the moon
点击查看代码
2. 有后效性的 dp
CF24D Broken robot
一般用高斯消元
求解。
也可以多跑几遍朴素 dp 使误差降到可接受范围内。
多跑几遍的代码
3. P14402 [JOISC 2016] 危险的滑冰 / Dangerous Skating
图论建模。
思考如何移动，即如何建图。无非就是两种方式：
可以通过耗费
的代价走到上下左右连续最远的非冰块的格子。
可以通过耗费
的代价走到相邻的格子。
HZOI2025 KingGojianOfYue's Solution
点击查看代码
4. 树上包含所有关键点的连通块最小大小
P9340 [JOIST 2023] 旅行 / Tourism
题意：树上问题，多次查询包含区间中所有点的连通块最小大小。
关键：包含所有关键点的连通块最小大小是经典问题，虚树中边的数量等于按 dfs 排序后两两相邻的点的距离之和。（第一个和最后一个也相邻）
由于与前驱后继有关，考虑使用链表维护只删不加回滚莫队，然后我们可以做到时间复杂度
。
点击查看代码
5. 折半报警器。
P7603 [THUPC 2021] 鬼街
假设这个报警器要触发报警还需要
次闹鬼，这个报警器监控
个房子。
那么根据鸽巢原理，如果这个警报器触发警报，这个报警器监控的屋子中一定存在一个屋子闹鬼次数
。但是反之则不一定。
将
定义为报警阈值。
我们对每个房间开一个优先队列，记录每一个监视器在该房间处可能报警的闹鬼次数的阈值。
所以当一个屋子的闹鬼次数增加时，我们把那些可能会触发警报的警报器拿出来，判断是否触发警报，如果没触发，那么重新计算
，再往这
个房间的优先队列里添加新的报警阈值。
堆的删除可以使用懒惰删除，维护每个监视器的最新阈值编号（出队次数）、以及堆中每个阈值信息的编号即可。
点击查看代码
6. 扫描线 + 并查集维护值域连续段。
P7907 [Ynoi2005] rmscne
过于高妙，我也不会讲。
点击查看代码
7. 分治优化区间背包问题
P6240 好吃的题目
先考虑不跨过分治中点的贡献，递归回来后再考虑跨过分治中点的贡献，然后合并背包或者暴力跑背包。
更像猫树的写法
更像整体二分的写法（不是这道题）
8. 拉格朗日插值优化 dp
P4463 [集训队互测 2012] calc
适用于转移是卷积的形式。
点击查看代码
9. 不去重离散化
适用于一类权值相同的元素也可以造成贡献的问题。
可以配合 bitset（手写） 。
例题：
经典例题：P4688 [Ynoi Easy Round 2016] 掉进兔子洞
（非正解）需要配合手写 bitset 求权值第
小。P3242 [HNOI2015] 接水果
10. 区间 LCA 深度求和问题
P4211 [LNOI2014] LCA
可以转化为根链上每个点加
，根链查询点权和。
点击查看代码
11. 绝对众数问题：摩尔投票法
P3765 总统选举
基本思想：
注意到这样一个现象：在任何数组中，出现次数大于该数组长度一半的值只能有一个。
摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。
这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。
我们可以用线段树来维护这个过程。注意左右儿子剩的元素相同时的 pushup。
点击查看代码
12. 反射容斥
双线板子题：P3266 [JLOI2015] 骗我呢
点击查看代码
13. 广义（？）矩阵树定理
P3317 [SDOI2014] 重建
点击查看代码
14. 去重方案数问题：
一般是具体问题具体分析。一般是贪心消除重复贡献或者减去重复贡献。
P12930 [USACO4.3] 逢低吸纳 Buy Low, Buy Lower 加强版
点击查看代码
15. 神秘交互题 P12421 【MX-X12-T4】「ALFR Round 5」游戏
做过了还是想不到。
考察题目的性质，发现（？叶子结点的答案一次查询就可以得知。
然后没了。
点击查看代码
16. 将区间查询变为左闭右开（左开右闭），再拆询问为两个单点询问，最后从左到右扫询问
经典 Trick，非常 nb。
左闭右开：P11830 [省选联考 2025] 幸运数字
点击查看代码
17. 一种非恰好
个的矩阵优化的解题方式
思路是在答案矩阵后再拼接一个答案矩阵，最后查询时求矩阵中一段元素的和即可。
P10581 [蓝桥杯 2024 国 A] 重复的串
my sol
18. 神秘树形 dp
设
为将子树染黑还需要多少次操作。
P3554 [POI 2013] LUK-Triumphal arch
点击查看代码
19. 数据点分治
如果你看到一个题的数据范围过于奇怪，不要怀疑自己，可能他真的想让你数据点分治
P3646 [APIO2015] 巴厘岛的雕塑
点击查看代码
20. 排序将有限制（计数）问题的限制减弱
P3077 [USACO13FEB] Route Design G
点击查看代码
21. 移项思想。
把题目中的限制移项，你可能就有更优做法了。
P3089 [USACO13NOV] Pogo-Cow S
点击查看代码
22. 临项交换贪心
P3076 [USACO13FEB] Taxi G
点击查看代码
23. 均分纸牌问题
两种做法，
推柿子得绝对值不等式
三分法求函数极值
P3051 [USACO12MAR] Haybale Restacking G
点击查看代码
24. dp 转移画出转移路径，网格图再求解
AT_abc279_g [ABC279G] At Most 2 Colors my sol
P2516 [HAOI2010] 最长公共子序列
点击查看代码
25. dp[x][y] 两维限制转化为 dp[x] 一维限制，dp[x] 记录 可行的 y 的最小值
设一维 dp 状态，所记录的值是原先二维 dp 数组的第二维的最小值。
可以优化很多。
P2224 [HNOI2001] 产品加工
点击查看代码
26. 分块打表
P1662 数7
点击查看代码
27. 正着做很难做考虑反着做（容斥/二反）
P1450 [HAOI2008] 硬币购物
点击查看代码
28. 在线决策单调性可以单
分治做。
https://www.luogu.com.cn/article/vqf42hah
以下是博客签名，正文无关
本文来自博客园，作者：Wy_x，转载请在文首注明原文链接：https://www.cnblogs.com/Wy-x/p/19265940
版权声明：本作品采用「署名-非商业性使用-相同方式共享 4.0 国际」许可协议（CC-BY-NC-SA 4.0 协议）进行许可。
合集: 学习笔记 , Tricks
好文要顶 关注我 收藏该文 微信分享
Wy_x
粉丝 - 25 关注 - 54
+加关注
60
« 上一篇： 决策单调性 dp 的分治解法（整体二分解法）
» 下一篇： NOIP 2025 游记（？
posted @ 2025-11-25 10:15 Wy_x 阅读(177) 评论(1) 收藏 举报
刷新页面返回顶部
登录后才能查看或发表评论，立即 登录 或者 逛逛 博客园首页
【推荐】注册成为HarmonyOS开发者，支持博客园HarmonyOS社区建设
【推荐】英博云GPU容器服务平台，智能算力即开即用，立即免费试用
【推荐】科研领域的连接者艾思科蓝，一站式科研学术服务数字化平台
【推荐】诚邀您体验阿里巴巴推出的新一代 Agentic 编程平台 Qoder
编辑推荐：
OpenCVSharp：了解几种特征检测
Keepalived详解：原理、编译安装与高可用集群配置
生产事故-那些年遇到过的OOM
Avalonia 实现跨平台的视频会议（Windows、Linux、信创）
Elasticsearch 避坑指南：我在项目中总结的 14 条实用经验
鸿蒙专区：
CodeGenie 基于图片生成鸿蒙应用UI代码
生态市场全新升级，助力鸿蒙应用高效开发
鸿蒙新闻行业解决方案助力行业应用体验变革
揭秘长相思App如何在鸿蒙打造沉浸式阅读体验
独立开发者，冲在「改变世界」第一线
公告
本博客内的所有文章均遵守 CC-BY-NC-SA 协议，转载请在文首添加原文链接。
昵称： Wy_x
园龄： 10个月
粉丝： 25
关注： 54
+加关注
< 2025年12月 >
日 一 二 三 四 五 六
30 1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31 1 2 3
4 5 6 7 8 9 10
搜索
最新随笔
1.NOIP 2025 游记
2.NOIP 2025 游记（？
3.丐版 OI 技巧 / 杂项部分总结 + 作者学习笔记
4.决策单调性 dp 的分治解法（整体二分解法）
5.格路计数的一类（降维？）技巧
6.整体二分学习笔记
7.手写 bitset
8.关于一种滚动数组的错误实现方式
9.辗转相减法求高斯消元
10.自动化测大样例
积分与排名
积分 - 9995
排名 - 124995
合集
游记合集(7)
学习笔记(17)
CSP-S 模拟赛(17)
Tricks(6)
题解(34)
源码(10)
鲜花(1)
级逊(5)
Useful(3)
阅读排行榜
1. 丐版 OI 技巧 / 杂项部分总结 + 作者学习笔记(177)
2. 整体二分学习笔记(165)
3. CSP-S 2025 游记(150)
4. CSP-S 2025 游记 (？(145)
5. 【模板】动态 dp 学习笔记（树剖版）(145)
评论排行榜
1. 吩咐(15)
2. 德州东站换乘攻略（仅供参考）(15)
3. CSP-S 2025 游记(12)
4. fc | diff(10)
5. 整体二分学习笔记(9)
推荐排行榜
1. 丐版 OI 技巧 / 杂项部分总结 + 作者学习笔记(6)
2. 【模板】动态 dp 学习笔记（树剖版）(5)
3. 整体二分学习笔记(4)
4. 格路计数的一类（降维？）技巧(3)
5. 关于一种滚动数组的错误实现方式(3)
最新评论
1. Re:NOIP 2025 游记（？
NOIP 2025
!
--养鸡大户肝硬化
2. Re:NOIP 2025 游记（？
十万火急，快打开！！！
--HS_fu3
3. Re:NOIP 2025 游记（？
不要打开！！！会做噩梦
--Gon-Tata
4. Re:【模板】动态 dp 学习笔记（树剖版）
@leizepromax awawwwwa...
--Wy_x
5. Re:整体二分学习笔记
@华容道专家 腌不知道阿，腌没试过...
--Wy_x
6. Re:【模板】动态 dp 学习笔记（树剖版）
切树游戏！！！为何不学全局平衡二叉树！！！
--leizepromax
7. Re:丐版 OI 技巧 / 杂项部分总结 + 作者学习笔记
%%%
--BIxuan—玉寻
8. Re:整体二分学习笔记
好像是二分法高手。请问下面的情况有无可能二分： 用简拼查词典，如yy对应的有800个，yingyv youya yunyv... 把yy看作y★y★，*=或者说匹配any (ing, v, a)......
--华容道专家
9. Re:整体二分学习笔记
大手子呀，%%%整体二分大赦
--HS_fu3
10. Re:整体二分学习笔记
www小孩生气了www
--HS_fu3
11. Re:整体二分学习笔记
@晏清玖安 wyx 最严厉的父亲（...
--S_Keep_Kiding
12. Re:整体二分学习笔记
@HS_fu3 可能不是天敌，是【】（...
--晏清玖安
13. Re:整体二分学习笔记
@Wy_x
不是啥意思，我当面跟你说让你折叠代码块你都不弄，你说要突出重点，skk一说你就改，skk是你天敌啊
--HS_fu3
14. Re:整体二分学习笔记
byd 不加可折叠代码块是吧？
还是感觉 P3332 的树套树更自然。
--S_Keep_Kiding
15. Re:整体二分学习笔记
%%%orz 太聚啦
--Nailong2357
博客园 © 2004-2025
)
)