ryp 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-08 20:53:03
本题是双指针问题。
我们可以将原序列以 $k+1$ 个点为界，分为 $A_i,\cdots,A_t$。很明显，无论如何我们都不可能让两个 $A$ 连成更大的连续 X 序列。然后我们的问题就转化为在这 $t$ 个序列中替换 $k$ 个点，找最终最大的结果。
我们维护快指针 p 与慢指针 q，p 始终指向当前序列的开头，而 q 进行遍历。我们在总替换的点数量不超过 $k$ 的情况下，将看到的所有点全部替换为 X，直到末尾或者替换次数不够。此时答案就是 q - p。处理完之后，我们将 p 向右移动，找下一个点。
有一点细节：当原来的快指针指点时，我们需要将限制值减去一。同时，慢指针开始的时候指的是快指针前面一个单位。
双指针是考察细节与编码能力的算法。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-08 21:52:03
最开始分析一通当成变形的拓扑排序，但是越来越发现不对劲，后来看了一眼根本没法拓扑（$O(nm)$）。
看了题解想到可以从后往前建点，对每一条边，我们判断它对连通块数量的影响。
多么好的思路……可惜不是我的。
由此我们知道不管哪场 ABC，只要是 E 题，一定有出其不意的优秀解法（
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-10 20:20:15
首先将删边改为加边，问题就转化为：向最初的无边图中依次加入 $M$ 到 $1$ 条边，求加入后的最短路。
我们设 $f(i)$ 代表从点 $1$ 走到点 $i$ 的最短路径，有边界：$f(1) = 0$。在加入每一条边 $(u,v)$ 的过程中，影响的只有 $v$：$f(v) = \min\{f(v), f(u) + w\}$。
更新完点 $v$ 之后，我们更新可能被点 $v$ 影响到的每一个点，即做一次 BFS。
作为出题人，有以下注意点：
以下是标程：
#include <iostream>
#include <vector>
#include <climits>
#include <cstring>
#define rep(v, s, e) for (auto v = (s); v < (e); v++)
#define rrep(v, e, s) for (auto v = (e); v >= (s); v--)
using namespace std;
const long long N = 2 * 1000, M = 100000, K = 10, wtsummax = 1e10;
long long f[N], q[M], pt[K], wi[M], qs[M * K];
vector<pair<int, long long>> e[N];
int ui[M], vi[M];
int
read (void)
{
int res = 0, sign = 1;
char c;
while (!isdigit (c = getchar ()))
if (c == '-') sign = -1;
do res = res * 10 + c - '0'; while (isdigit (c = getchar ()));
return res * sign;
}
void
spread (int s)
{
int head = 0, tail = 1;
q[0] = s;
while (head <= tail)
{
int p = q[head++];
for (auto t : e[p])
{
int v = t.first, w = t.second;
if (f[v] > f[p] + w)
f[v] = f[p] + w, q[tail++] = v;
}
}
}
int
main (void)
{
int m, k, tail = 0;
read (), m = read (), k = read ();
rep (i, 0, k) pt[i] = read () - 1;
rep (i, 0, m) ui[i] = read () - 1, vi[i] = read () - 1, wi[i] = read ();
memset (f, 0x3f, sizeof f);
f[0] = 0;
rrep (i, m - 1, 0)
{
int u = ui[i], v = vi[i]; long long w = wi[i];
e[u].push_back (make_pair (v, w));
if (f[v] > f[u] + w)
{
f[v] = f[u] + w;
spread (v);
}
rrep (j, k - 1, 0) qs[tail++] = f[pt[j]] > wtsummax ? INT_MAX : f[pt[j]];
}
tail--;
while (tail >= 0)
{
rep (i, 0, k) printf ("%lld ", qs[tail--]);
putchar ('\n');
}
return 0;
}
关于复杂度：
这算法看起来是 $O(nm)$ 的，但卡不到，因为只有当前边更优的时候我们才会更新其他点，而且更新的点只是整个图很小的一部分。随机数据只到了大约二十到三十万的水平。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-11 11:10:53
根号分治是一种暴力的算法：将问题以 $\sqrt{n}$ 为界，使用两种不同的算法，达到较好的复杂度。
对于本题，我们如果纯使用暴力来做，那么代码类似于：
查询：
int x, y, res = 0;
...
for (int i = y; i <= n; i += y) res += a[i];
修改：
seq[x] = y;
查询是 $O(n)$ 的，而修改 $O(1)$。整体复杂度就是 $O(nm)$，显然不行。
我们容易发现：当 $y$ 很小的时候，查询的操作数多；当 $y$ 很大的时候，操作数反而少了。因此我们可以想到这样的策略：当 $y$ 小的时候我们预处理出值，当 $y$ 大的时候，我们暴力。修改的时候，我们更新预处理出的值。
分界线是什么呢？明显是使得两边复杂度都最小的值，就是 $\sqrt{n}$。此时，小规模查询的复杂度是 $O(1)$，大规模查询的复杂度是 $O(\sqrt n)$，修改的复杂度是 $O(\sqrt {n})$，整体复杂度是 $O(m\sqrt n)$，大约是 $10^8$ 级别，可以通过。
这就是根号分治，是一种“分而治之”的思想。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-14 12:54:22
一眼树形 DP，但是不太好处理，因为根是不确定的。
我们可以先假设点 $1$ 是根（因为题目保证联通），然后预处理出一些参数：$\sigma$ 和 $s$。$\sigma(u)$ 表示点 $u$ 的子树中的点权乘上边权和，$s(u)$ 表示点 $u$ 为根的子树节点数量。
然后我们知道：$\sigma(1)$ 就是以点 $1$ 为根时题目要求的权值和。但是，我们现在要求的是以其他点为根时的权值和。
这实际上是可以根据计算出来的参数得到的。
我们设 $f(v)$ 表示点 $v$ 为根时，题目要求的权值的和。设点 $u$ 是点 $v$ 在以点 $1$ 为根时的父节点，$w$ 是树边 $(u,v)$ 的权值，那么我们可以得到这样的转移方程：
$$ f(v) = f(u) - ws(v) + w\times(T - s(v)) $$
之后我们取得 $f$ 在 $[1, n]$ 上的最小值即可。
这叫做换根 DP，基本策略是：
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-14 18:27:18
LCS 是动态规划的经典问题。
我们用 dp[i][j] 表示序列 $A_1 \cdots A_i$ 与 $B_1 \cdots B_j$ 的 LCS 长度。dp[i][j] 之间有什么关系？也即，状态之间应当怎样转移？
我们可以分情况讨论。
当 $A_i = B_j$ 时，这个新的 LCS 长度就是上一个 LCS 的长度加上一。这是明显的。
否则，新的 LCS 长度是前两个 LCS 长度中的最大值。
所以，当 a[i] == b[j] 时 dp[i][j] = dp[i - 1][j - 1] + 1，否则，dp[i][j] = max (dp[i - 1][j], dp[i][j - 1])
为了求 LCS 序列，我们需要维护一个 dir 指示动态规划中的顺序，然后逆推即可。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-14 20:47:48
谨此纪念我的第一道蓝题题解（虽然是看了其他题解后写的）
给定一个序列 $W_0 \cdots W_{n - 1}$，以及一个整数 $D$，要求把 $W$ 的所有元素分配到 $D$ 个盒子中，求分配的方差和最小值。
很明显是动态规划题。我们可以设 $f(i,j)$，表示将状态 $j$ 所表示的元素分配到 $i$ 个盒子中的最小方差（$\sum_k^i (x_k-\bar x)^2$）。
分析边界：
$f(0,j)$，也就是将所有元素放到同一个盒子中，就是： $$f(i, j)=\sum\limits_k^0 (x_k-\bar x)^2=(x_k-\bar x)^2 \quad i = 0$$
对于一般情况，要将 $j$ 所表示的元素放进 $i$ 个盒子中，我们要考虑 $j$ 的每个子状态 $k$：找将 $s$ 与 $k$ 差的元素放进 $i - 1$ 个盒子中所得到的最小方差和再加上 $k$ 状态的方差，以上的最小值，也就是
$$f(i, j) = \min\limits_{k\in j}{f(i-1,j\oplus k)+(x_k-\bar x)^2}$$
因此
$$f(i,j) = \begin{cases} (x_j - \bar x)^2 & i = 0 \ \min\limits_{k\in j} f(i-1,j\oplus k)+(x_k - \bar x)^2 & \text{otherwise} \end{cases}$$
证明是彻底理解转移方程原理的很好方式。
首先易证本问题有最优子结构：
问题就是求 $\frac{1}{D}\min\sum\limits_{i=0}^D(x_i-\bar x)^2$。设 $T$ 是问题的最优解，要证 $\sum\limits_{i=1}^D(T_i-\bar x)^2$ 也最小。
反证。设 $U_1,\cdots,U_{D-1}$ 是一个更优的方案，即
$$ \sum\limits_{i=1}^D(T_i-\bar x)^2 > \sum\limits_{i=1}^D(U_i -\bar x)^2 $$
那么可以有
$$ T' = \frac{1}{D}((T_1-\bar x)^2+\sum\limits_{i=1}^D(U_i-\bar x)^2) $$
则必有 $T' < T$，与 $T$ 是本问题的最优解冲突。故不存在比 $T_1, \cdots T_{D-1}$ 更优的方案 $U$，得证。
以上是证明最优子结构的常用方法，即《算法导论》中所讲的 copy-paste 法。
代码预计算出了 $\bar x$ 与 每一种状态 $k$ 对应的 $x_k$，然后就是状压 DP。
#include <iostream>
using namespace std;
#define rep(v, s, e) for (auto v = (s); v < (e); v++)
#define square(x) ((x) * (x))
const int N = 15, M = 1 << 15;
long long *w;
long long s[M];
double f[N][M];
long long
read (void)
{
long long res = 0;
char c;
while (!isdigit (c = getchar ()));
do res = res * 10 + c - '0'; while (isdigit (c = getchar ()));
return res;
}
int
main (void)
{
int n, d; n = read (); d = read ();
double xbar = 0;
w = new long long [n];
rep (i, 0, n) xbar += w[i] = read ();
xbar \/= d;
rep (i, 0, 1 << n) rep (j, 0, n + 1)
s[i] += w[j] * !!(i & (1 << j));
rep (i, 0, 1 << n) f[0][i] = square (s[i] - xbar);
rep (i, 1, d) rep (j, 0, 1 << n)
{
f[i][j] = f[i - 1][j] + square (xbar);
for (int k = j; k; k = (k - 1) & j)
f[i][j] = min (f[i][j], f[i - 1][j ^ k] + square (s[k] - xbar));
}
printf ("%.10lf\n", f[d - 1][(1 << n) - 1] \/ d);
return 0;
}
以上代码 不是最优解 （235ms）。
最优解使用的是另一种动态规划的实现方法，即自上到下的动态规划。在某些情况下这可以省去很多的计算。采用这种方法可以得到 13ms 的最优解。
upd. 2023/12/15 增加最优解
证明有错误或叙述不当的请指出。感谢。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-15 22:56:39
我承认我的动态规划真的非常烂，所以我决心要恶补一下。
Ad maiora!
贪心。下面证明。
问题是求在 $T$ 秒内能走的最长距离。有几种选择：
我们要证明的是本问题的最优子结构。如果我们已经有了走到 $t - 1$ 时间的最优解 $P_{1, t - 1}$，要证走到 $T$ 时间的最优解一定包含 $P_{1, t - 1}$ 。
用标准的 cut-and-paste。设 $Q_{1, t}$ 才是到 $t$ 时间的最优解，那么一定有 $Q_{1, t - 1} \gt P_{1, t - 1}$。
如果 $Q_T$ 是操作 A，那么 $\lvert Q_{1,t}\ ert = \lvert P_{1,t-1}\rvert$。矛盾，得证。
如果 $Q_T$ 是操作 B，那么明显将 $P_{t-1}$ 嫁接到 $Q$ 上对其没有任何影响，况且可以得到 $\lvert Q_T\rvert \gt \lvert Q_{1, t} - Q_{1, t-1} + P_{1, t-1}\rvert$。矛盾，得证。
如果 $Q_T$ 是操作 C，那么我们知道 $M_Q(t-1) \ge 10$。我们要证 $M_P(t-1) \ge 10$。
（情况 1）： 如果正如此，那么没有什么好证明的。
（情况 2）： 如果并非如此，即 $M_P(t-1) < 10$，这就意味着 $P_{1,t-1}$ 一定比 $Q$ 多至少一次操作 C，$Q_{1,t-1}$ 一定比 $P$ 多至少一次操作 A，因此 $\lvert P_{1,t-1}\rvert - \lvert Q_{1,t}\rvert \ge 60$。于是，$\lvert Q_{1,t}\rvert + 60 \le \lvert P_{1,t-1}\rvert$，更有 $\lvert Q_{1,t}\rvert + 60 \lt \lvert P_{1,t-1}\rvert + 17$。这也就是说 $Q_{1,t}$ 甚至比不上 $P_{1,t-1}$。这显然是矛盾的，得证。
于是得证。
归纳边界：当 $t = 0$ 时明显最大距离为 0。
设 $t$ 对于本问题是前 $t$ 秒的最优解，那么对于前 $t + 1$ 秒，由于最优子结构性质，我们只需要考虑在操作 A、B 与 C 中进行选择，选择最大者即可。
最优子结构易证。
我们设 $f(i)$ 表示从 $1$ 到 $i$ 的最小租金。归纳边界是 $f(1) = 0$。
要走到第 $i$ 个回收站，我们可以从 $1, \cdots, i - 1$ 的回收站里选一个进行租用。那么方程就是
$$ f(i) = \begin{cases} 0 & i = 1 \ \min\limits_{1\le j\lt i} f(j) + r(j, i) & \text{otherwise} \end{cases} $$
计数 DP。要求的是方案数量。设 $f(i, j)$ 是在这个集合的前 $i$ 个元素中表示 $j$ 的方案数。
归纳边界明显：$f(i, 0) = 1$。
一般地，要表示 $j$，只有两种方法：$j$ (1) 和 $(j - p_i) + p_i$。那么，表示出 $j$ 的方案数，就是原来的方案数量加上 $f(i - 1, j - p_i)$
但是最终的答案要减去每一个 (1)。即，最终的答案要减去 $m$。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 12:46:56
对于原问题，这就是一个简单的计数 DP。设 $f(i)$ 是将这些物品放进体积为 $i$ 的背包内的方法数量，则转移方程是
$$ f(i) = \begin{cases} 0 & i = -1 \ 1 & i = 0 \ \sum\limits_{j = 0}^{n} f(i - \min (w_j, i + 1)) & \text{otherwise} \end{cases} $$
写成代码便是
rep (i, 0, n) rrep (j, v, w[i]) dp[j] += dp[j - w[i]];
对于本问题，我们要求的是删除某个物品 $i$ 后的最大容积。
明显我们有以下等式：
$$ f(n) = f(n - w_0) + f(n - w_1) + \cdots f (n - w_{i}) + \cdots + f(n - w_k) $$
删除物品 $i$ 后的 $f(n)$ 应当减去 $f(n - w_i)$。于是，我们可以计算出去除了 $i$ 后的 tp：
rep (i, 0, n) rep (j, 0, v + 1)
if (j < w[i]) tp[j] = dp[j];
else tp[j] = dp[j] - dp[j - w[i]];
这个复杂度是 $O(nV)$ 的，显然能够通过。
编码时注意取模即可。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 13:08:04
本题的特点是 $W$ 极大，而 $v_i$ 与 $N$ 却较小。求的是在总重量小于等于 $W$ 的前提下的最大价值。
我们可以进行一个简单的思维转换：将问题转换为价格最大时的最小重量。也即，将价格作为状态，求出价格为某时的最小体积。
之后我们自后往前遍历 dp 数组并找到第一个满足 dp[i] <= w 的 $i$。此时 $i$ 就是最大的价格。
归纳边界：dp[0] = 0
鲁ICP备2025150228号