题目描述 给定一个 $2\times n$ 的网格图，每个格子都有一个权值，你需要将这些格子划分为尽可能多的连通块，使得每一个连通块的格子权值的平均值均相等。这里的联通指的是四联通。 分析 首先先将所有格子减去平均值，这样转化为将格子划分为尽可能多的连通块，使得每一块所有格子的和为 $0$。 一个直观的想法是在状态中记录上一列两个格子所在连通块的大小进行 DP，但这是不可接受和不必要的。 如果上一

题目描述 给定序列 $a_1,\dots,a_n$ 和常数 $c$，$m$ 次询问，每次询问给出 $l,r$，询问所有满足 $l\le l^\prime \le r^\prime\le r$ 且 $r^\prime-l^\prime+1\le c$ 的 $[l^\prime,r^\prime]$ 区间和的最大值。 思路 按照 $c$ 分块，则合法的答案必然完全在一个块内或者是一个块的后缀和下一块的

注意事项： 需使用 c++11 及以上版本编译。 确保引用 cstdio 和 cctype 这两个头文件。 请不要与其他任何输入输出方式混用。 在终端中使用时输入结束需手动输入 EOF（Windows Ctrl+Z Linux Ctrl+D）。 非封装版 123456789101112131415161718192021222324252627namespace IO{ con

小清新题。 题目描述 给定序列 $a_1,\dots,a_n$ ，$m$ 次询问，每次询问给出 $l,r$ ，问有多少组 $(i,j,k)$ 满足 $l\le i<j<k\le r,\;a_i=a_k>a_j$ 。 思路 记 $w_x$ 为 $\sum_{i=1}^{x}[a_i<a_x]$，即 $1\sim x$ 中小于 $a_x$ 的数的个数。从左往右依次将数加入值域树

题意简述 给定一棵 $n$ 个点的树，点有蓝色和白色两种颜色，每次选择一个蓝点 $u$ 并将所有距离为 $1$ 的点染成蓝色，代价为该点的点权 $w_u$，求将树全变为蓝色的最小代价。$n\le 2\times 10^5$。 思路 树 DP。 每个点要么被父亲染成蓝色，要么被儿子染成蓝色。设 $f_{u,0/1/2/3}$ 为对于 $u$ 子树内所有节点都被染成蓝色，$u$ 被选择，父亲需要被选择

还是不够熟练。 题意简述 一个 $n\times n$ 的网格图，每个格子上有颜色，求满足起点和终点颜色均相同且只向下和向右走的路径条数。可以走 $0$ 步。$n\le 400$。 解法 设起点为 $(x,y)$ 终点为 $(z,w)$，则从 $(x,y)$ 到 $(z,w)$ 仅向下和向右走的路径条数为 $\dbinom{x-z+y-w}{x-z}$，可以理解为从起点到终点总共要走 $(x-z

真的难写。 $\checkmark$ A 给定序列 $a$，求该序列差最小的数对。 差最小的数对一定在排序后的相邻两项中产生。 1234567891011121314151617constexpr int N=2e5+5;int a[N];inline void work(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.ti

总体而言，这套比 ARC 058 要简单。 $\checkmark$ A 将 $x$ 变为 $y$ 的代价为 $(x-y)^2$，给一数组 $a$，每个元素只能变一次，求将该数组所有元素变相同的最小代价。 最后数组中的数的大小一定在原来最小值和最大值之间。枚举这个数计算代价并比较。 1234567891011121314151617constexpr int N=105;int a[N];inli

$\checkmark$ A 给定 $x$ 以及几个 $0\sim 9$ 的数字，求最小的 $k$ 满足 $k\ge x$ 且 $k$ 的十进制表示中不含给定的数字。保证不能出现的数字不是 $0\sim 9$ 或 $1\sim 9$。 直接从 $x$ 开始枚举，检验是否满足要求，记 $t=\lfloor \log_{10} x\rfloor$，则必然 $k<10^{t+1}$。时间复杂度可以

简介 正常的 DP 是要满足若干条件，对某个东西求最值或者计数。但是某些情况下，求的东西可能刚好是相反的。即给定值反推有多少种条件能使得最后 DP 出的答案为给定的值。 将原来的 DP 作为内层，将内层 DP 每个状态的取值作为外层 DP 的状态，在下标上进行内层 DP 来转移外层 DP。 很多情况下要观察性质或搜索，将内层 DP 不可能取到的 DP 状态剪掉，或者合并内层 DP 的状态，以达到优