本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-04 13:28:09

题意很明确，就是选择虚拟根的 $m$ 个子树使得总和最大。

这也是很经典的背包问题：在每一个子树上，我们做一次背包，得到这个子树在 $0$ 到 $m$ 的体积上的所有最值。然后处理根：很明显，这就是一个零一背包。

树形 DP 充分利用了树状结构的天生的最优子结构性质，是十分优雅的。

虚拟根的技巧也是很优雅的，可以将本来不联通的几棵树转化为一颗。

本文章由 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。

作为出题人，有以下注意点：

• 本题不卡常，正确的算法应当都能通过，$O(m^2)$ 以上的暴力最短路不能通过。但是，STL 与手写可以差两倍时间。
• 本题的数据：Subtask 0 是生成数据，Subtask 1 是手写数据，包括样例

以下是标程：

#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 是动态规划的经典问题。

求 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 序列

为了求 LCS 序列，我们需要维护一个 dir 指示动态规划中的顺序，然后逆推即可。