ryp 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-04 18:22:38
典型的树形背包，比如 P2014 选课，其复杂度是 $O(nm^2)$ 的。但实际上，我们可以达到 $O(nm)$ 的优秀复杂度。
常规的做法是：对每一个节点，我们计算它子树在 $0$ 到 $m$ 上的最优值，然后枚举每一个子节点被分配给的空间大小，并求得最值。
我们考虑优化：不将节点看作是树形的，而是将它摊平。对某一个点 $p$ 的子节点 $q$，它的初始值是 $p$ 在当前的值。也就是说，将这个树摊平之后，$p$ 成为第 $i$ 个节点，而它的孩子 $q$ 是第 $i + d$ 个，我们有 $f(i+d)_0 = f(i)$。
在转移时，我们不需要考虑“给某个子节点分配多大的空间”，因为它们此时都是并列的。在总空间为 $t$ 时，给这个孩子的便是 $t - 1$。
于是最后的复杂度就是 $O(nm)$ 的。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-06 10:55:51
我觉得是一道比较好的思维题。
当只有 $m$ 个荷叶的时候，明显我们最多有 $m + 1$ 个青蛙。从 $A$ 出发依次跳到 $m$ 个荷叶上，最后一只青蛙直接跳到 $D$，然后再顺次跳到 $D$ 上即可。
我们看石墩。石墩增加一个，可以过的青蛙翻倍。很简单，我们设原来有 $m$ 个荷叶，那么最多能过 $m + 1$ 个青蛙。增加石墩后，我们让前 $m$ 个青蛙跳到荷叶上，第 $m + 1$ 个跳到石墩上，然后让这 $m$ 个再跳到那个石墩上，现在这个石墩上就有了 $m + 1$ 只青蛙。之后我们按照原来的方法转移即可。
于是最终的答案就是：$(m + 1) \times 2^n$。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-07 08:52:18
赛时 24 分切了 ABC，看了 D 感觉很恶心就没做，就做开了 E。最开始还以为是个简单的 DP，结果越做越不对劲，有几个坑点：
所以一直卡到 9:39 分还在调一个基于集合的屎山 DFS + DP。后来看了一篇题解豁然开朗。
我们可以将权值相同的节点视作一个节点，然后建小权值指大权值的有向图，之后用拓扑求最长路即可。
但是它扛不住这个 hack
4 4
1 2 1 4
1 2 2 3 2 4 3 4
我们的代码输出 0，因为这时点 2 的入度是 2（1 和 3），而 3 是永远访问不到的，故我们就访问不到 4。我们需要改一下，只建能从 1 能访问到的边，即跑一边 DFS 记录，然后重新建边即可。
本文章由 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 增加最优解
证明有错误或叙述不当的请指出。感谢。
鲁ICP备2025150228号