做题笔记

P_Bisector · 2025-03-15 19:32:10 · 个人记录

ARC150C：Dijkstra。

P1600 [NOIP 2016 提高组] 天天爱跑步：考虑一定的和或一定的差 \rightarrow 树上差分 \rightarrow 考虑子树内情况 \rightarrow 离线，使用树剖和树状数组维护。

P4513 小白逛公园：线段树板子，手动设计区间合并。

P4514 上帝造题的第七分钟：二维树状数组板子题，推式子题。

P4768 归程：最短路 \rightarrow Kruscal 重构树 \rightarrow 树上倍增。

P5072 [Ynoi Easy Round 2015] 盼君勿忘：计算通式 \rightarrow 莫队 \rightarrow 暴力维护 \rightarrow 分段维护。

P5073：维护所有半素数。

P5749 排列鞋子：贪心确定鞋子配对 \rightarrow 贪心确定鞋子位置 \rightarrow 求逆序对。

P10144 水镜：O(1) 分治合并方案 \rightarrow 线段树二分。

笔记：两个状态之间的合并可以使用矩阵。

P11713 玛里苟斯：线性基删无效信息 \rightarrow 拆贡献 \rightarrow 考虑任意 k 个位是否相关 \rightarrow 线性基。

P11831 追忆（recall）：分块确定可行集合 \rightarrow 分块确定最大值区间 \rightarrow 暴力枚举最大值。

笔记：对于在奇怪的集合中求最值的问题，存在一种特殊的时间复杂度为 O(\frac{n}{\omega}+\sqrt{n}) 的解法，即暴力计算出该集合并算出值的其中 \sqrt n 个后缀所对应的集合，每次拿出集合的一个长为 \omega 的块与后缀比较，如果存在交集则再比较更短的后缀。

P11832 图排列（graperm）：建圆方树 \rightarrow 双极定向转仙人掌 \rightarrow 树上DP。

P12520 超速检测II：差分约束 \rightarrow 考虑关键边 \rightarrow 转一二维偏序问题。

P12827 「DLESS-2」XOR and Even：考虑限制偶数 \rightarrow 在首位添加一位 \rightarrow DP。

不知道哪个题：维护诡异函数可以使用网络流，一条边拆成若干条边。

CF1442D：缺一分治。

不知道哪个题：如果要求答案在 [ans,2ans] 范围内，对所有数字取对数。

Luminescence：\text{mex}(A)=\min(U\setminus A)。

中子衰变、生日礼物：奇偶性分析。

P8493：方案数转期望。