对于已有的集合考虑下一个选什么数是非常困难的，我们考虑反过来做，考虑对于当前的数最多能选多少个数出来。 因此可以直接设状态 $f_x$ 为集合最大值为 $x$ 时最多能选多少个数，为了有拓扑序，需要排序去重后再逐一转移。 对于每个 $x$，我们需要枚举其因数，从其因数 $d$ 转移而来，选一个最大的转移，即 $\beg…

这不直接 ODT 吗？但是我不会。所以我写了线段树。 考虑一个数 $a_k$ 减 $d$ 后会产生什么影响：令 $b_i$ 为 $[1,i]$ 的前缀最小值，减去后，$[k+1,n]$ 中大于 $b_k$ 的前缀最小值 $b_j$ 一定会变成 $b_k$，又由于前缀最小值具有单调性，这一部分可以直接二分。 考虑怎么维护…

我们手玩发现，对于一开始给定的 $s$，最后一个 $0$ 的地方，一定填 $1$。 我们尝试将这个结论推广：既然是小于 $a_i$ 的 $a_j(j #define int long long #define ls (p > 1; Build(l, mid, ls), Build(mid + 1, r, rs); pu…

统计数对，可以考虑枚举右端点统计最短点，或分治统计，这里选择了枚举右端点。 令当前右端点为 $i$，考虑从 $i$ 到 $i+1$ 有什么变化。手玩样例，我们发现每个位置 $0$ 和 $1$ 贡献的变更是与其左边最近的最大或最小值影响的，分别令它们为 $mx_i$ 和 $mn_i$。 具体地，由于给定的是排列，因此 $…

非常厉害的原理题。 容易发现程序模拟的就是树状数组的 `update`。考虑树状数组中 `update` 的本质：一直在 $c$ 中往后跳，对所有维护该点的段加一个权值。 回到原题，告诉我们了 $c$ 中一些点是否有值，不妨记 $f_i$ 为树状数组上第 $i$ 个段需要被修改的次数，我们可以分类讨论： - $c_i=…

感觉，被，诈骗了。 ---- ## T1 看到第一眼，合并芒果？不对，这是 $a \times b$，而且题目中还有取模，哪里有求最小值，还要取模的？最小值不会变么？ 这启示我们，也许，怎么合并都是一样的。 ---- 手模/打一个暴力，你会发现确实是这样，那么第一问就好解决了，第二问怎么做？ 很简单，每一次合并芒果时都…

在文章《题解：P9984 [USACO23DEC] A Graph Problem P》发表评论：

这 TLE 为什么是奶龙？？？

很多时候 DP 转移困难不是你不会优化，很有可能是你状态没设好。比如 T2 和 T3。 [L1nk](https://www.luogu.com.cn/contest/268963#problems) ### T1 可以先给八十分写一个 DP 暴力出来：$f_{i,j}$ 表示位置 $i$ 选 $j$ 的方案数，然后发…

### [CF947A](https://www.luogu.com.cn/problem/CF923A) 显然我们有 $x_i-p_i+1 \le x_{i-1} \le x_i$，由题面，我们需要 $x_1$ 尽可能小，$p_1$ 尽可能大，因此 $p_1$ 即为 $x_1$ 最大质因数，然后根据上式推出 $x_0…

### [CF1336A](https://www.luogu.com.cn/problem/CF1336A) 我们发现想要距离远，放叶子节点是最优的，既然每个点防止之后，它的每一个叶子节点的贡献都要减 $1$，那么其负贡献就是 $siz_u - 1$，而他本身又会提供正贡献，即 $dep_u-1$，那么两个相减就是…

### [CF1679D](https://www.luogu.com.cn/problem/CF1679D) 我们发现，如果较大的权值合法，那么更大的权值也一定合法，因此可以对最小值进行二分。 考虑 check。如果一点可以经过一个环来到达，那么这个点必定能取到；如果一个点可以通过一条长度超过 $k$ 的链到达，那么…

利用斜率单调性，缩小决策集合，提高转移效率。不同决策点的比较可以转化为斜率的不等式。因此称为斜率优化 DP。 状态转移方程具有如下特征：$f_i = \max\{f_i,f_j+a_i\times b_j+c\}$ ### [HDU3507](https://vjudge.net/problem/HDU-3507) 1…

🕊

### [CF1436C](https://www.luogu.com.cn/problem/CF1436C) 我们注意到样例中的序列不用有序就能二分到指定的数，这说明每一次二分到的 $a_{mid}$ 都满足有序序列的单调性。 那么，如果二分到的 $mid$ 比 $x$ 小，那么有 $x - 1$ 种可能，否则有 $…

由此可见设计一个好的状态是至关重要的。 ### [CF1324E](https://www.luogu.com.cn/problem/CF1324E) 令状态 $f_{i,j}$ 为已经睡完前 $i-1$ 时间点（$a_i$），时间 $j$ 入睡，“好的”的最长时间段。 首先在在时间点零还没入睡的最长时间段一定为 $0…

其实是 IOI 赛制。 ### T1 把原题的式子玩一遍之后发现答案只会是 $1$ 或 $2$，其中当 $x=y$ 时答案为 $1$，因为 $x + y \ge x | y$。 那么可以使用一个容斥，在二进制意义上，具体为当一对数之间如果有一位重合时答案加 $1$，有两位重合时答案减 $1$ 以此类推，计算有多少个与…

- [ ] 图转树：MST，边双连通分量，圆方树，Kruskal 重构树...... P1967 Kruskal 重构树的实现: 1. 将无向图的边按边权排序； 2. 枚举排序后的边 $e$，若 $e$ 的两个端点 $u$ 和 $v$ 不连通，那么新建一个点 $p$，点 $p$ 连接 $u$ 和 $v$ 所在并查集的根…

### [CF1514D](https://www.luogu.com.cn/problem/CF1514D) 我们发现对于一个集合中的众数，设它出现的次数为 $cnt+1$，需要 $cnt$ 个非众数让这个众数所在的集合合法。这个结论易证。 我们还发现，处理这 $cnt+1$ 个众数时，一起用非众数消除影响一定不比分…

### 简介 可以追溯到任何一次修改前的状态。 ### 可持久化线段树 第一种：维护区间的可持久化线段树。 第二种：维护值域范围的可持久化线段树（主席树）。 ### 动态开点线段树 一种线段树实现的方法，其线段树的原理和普通线段树没有任何区别 每次 Build 或 Update 递归时，若 $p$ 为 $0$，则新建一…

WA 了 19 个点 思路就是预处理，将方块分层，第 $i$ 层由每一列的从下往上第 $i$ 个方块组成，每一层被消除的时间就是这一层最高方块的 $y$ 坐标。处理完答案之后 $O(1)$ 回答询问即可。 ```cpp #include using namespace std; using PII = pair ; c…

### [A](https://www.luogu.com.cn/problem/CF2028A) 可以重复小 A 走的路线，直到经过小 Q 即可。 ### [B](https://www.luogu.com.cn/problem/CF2028B) 我们只会对大于等于 $n - 1$ 的 $a_i$ 进行操作，考虑从最…

在讨论《Yet Another 正确性求助》回复：

Yet Another 玄两关

在讨论《Yet Another 正确性求助》回复：


[前传](https://www.luogu.com.cn/discuss/971283) 求助一下两份代码的复杂度正确性: swap 思路: 将相等的全部 swap 走. 这一份时间复杂度很小概率假: 峰值时间 166ms ```cpp #include using namespace std; const int…

在讨论《正确性求助》回复：

@[_lbh_](/user/820057) 感谢,已关.

在讨论《正确性求助》回复：

悬赏两关

在讨论《正确性求助》回复：

@[_lbh_](/user/820057) 没有 hack 掉

在讨论《正确性求助》回复：

@[_lbh_](/user/820057) a,b必须有序

在讨论《正确性求助》回复：


在讨论《正确性求助》回复：

WA 了 3 个点