这是一篇 DDP 做法的题解。 首先需要想通的一个点就是最值一定出现在端点处，否则区间长度变化而极差不变，会导致答案更劣。 设最值所在的位置为 $l,r$，则会有两种情况： 若最大值在最小值左侧，则答案为 $a_l - a_r - (r - l) ...

Floyd 求最短路，时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。 123for (int k = 1;k <= n;++k) for (int i = 1;i <= n;++i) for (int ...

可以尝试通过构造解决此题。 考虑到一个数能被 $9$ 整除是各个数位上和为 $9$ 的倍数，一个数整除 $8$ 只需要末三位均为 $0$ 即可。因此大致的方向就是去构造 $x,8 - x,0,0,\cdots,0,0,0$ 的一个数来满足条件。【为什...

是稍微迟了一点的有关我编程故事的年度小结。昨天看到洛谷出了年终总结，想了想还是决定分享一些。 其实高中参加信息竞赛以来，很少有和别人分享给具体的经历，更多是悄悄地写在博客里。 我嘛编程的天赋并不多，能坚持这么久更多的是一份热爱。高中三年来，其实周围能...

对于每一行的 $-1$，显然只会填一种数字，因此可以得出一种比较朴素的 DP。设 $f_{i,j}$ 表示考虑前 $i$ 行，第 $i$ 行的 $-1$ 变为 $j$ 时的最大值，再设 $d_{i,j}$ 表示第 $i$ 行数字 $j$ 的个数，则可...

Weighted Tic-Tac-Toe 用二进制表示每一格的情况，然后必胜态和必败态需要相互转换。 Remove Pairs 直接状压，时间复杂度 $O(2^nn^2)$。 Exchange Game $dp_{f,st}$ 表示某一方...

定义：一棵有根树形成的任一排列 $p$，若 $i$ 是 $j$ 的父亲，排列 $p$ 均满足 $i$ 在 $j$ 之前。更加形式化的，$\forall 1 \le i < j \le n$，$p_j$ 均不是 $p_i$ 的父亲。 结论：设...

母题—逆序对与期望 求长度为 $n$ 的排列的期望的逆序对个数。 对于每一对数，是否成为逆序对的概率显然为 $\frac{1}{2}$，那么就有： E(x) = E(\sum\limits_{i,j\mid i < j}[a_i > a_j])...

$\gcd (x,y)$ 求两个数 $x,y(x > y)$ 的最大公因数，辗转相除法即可。 1int gcd (int x,int y){return !y ? x : gcd (y,x % y);} $\rm l...

将行和列分开考虑。 在每组询问 $(x_1,y_1,x_2,y_2)$ 中： 对于每一行，相邻的两个数的下标差为 $1$。 对于每一列，相邻的两个数的下标差为 $y_2 - y_1 + 1$。 不难想到对行和列分别做 $i \times a_...