题解 CF1314D Tourism Dilute 2020-02-24 题解 开场 10 分钟就有人过的 1D ,你值得拥有! $\texttt{swap(B, D)}$ 警告。 阅读全文 DP 随机化
题解 CF1286C Madhouse Dilute 2020-01-12 题解 这个 $0.777$ 让我想起了某位 EDG 的退役打野选手 —— Sooke 4396(无 端 迫 害) 阅读全文 非传统题
题解 CF498D Traffic Jams in the Land Dilute 2019-09-01 线段树首先观察数据范围,发现$a_i \le6$,这个是一个非常有用的性质。 发现$\mathrm{lcm}(1, 2, 3, 4, 5, 6)=60$,这个数有一个非常优美的性质:把$t$再$\mod 60$意义下进行不会影响结果的正确性。 阅读全文 数据结构 线段树
题解 CF1178G The Awesomest Vertex Dilute 2019-07-21 题解 分块 + 斜率优化G真的比F2清真 首先,看到树上 + 子树操作,第一反应使用dfs序拍平。 那么这个问题就变成了支持: 区间$a_i += x$ 询问区间$\max{|a_i| * |b_i|}$ 阅读全文 斜率优化 分块 DFS序.
题解 CF1183H Subsequences (hard version) Dilute 2019-06-27 题解 瞎搞DPCF出了H没出G 菜的真实 发现$k$从$\texttt{E}$题的$100$变成了$O(10^{12})$,考虑与$k$复杂度无关的做法。 我们考虑$f_{i, j}$表示以$s_i$开始,本质不同的长度为$j$的子序列数量。 阅读全文 DP
题解 CF1051E Vasya and Big Integers Dilute 2019-05-28 哈希 + 二分 + DP首先看到题面,很容易想到一个$DP$,令$f[i]$为划分到$i$为止的方案数。 然后朴素的暴力转移是$O(n^2)$的,非常显然一个状态$i$能够转移到的$j$是一段连续的,进而想到使用前缀和优化。 阅读全文 DP 哈希 二分
题解 CF15D Map Dilute 2019-05-08 题解 $set$ 瞎搞首先非常显然,一个矩形$(x1, y1, x2, y2)$的代价就是$\displaystyle\sum_{i = x1}^{x2}\sum_{j = y1}^{y2} h[i][j] - \min_{x1 \le i \le x2, y1 \le j \le y2} h[i][j]$,我们用$f[i][j]$表示以$(i, j)$为左上角的矩形的代价。即矩形$(i, j, i + a - 1, j + b - 1)$的代价。 我们首先考虑如何求出$f[i][j]$。 阅读全文 数据结构
题解 CF609F Frogs and mosquitoes Dilute 2019-04-22 题解 set瞎搞预处理我们考虑一下,一只青蛙能够影响的区间是什么 我们发现,如果将每只青蛙能够吃到的文字区间$[l, r]$按照左端点$l$排序,然后把后面的区间和前面的区间的重复部分去掉,那么就可以得到一个青蛙真正可以吃到的蚊子的范围区间 阅读全文 数据结构