在文章《别笑，你来你也过不了第二关。》发表评论：

谢谢你，T2 出题人，愿你的母亲和在省选 D2T2 放非多项式复杂度题目的人的母亲相遇

在讨论《NOIPlus 2025》回复：

CCF 觉得你没资格打 NOI 然后就送了一场 NOIPlus 给你打，并且确保了你一定没资格打 NOI。

在讨论《【个人血泪史】NOIP考前注意事项》回复：

严肃学习

简单题。 按照结果的 $A$ 从大到小顺序考虑。对于 $A$ 的最大值，青木若想结果比它小，那么至少在到达写有该 $A$ 的节点的父亲时，需要选择把它变成 $0$。继续递推着，在处理完前面的限制后，发现当前 $A$ 带来的限制可以表示为，在目前写有该 $A$ 的节点的未被选用的祖先中，需选择一个，在到达它时，青木选择这…

因为限制长成了环形的鬼样子，导致一个一个数地填维护限制非常困难，必须将填的过程对每个数同时进行。但是注意到 $a_i + (a_{i-1} \& a_{i+1})$ 的样子很二进制，可以发现该式上 $a$ 最低位只有限地影响得数最低几位。因此有逐位确定的想法，可以在当前最低位上，对每个数的该位进行填，以凑出 $M$ 的…

首先可以想到一个静态的做法。按照原式计算是困难的，不妨变换顺序，计算每个点对答案的贡献，需要处理出 $L[i], R[i]$ 表示 $i$ 点最大值能延申到的区间。推一下式子，贡献可表示为 $3$ 段加等差数列的形式，可用线段树简单维护（注意标记的首项下传细节！）。 观察修改的样子，发现修改前后只是在某些区间的答案上简…

在文章《NM-S00251 代码迷惑行为大赏》发表评论：

做干净的奥赛

画几个图分析一下，若我们钦定某一个点，那么重叠于这个点的路径对端点就分居于两个子树内。对树上每一个点都做一遍，若取到重叠部分的端点，就相当于以该点为根，对于左子树上不配对的点，他们的对应在右子树上点，选两个，lca的深度的最大值。因为最大值一定被遍历序相邻的两个节点取得，是容易维护的。所以可以在以 1 为根的树上维护子…

要求的是是否存在一个包含点 $v$ 的环，使得环的长度模 $t$ 与 $-s$ 同余。 那么有关的部分就是包含点 $v$ 的强连通分量。由于对于分量上的任意点，存在一个包含其与 $v$ 的环，那么只需要跑 $t$ 遍该环，就可以在某一时刻“出现”在这个点上。又由于复杂环可以由简单环构成，那么问题转化为在强连通分量上选若…

需要观察。 可以注意到做一次操作，相当于将一个数加入，然后将一个最小的数移除。这便于统计操作后的和。进一步观察到修改操作的相似性：他们都从 $1$ 开始进行；甚至可以发现任意调换修改顺序，最后的数列不变。 那么对于一个数列大小为 $siz$，从开头起进行若干次操作后，最后剩的就是数列中的数和操作的数的前 $siz$ 大…

在讨论《欢迎 XCPC 选手加 LA/LB 群》回复：

疑似歧视无气球者

注意到若把整张 DAG 分成三类点，一类是符合题目条件的点，一类是从 1 号点可以到达的点，一类是从 1 号点不可到达的点。那么合法点连边方法有 ① -> ②，③ -> ①，③ -> ②。他们之间相互独立，也就是不同类之间的连边合法性只与类的种类有关，故可以将他们分开考虑，再进行合并，以降低问题复杂度。 考虑全为 ①…

可以感受到满外向树是比较简单的，所以先思考满外向森林的情况。（后文深度表示离出度为 0 的点的距离） 假如只有一些深度为 1 的点，显然就是取石子游戏。 假如上面接上一些深度为 2 的点，通过手玩几个样例，可以发现当深度为 2 的点异或和 和 深度为 1 的点异或和 全都为 0 时，先手必输，否则先手必胜。 最大深度为…

观察到：当所有堆中石子个数相同时，若有偶数堆，则： 1. 先手执行第一步，此时设取走第一堆 $x_1$ 个。 2. 后手取走第二堆 $x_1$ 个。 3. 先手第三步，当合法时，取走第一或三堆 $x_2$ 个。 4. 后手取走第（先手取的堆的编号 $+1$）个堆的 $x_2$ 个。 5. 重复以上操作，最后先手失败。…

