这个人不懒，但还是什么都没写
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
20251118【NOIP】模拟 C. 修建道路 简化题意： 一棵树，任意加边，使新图恰有 $k$ 个边双。对合法方案计数。 关键观察： 1. 将所有割边断开，会形成恰好 $k$ 个连通分量。 2. 所有的割边都是原来的树边。 考虑结论 2 的证明： - 考虑新加入的边，一定不会有新割边产生，因为两个端点一定在原树上是…
在讨论《关于 freopen 的一个问题》回复：
@[xzy_sf](luogu://user/780320) %%% 给斜队爷磕头了
agc036_d 基于[题解](https://www.luogu.com.cn/article/jdnup9d1) 关于为什么没有孤立点： 注意**原边**不能被删去，所以孤立点并不是真正的不可到达。 如果孤立点向前面的点有连边（正边），且正边构成负环，那么一定会将正边删去，而将这个孤立点加入前面的那个区间不会新增负…
20251113【NOIP】模拟 B. 序列 (seq) 首先，对原序列建出大根笛卡尔树，对于每一个节点，考虑左右儿子与这个点的贡献，维护左右儿子的 $\sum x_i,a_i,cnt$ ，即总共的 $x_i$ 的和，$a_i$ 的值，注意为了不使这个加法无效，必须一段一起加，贡献为 $2*k*\sum x + k^2…
Qoj1839 Joke 题目要求对 $s$ 计数，而 $s$ 只跟 $p,q$ 的相对大小有关，所以我们先将 $p$ 排序，同时保证 $q$ 与 $p$ 的大小关系不变。 所以可以画出图像 …
Special Cycle 先考虑什么关键边可以删，当两个关键边共一个点时，答案中的环要么两条边都经过，要么两条边都不经过，所以可以合并成一条关键边。当有大于等于三个关键边共一个点时，环一定不会经过这个点，所以直接将这些关键边和点都删去。然后这张图一定没有关键边相邻。 如果一条边是割边，那它一定不会在答案里，所以可以直…
Qoj2570. Maximal Subsequence ### 题目描述 给定一个包含 $n$ 个整数的数组 $a$。序列的美观度定义为该序列的最长递增子序列的长度。要求找出数组 $a$ 的一个子序列，使得该子序列的美观度小于整个数组 $a$ 的美观度，并且该子序列的长度尽可能大。 转化题意，找出子序列等价于在原…
# day -1 校内模拟赛怎么波动怎么大，状态很重要。 # day 0 很好的信心赛，使我的信心旋转。 # day 1 上午 在机房复习。 # 赛时 顺序开题，T1看一眼出思路，想到排序后贪心，但发现第三个样例的情况有误，因为没有深思就直接开码，导致浪费了不少时间。这时候就开始怀疑思路，想换成DP，但是不会。开新 c…
AT\_arc208\_b \[ARC208B] Sum of Mod 题解 ## 前言 讲一种不用二分 $a_1$ 的做法 ## 解法 为了方便描述，记题目中的式子的值为 $sum$。 首先，因为取模，差最大为 $a_{i-1}-1$，所以我们要让 $a_n$ 尽量小，就要最小化前面的值，所以每次 $a_i$ 取 $…
## AT\_abc426\_g \[ABC426G] Range Knapsack Query 题解 ## 解法 这道题求区间 01 背包的值，01 背包的值可以预处理，考虑分块。 设 $f_{i,j}$ 表示第 $i$ 个块到正在枚举的物品，容量不超过 $j$ 的 01 背包价值，$g_{i,j}$ 表示第 $i$…
## 前言 [双倍经验](https://www.luogu.com.cn/problem/P3590) 这篇题解主要是提供一种更简单的证明结论的方法。感谢 [q1uple](https://www.luogu.com.cn/user/539133) 大佬的讲解。 ## 解法 首先，我们根据直觉觉得在随机情况下，答案应…
## 前言 这篇题解主要是提供一种更简单的证明结论的方法。感谢 [q1uple](https://www.luogu.com.cn/user/539133) 大佬的讲解。 ## 解法 首先，我们根据直觉觉得在随机情况下，答案应该会很长，所以，我们可以通过打表~~或翻讨论区~~得到一个结论：**答案开头或结尾一定在 $[…
2025.8.21 ## 临项交换法 适用于将序列重排列使最优的题目。 当不知道最优序列满足什么性质时，可以使用这个方法。 例：[P1080 [NOIP 2012 提高组] 国王游戏](https://www.luogu.com.cn/problem/P1080) 2025.8.24 upd:[[AGC023F] 01…
7.28 最小斯坦纳树，整体二分，树剖等 ## 2025.07.29【提高A组】模拟赛 题面在u盘中 T1:1257. 海报 原题：[P9790 [ROIR 2020] 海报 (Day 2)](https://www.luogu.com.cn/problem/P9790) 算法：动态DP 首先，考虑没有修改应该怎么做。…
首先，我们称一个**合法的**行的选取方案当且仅当我们能选出一列，使这一列上的与行的交点的值异或起来是 $1$。这样其他列就可以任意选了。若选完异或和为 $0$，异或上这一列，否则不异或。在排除一列后，这个选法的贡献是 $2^{m-1}$ 的。 现在考虑怎样算出合法的行选取方案的个数。一个选法不合法当且仅当不存在有一列…
2025.7.17-2025.7.18做题记录 ## 高斯消元，矩阵 [P4159 [SCOI2009] 迷路](https://www.luogu.com.cn/problem/P4159) 只有边权 $0,1$ 时，答案就是邻接矩阵的 $t$ 次幂。 观察到边权很小，暴力拆点，建立分层图。$(i,j)$ 向 $(i…
## CF1747E 题解 题意比较明确，不再复述。 #### 分析 这道题给了两个数列，并且同一个数列之间有限制关系，不同数列之间也有限制关系，直接下手没有什么思路，考虑转化。 看到有两个数列，且互相限制很弱，考虑搬上网格图，将一对 $ (a_i,b_i) $ 看作坐标，所有路径从 $(0,0)$ 出发 $(n,m)…
1. https://www.luogu.com.cn/problem/P1082 https://www.luogu.com.cn/article/1wawrmip 2. https://www.luogu.com.cn/problem/P1495 https://www.luogu.com.cn/article/n…
1. [P1365](https://www.luogu.com.cn/problem/P1365) 设 $ dp[i] $ 表示第 $i$ 位的期望，$len$ 为最长的长度 当是 $s[i]$ 为 $o$ 时 $$ dp[i]=dp[i-1]+[(len+1)^2-len^2] $$ $$ = dp[i-1]+le…
[博客](https://www.cnblogs.com/alex-wei/p/network_flow_bipartite_graph_and_graph_matching.html) ## 最大流 反对称性：$ 𝑓(𝑥→𝑦)=−𝑓(𝑦→𝑥) $ 流量限制：$ 𝑓(𝑥→𝑦)≤𝑐(𝑥→𝑦) $…
## 归约 当A问题是B问题的子问题，就是B题的代码能原封不动地用来通过A问题时，我们将B问题认为是难于A问题的。 这时候，**当我们解决了B问题时，A问题也被解决了，这就叫做将A问题归约到B。** 同时，有一些问题能够经过转化变成另一些问题，我们就叫做**A问题等价于B问题** ## 复杂度下界 当我们对一个问题完成…
## 注意 在考试时注意时间，用基本技巧（倍增，dfs序，树上差分）解决的问题就不要使用高级数据结构（树链剖分，线段树合并和dsu on tree） **倍增维护信息时要注意lca周围** ## 幂等信息 一个信息是幂等的，就是说这个信息在合并后任是自己，比如最大值算多了答案、仍然正确 这样就可以把信息合并次数减少，比…
## 代数学 通过理论推导，得出一些抽象得代数性质，遇到具象的集合或其他得东西，就有这样得结论 ## 代数结构 OI中常用得有半群，群，环，域。 **半群**：满足结合律的一个集合。 可以用线段树和快速幂 **群**：满足结合律和运算可逆，并存在一个单位元，即 $ \forall a \in S \ \exists e…
# dp优化 几何体是凸的，当且仅当任意两点的连线的所有点都在几何体内。 函数 $f$ 是下凸的，就等价于 1. 导数单调不降（对于离散函数，就像数组,e.g. 即由点构成的点函数，导函数定义为…
[CF593D Happy Tree Party](https://www.luogu.com.cn/problem/CF593D) 有 $ \lfloor \frac {\lfloor \frac {a}{b} \rfloor }{c} \rfloor = \lfloor \frac {a} {bc} \rfloor…
# CF75D Big Maximum Sum ## 具体思路 首先，我们考虑大数组的答案构成是什么，经过思考，可以得出只有两种情况： 1. 是某个小数组的最大子段和。 2. 跨越了很多个小数组。 这样我们就可以设出 $O(n^2)$ 的 dp： 设 $ dp[i][j] $ 表示以大数组的第 $ i $ 位结尾，结尾…
[CF404D Minesweeper 1D](https://www.luogu.com.cn/problem/CF404D) 1. dp[i][0]表示i-1和i+1都不是雷的情况 =```s[i]==0``` 2. dp[i][1]表示i-1是雷，i+1不是雷的情况 =```s[i]==1``` 3. dp[i]…