3月日记
26-3-1
开学第一天
不说做题，只是这个竞赛生活动还是有点抽象了。
@Antimony_ 退役了，祝好。
@Takato_ 退役了，祝好。
26-3-2
P10947，P10948 前者是最短路计数，后者是图论建模，但是有比我的更优的做法（利用一个层只会到一次的特点用优先队列优化 bfs （dijkstra） 跑最短路）。
26-3-3
P3225，基环树板子题，分讨然后跑个 LCA 再分讨。
P10951，二分 + spfa 找正环，但是数据卡了朴素 spfa 是令人忍俊不禁的。
P4819，前半部分 tarjan 缩 SCC 还算容易，但是有关概率的部分很迷惑，正解结论感觉很合理，但又不知道自己的思路错在哪里概率白学了。
26-3-4
P10950，欧拉路径应用计算机译码板子。
P3304，随机化乱搞过的。
P3225，显然可以想到点双，但是对于点双中的的情况分析稍有难度。
如下：
- 点双内无割点，则此时需要在该点双内放两个出口
- 点双内有一个割点，则此时需要在该点双内的非割点中放一个出口
- 点双内有不小于两个割点，则此时不需要在该点双内放出口
- 如果是点双内只有一个点，且该点不是割点，则也需要放一个出口
但是不知道为什么 UVA 和 SPOJ 上过不了。
26-3-5
P10953，边双缩点，然后 LCA 求树上两点距离。
P4281，抬手分讨。
- 若一点在另外两点的路径上，直接选这个点，这是最优解之一。
- 若有一点，以另两点的 LCA 为根，该点不与另外两点在同一个子树内，则选这个 LCA 是最优解之一。
大概可以证明
UVA1464，圆方树板子。
还因此被迫学习了重链剖分 :（ 写小常数 LCA。
26-3-6
P10949，对于一个子图，若该子图中的点的权值和为 0，则该子图可以单独成一棵树。
对于每一个子图跑最小生成树，记子图
然后跑 DP，设
26-3-9
P15649，联合省选 2026 D1T1，先拆贡献成
树上卷积是经典看似
其他三道绿题，不提了。
26-3-10
P10589，略。
P1502，略。
P10463，运用更相减损法将区间加减变成单点加减，然后就能做了，但是线段树节点合并因为需要求 gcd 所以是
P3345，这我得坐起来写，题解点这里。
26-3-11
P10590，分块优化
P1494，莫队板题。
P4178，点分治板题，点分治学习笔记点这里。
26-3-12
P4735，可持久化数据结构的一大用处就是通过记录历史版本的信息，帮助我们过滤错解（本题中用于使答案符合有关
P1525，略。
P10686，判定方式比较有趣，是假设一个人是裁判，此时有关这个人的所有条件是无用的，除去这些无用条件后再扫一遍判断，若合法就证明这个人可以是裁判，第二问的答案是判定其他不是裁判的人时找到矛盾的最大轮数，因为至少要经过这些轮次后才能知道其他人不是裁判。
P10687，yes 表示同一部落，no 反之，这是好想的，但是后面然后要跑一遍背包，因为对于每一个连通块，其具体情况是未知的，所以要跑背包以考虑所有情况，如果有且仅有一种方案符合条件，那这就是解。
DP 状态
输出具体方案，就是记录状态如何转移，但这里有个 Trick。
在把 DP 第一维去掉之后，发现有方案的
反正就是直接压成一维不用滚动而且连记录方案的数组也是如此就对了。
26-3-13
P2894，区间最大子段和加区间赋值加线段树二分。
P10688，略。
P4135，类似于蒲公英的思路，实现稍繁琐。
26-3-14
模拟赛 - 凌云计划 7。
预估得分 300 pts，实际得分 300 pts，没有挂分。
26-3-16
P4169，cdq 分治，比较板。
P4149，点分治，比较板。
26-3-17
补了 CF2204D,E,F。
完成了 P10689，平衡树屎题，差评。
26-3-18
P4390，cdq 分治，比较板。
今天效率较低，下午学整体二分学了比较多的时间，学完后写的题目也没调出来。
26-3-19
P3527，整体二分，特别之处是转区间为差分再转为单点修改操作，本题注意空间限制。
P10690，正解分块套可持久化 01 Trie，预处理
但是有歪解，注意到设
P2824，二分答案加权值线段树。
注意到
所以原排列分为小于
然后发现排序就是将序列区间修改，一半
然后在 25-8-18 的模拟赛（还是 hyc 模拟赛）的 T3 sort 中，后半部分这个 Trick 就基本出现了。
甚至 sort 题面也有一模一样的排序操作。
我甚至在模拟赛中场切了 sort。
我好菜，水平严格低于以前 /ll。
26-3-20
P3402 【模板】可持久化并查集，就是用可持久化线段树维护并查集，由于不能路径压缩（Hack：构造两个大小之和
然后基本就是一个任意操作复杂度带只
然后开始蓝书数学专题，今天通过 6 道。
cdo 进度尚未追上，同志仍需努力！
26-3-21
模拟赛 - 凌云计划 8。
预估得分 308 pts，实际得分 295 pts，挂分在 T1 特判写错和 T2 Tarjan 打错。
注意到自己对于 T3T4 有一定的心理恐惧，很容易导致最后做的时候没尽全力思考，同时做完 T1T2 后有点疲惫，导致思维比较迟钝,经常导致在能力范围内的 T3T4 却没能做出来。
首先是要克服心理问题，但怎么克服只能让时间给出答案，然后对于疲惫，可以在做完前两题后上个厕所休息五分钟。
26-3-23
补完了模拟赛 - 凌云计划 8。
做了 P4777 和 P1939。
26-3-24
P10498（矩阵乘法），P10499（高斯消元），P3265（高斯消元），P1313（二项式定理）。
其中 P3265 涉及线性基，有点难理解，粗略地从异或空间线性基理解了一下。
感冒了难受死我了。
26-3-25
P4778（注意对排列连边分析性质的 Trick），P2480（Lucas 定理和 CRT），P3455（莫比乌斯函数），P10500（实际不是期望题，二进制分位计算），P10502（矩阵乘法，Hint：矩乘有分配律）。
26-3-26
CF451E。
首先考虑如果每个盒子内没有数量限制的方案数，插板法可得
这显然多算了，考虑如何减去多的部分，发现当有至少 1 个盒子选择的数量超过了其容量，这个方案就是不合法的。
考虑如何计算至少 1 个盒子选择的数量超过了其容量的方案数。
若钦定盒子
同理若钦定盒子
枚举超限盒子再容斥一下就可以算出来至少 1 个盒子选择的数量超过了其容量的方案数，容斥系数是
然后用
UVA12369。
设
如果已经不可能达到目的，期望就是
直接记搜做即可。
P2568。
显然有
结论：
假设
则有：
$$
\begin{aligned}
\sum_{i=1}^{x+1} \sum_{j=1}^{x+1} [\gcd(i,j)=1]
&= \sum_{i=1}^{x} \sum_{j=1}^{x} [\gcd(i,j)=1] + \sum_{j=1}^{x+1}[\gcd(x+1,j)=1]+\sum_{i=1}^{x+1}[\gcd(i,x+1)=1] - [gcd(x+1,x+1)=1]\
&= \sum_{i=1}^{x} \sum_{j=1}^{x} [\gcd(i,j)=1]+2 \times \varphi(x+1)\
&= \sum_{i=2}^{x+1} 2 \times \varphi(i)
\end{aligned}
$$
所以，该结论对
P2303。
转化答案为
P1516。
事实上就是求解满足
P2485。
三个板子，分别是快速幂，求逆元，BSGS。
P10503，略。
26-3-27
P4151，题解。
P4301，考虑朴素 Nim 游戏，发现这道题本质问的就是插入的所有数和最大的线性基的插入数的和是多少，然后从大到小将每个数尝试插入一遍线性基即可求出。
P4071，错排问题的变题。
错拍问题的递推式的推导（设
考虑在
- 元素
放到 号位，也就是交换 号位和 号位，剩 个元素要排，方案数 ； - 元素
不放到 号位，也就是假装 号位是 号位，剩 个元素要排，方案数 。
所以递推式就是：
26-3-28
SPOJ-WIDGET，唐氏模意义下高斯消元。
模拟赛 - 攀登计划 1。
得分/估分：280/280。
PS：但是 T2 做法是假的呜呜呜……
26-3-30
改完了模拟赛 - 攀登计划 1。
26-3-31
今天没有做什么题，都在改昨晚晚练题（P4364）。
题解 To do。
- 标题: 3月日记
- 作者: DimStar
- 创建于 : 2026-03-04 10:04:10
- 更新于 : 2026-04-01 20:23:16
- 链接: https://dimstar-zhang.github.io/2026/03/04/3月日记/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。