Posts by hostmaster

概述 矩阵乘法一般可以用来优化 DP。 公式 $n \times m$ 的矩阵 $a$ 与 $p \times q$ 的矩阵 $b$ 相乘，要求 $m = p$。乘出来得到的结果是一个 $n \times q$ 的矩阵 $c$。 $$c_{i, j} = \sum\limits_{i = 0}^m a_{i, k} b_{k, j}$$…

题意 求 $\left[l, r\right]$ 中满足一下条件的数的个数 出现至少 $3$ 个连续的相同的数字 不能同时出现 $4$ 和 $8$ $10^{10} \leq l \leq r < 10^{11}$。 题解 数位 DP。 $f\left(idx, l1, l2, a4, a8, ctn, less\right)$ 表示 从…

题意 给定一个长度为 $n$ 的环，环上第 $i$ 个点有权值 $U_i$。选择其中 $k$ 个点，对于一段连续的选择的点，除第一个点外其余计入答案。求最大的答案。 $1 \leq b < n \leq 3830$ 题解 我们在 $\left(n, 1\right)$ 间断开环，变成一条链，然后 DP，$f\left(i, j, 0/1\right)$…

题意 有 $n$ 个敌人，第 $i$ 个敌人跟你的距离是 $d_i$，必须在 $\left[a_i, b_i\right]$ 时刻消灭。 你可以在某个时刻消耗 $r$ 的代价，消灭距离 $r$ 以内的所有敌人。求摧毁所有敌人的最小代价。 $1 \leq n \leq 300$ 题解 尝试使用线性 DP 后发现不行，所以考虑区间 DP。 $f\left(l, r\right)$…

题意 给定 $n$ 个点 $\left(x_i, y_i\right)$，求曼哈顿距离下前 $k$ 小的点对。输出他们的距离。 $2 \leq n \leq 2.5 \times 10^5$，时限 $9$ 秒。 题解 做法 1 暴力的做法是维护一个堆，枚举点 $u$，再枚举 $v$，然后计算 $u$ 到 $v$ 的距离，插入到堆中，并且始…

题意 给你一个长度为 $n$ 的链，链上的每条边有边权。 有 $m$ 次操作，对于每次操作： C l r v，表示将 $l$ 到 $r$ 之间的所有边的边权都加上 $v$。 Q l r 表示在 $l$ 到 $r$ 上随机选两个不同的点，从 $a$ 到 $b$ 的路径上边权和期望是多少。 $1 \leq n, m \leq 10^5, -10^4 \leq v \leq 10^4$…

题意 题解 考虑 DP，设 $f(i)$ 为装满容量为 $i$ 的背包的方案数，这个很容易求。 设 $g(i, j)$ 为不用第 $i$ 个物品，装满容量为 $j$ 的背包的方案数。 当 $j < w[i]$ 时，$g(i, j) = f(j)$； 当 $j \geq w[i]$ 时，我们用 总方案数 减 选的方案数来计算：$g(i, j) = f(j) - g(i, j - w[i])$…

题目 Cow Dance Show Hoof, Paper, Scissors Secret Cow Code 题解 T1 我们可以把问题看成： 有 $n$ 个人，$k$ 个水龙头，第 $i$ 个人需要打 $d_i$ 时间的水，求最少时间。 这个的思路很简单，每次我们让一个人去使用时间最少的水龙头，开个堆就行了。如图 蓝色的点表示水龙头，…

题意 给定一个长度为 $n$ 的序列 $a$，请对 $k$ 从 $1$ 到 $\lceil \dfrac n2 \rceil$，回答出使 $k$ 个数严格大于他两边的数，至少需要进行多少次让其中一个数加一或减一的操作数量。 $n = 5000$ 题解 非常明显是 DP。 状态设计 $f(i, j, 0)$ 表示 前 $i$ 个数，有 $j$…

题意 给出一个网络图，以及其源点和汇点，求出其网络最大流。 题解 最大流问题就是，给你一张网络图，如果点 $u$ 到点 $v$ 有一条边，边权为 $w$，那么点 $u$ 到点 $v$ 最多 流 $w$ 的流量。求 汇点 最多能流到多少流量（源点流量无限）。 一个容易被想到的 错解 每次枚举一条从 源点 到 汇点 的路径，然后流 这条路径上…