```cpp 10 16 24 28 14 21 24 1 0 12 8 12 6 16 13 6 12 0 6 14 20 976 10 4 6 20 14 9 2 12 23 23 16 6 18 4 0 5 20 26 0 6 18 841 ```

容斥在dp中的应用 经典题。 啊这题首先是要dp ~~（因为其他想法都是难维护的难以达到正解）~~ 设计状态，按照一般的树形 dp 去想，如何描述清楚一个子树的形态？我们需要知道在树上的根节点 i，在图上对应的点 j，和在图上对应的点集 S。然后发现每个节点的转移肯定是绕不开枚举子集的。 于是想改状态，对枚举子集的祸首…

好题啊。基本把期望线性性玩明白了。 利用期望线性性，首先可以拆贡献。要计算“某个点在点分治过程中被遍历的期望次数”。所有点分别计算后求和就是答案。 然后可以手玩这个分治过程，假设要计算的点为 $i$，从 $i$ 的视角观察，把它定为“根”。然后就会发现，按照分治过程，等概率在 $i$ 所在的联通块内选一个点，然后把它删…

在讨论《RemoteJudge 服务中断情况公告》回复：

不是，没有人在意现在的 SPOJ & UVA 吗？

在讨论《SPOJ 一直 UKE》回复：

不是，SPOJ从昨天就开始炸

在讨论《RemoteJudge 服务中断情况公告》回复：

SPOJ RMJ是什么情况？

在讨论《本题可能存在简单的单log解法》回复：

ans = 100

在讨论《本题可能存在简单的单log解法》回复：

Hack: ```cpp 7 4 4 4 100 -200 150 -50 1 2 1 1 3 2 3 4 3 1 5 2 5 6 3 2 7 4 ```

知道 Hall 定理应该好想。首先要想到对于任意一个 T1 的边集 $E$，删去它的边后会得到 $|E|+1$ 个联通块，若把他们放到 T2 上的话，由于 T2 是棵树，所以各点集间仍是联通的，所以至少各点集之间至少有 $|E|$ 个边。由霍尔定理，知一定存在 $n-1$ 条边的完美匹配。 另附霍尔定理的证明：[证明]…

### 3012 考虑最终无法继续消除的情况，存在于 $ 2 \times 2 $ 的黑色方块内的黑块一定无法消除。并且“伸出的斜线”也无法消除。如： $ BBWWWWW $ $ BBBWWWW $ $ WWBBWWW $ $ WWWBBWW $ $ WWWWBBW $ $ WWWWWBB $ $ WWWWWBB $…

首先判断方案合法需要满足什么条件。按照deadline排序的方法是错误的，用完全包含的情况hack。由此想到用最后完成的时间offline排序，顺序完成任务，若全部满足条件则合法。可以证明。 所以先以offline为关键字排序，就可以按顺序考虑判断是否合法。 证明对于当前的一些任务，若添加一个任务，按照完成任务数为第一…

首先不同 SCC 无关联是好证的，因为无后效性，可以不计后果地随便赋值。 对于单个 SCC 考虑选任意一个点u为 “基准” ，那么从该点出发到v，长度为len的路径相当于u和v的差值最多为len。他们之间的点也一定在这个[dis[u],dis[v]]区间内，所以答案的上界就是区间的大小。由于边权只有-1、0、1，所以区…

根号分治大成题。蒟蒻不看题解想了一天。 题目意思就是在序列中删掉一区间，分别取剩下的段和删掉的段中的众数的个数，问他们的和最大能为多少，还有能取到最大和的剩下那段众数的方案。 直接做是不行的，用根号分治的方法创造条件。 #### 1. 处理小于 $$ \sqrt{n} $$ 个数字。 这种情况容易想到对每个数字分开处理…

什么是 Hall 定理，蒟蒻不知道。 考虑二分答案，问题转化为是否能在 $mid$ 距离内为每个少男找到匹配的少女。 首先证明对于一个两个**位置序列**，最优匹配方案一定是分别从小到大排序后依次匹配。分类讨论即可。 然后证明对于**环上**问题，最优匹配方案一定不同时存在有少男从左端到右端和从右端到左端的情况。并且一…

在讨论《FAOI-R5 作弊名单》回复：

tm有狗 @Union_Find jc我

在讨论《FAOI-R5 作弊名单》回复：

竟然没有我！！！