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

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 14:11:14

本题是要求序列中的 $\max \sum\limits_{i=0}^{\lvert x\rvert -1 } A_{x_i} \le T$。

注意到 $N \le 40$，无法直接进行子集枚举。但是如果我们将其分为两半，那么 $N' \le 20$，这时进行子集枚举可行。

于是我们就在 $A =T_1, \cdots, T_{\lfloor N/2\rfloor}$ 与 $B =T_{\lceil N/2\rceil}, \cdots, T_N$ 上进行子集枚举，求出每种状态的和。

最后，我们将两个子问题的解组合在一起：在其中一个子集上进行遍历：对 $A_i$，我们需要找到一个 $B_j$ 使得 $A_i + B_j$ 最大且小于等于 $T$。

这就是 upper_bound 的上一个元素。用指针就是 upper_bound (...)[-1]。取最大值即可。

源代码

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-17 15:43:16

重心的定义与性质

一棵树的重心是这样的点：将它删除后，它的所有子树的节点数量的最大值，在所有节点中最小。

重心最重要的性质是：一棵树上所有点到重心的距离和是最短的。

重心的求法

我们可以用一个简单的 DFS 算法来求重心。

对每一个节点，我们在 DFS 中统计它的子树节点数量，并且取得其最大值 $t$。我们知道，将这个节点删除后，整个图中除了它的子树，还有它的父亲所在的子树。它父亲所在的子树的节点数量，很明显是树的总节点数量减去这个节点的子树节点数量，也就是 $n - t$。

设 $p = \max (n - t, t)$，则我们只需要找到使 $p$ 最小的节点即可。

int
centroid (int p, int father)
{
  int weight = 0;
  sizep[p] = 1;

  for (auto t : e[p])
      if (t != father) weight = max (weight, sizep[p] += centroid (t, p););

  weight = max (weight, n - sizep[p]);
  if (weight < mw) mw = weight, center = p;
  return sizep[p];
}

则 center 就是重心。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-19 21:48:04

题目要求的是一个区间内的平均数和方差。很明显是线段树的题目。

容易得到：

$$ \begin{aligned} s^2 & = \frac 1 n \sum\limits_{i=1}^n (x_i - \bar x)^2 \ & = (x_1 - \bar x)^2 + (x_2 - \bar x)^2 + \cdots + (x_n - \bar x)^2 \ & = x_1^2 + x_2^2 + \cdots x_n^2 + n\bar x^2 - 2\bar x(x_1 + x_2 + \cdots + x_n) \ & = \sum\limits_{i=1}^n x_i^2 -2\bar x \sum\limits_{i=1}^n x_i + n\bar x^2 \ & = \frac 1 n\sum\limits_{i=1}^n x_i^2 -\frac 1 {n^2} (\sum\limits_{i=1}^n x_i)^2 \end{aligned} $$

于是对一个区间，我们只需要维护它的总和以及平方和即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-20 19:32:04

本题很明显是动态规划。

可以用完全背包的思路来做：每一件纪念品一天能买无数次，将背包容量设为当前拥有的金币数量，将体积设为今天的价值，将价值设为明天的价值。

这样使用完全背包即可。

为什么？因为题目中有比较重要的一条：当日买进的纪念品也可立马卖出。因此，我们可以将价值设为今天与明天的价格差。

于是转移方程就是：

$$f(i, j) = \max {f(i - 1, j - P_{i,j}) + P_{i+1,j} - P_{i, j}, f(i - 1, j)}$$

本题告诉了我们背包模型的常见：对于很多作出选择的动态规划，我们都可以将其归为 01 背包、完全背包或者多重背包的一种。重点在于怎么设出正确的状态，也即 容量、体积 与 价格。这三者缺一不可。

明显，体积和价格是每一个物品所具有的属性。体积是作出选择所要付出的代价，而价格是所能获得的利益。而容量是转移方程中所变化的量，容量的变化能够影响当前的决定。

根据这些量来将题目抽象化，就可能将难以解决的问题归为背包问题。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-21 15:10:00

本题的特点是每个点上要加的值是不一样的，但是差值之间是一样的。

这让我们想到差分。

事实上，我们可以对这个序列进行差分。这样，点 $p$ 的值就是 $\sum\limits_{i=1}^p d_i$。这恰好就是线段树所可实现的区间更改和区间查询。

更新区间 $[l, r]$ 时，我们需要将 $l$ 点加上 $k$，将 $[l+1, r]$ 上每个点加上公差 $d$，最终在 $r + 1$ 点处减去 $a_{r - l + 1}$，即 $k + d\times (r - l)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-21 20:56:05

这两道题都是状态压缩的题目。

P1879 [USACO06NOV] Corn Fields G

我们知道，对于一个状态 j，为了使它每一个 $1$ 之间不相邻，我们有 j & (1 << j) 为零。而要使它与前一行的状态 $k$ 不冲突，我们需要有 j & k 为零。

这就告诉我们怎么进行状态之间的转移。我们设 $f(i, j)$ 表示第 $i$ 行，状态为 $j$ 的时候的方案数。我们知道，$f(i, j)$ 可以由 $f(i - 1, k) \text{ s.t. } k \text{&} j = 0$ 转移而来，其中 $k$ 表示的是前一行的状态。

最终，我们有

$$ f(i,j) = \begin{cases} 0 & i = 0, j = 0\ \sum\limits_{k & j = 0} f(i-1,k) & \text{otherwise} \end{cases} $$

最终我们要统计的就是第 $m$ 行所有状态的方案数量和。

P1171 售货员的难题

旅行商问题嘛。依然是设状态 $f(i, j)$， 表示由状态 $j$ 走到第 $i$ 个点的最短距离，其中 $i \notin j$。

我们如果知道了 $f(i, j)$，就可以推出 $f(i, j\cup \{k\}) = f(i,j) + P_{j, k}$。归纳边界 $f(0, 1) = 0$。

我们要求的就是在最终的满状态里选一点，从这一点走到 $0$，找最小值。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-23 09:51:40

这道题的转移方程还不算难列：

$$ f(i, j) = \begin{cases} \frac 1 2 f(i, i) & j = 1 \ \frac 1 2 f(i - 1, j - 1) + \frac 1 2 f(i, j - 1) & \text{otherwise} \end{cases} $$

但是问题是，这个转移方程是带环的：

$$ \begin{aligned} f(2, 1) = \frac 1 2 f(2, 2) \ f(2, 2) = \frac 1 2 f(2, 1) + \frac 1 2 f(1, 1) \end{aligned} $$

但是我们发现，这个方程组是有通解的：

$$ \begin{aligned} f(n, 1) = \dfrac {\sum\limits_{i=1}^{n - 1} 2^{i-1} \times f(n - 1, i)}{2^n - 1} \ f(n, i) = \frac 1 2 f(n - 1, i - 1) + \frac 1 2 f(n, i - 1) \end{aligned} $$

于是，$f(n, 1)$ 的计算是 $O(n)$ 的，而 $f(n,i), \text{s.t.} \space i \neq 1$ 的计算是 $O(1)$ 的。

然后推出即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-12 22:54:59

题意

给定整数列 $A(A_1, A_2, \cdots, A_N)$ 与 $P(P_2, P_3, \cdots, P_N)$ ($1 \leq P_i \leq i$).

有以下操作：

• 对 $i = 2, \cdots,N$，将 $A_{P_i}$ 加上 $A_i$

重复以上操作 $10^{100}$ 次，问 $A_i$ 正负性。

分析

根据样例 1 有推导：

第一次操作后： $$ \begin{aligned} A_1 = A_i + A_2 \ A_2 = A_2 + A_3 \ A_3 = A_3 + A_4 \ A_4 = A_4 \end{aligned} $$

第二次操作后： $$\begin{aligned} A_1 = A_1 + A_2 = A_1 + 2A_2 + A_3 \ A_2 = A_2 + 2A_3 + A_4 \ A_3 = A_3 + 2A_4 \ A_4 = A_4 \end{aligned}$$

第三次操作后： $$\begin{aligned} A_1 = A_1 + 3A_2 + 3A_3 + A_4 \ A_2 = A_2 + 3A_3 + 3A_4 \ A_3 = A_3 + 3A_4 \end{aligned}$$

第 $10^{100}$ 次（在本问题下可以看作趋向正无穷）操作后： $$\begin{aligned} \lim_{n\rightarrow \infty} A_1 = n\times A_2 \ \lim_{n\rightarrow \infty} A_2 = n \times A_3 \ \lim_{n\rightarrow \infty} A_3 = n\times A_4 \end{aligned} $$ 显然，$A_3$ 的正负性由 $A_4$ 决定。同理 $A_2$ 的正负性由 $A_3$ 决定，$A_1$ 的正负性便是由 $A_2$ 决定。

于是确定 $A_1$ 的正负性就变成了从 $A_n$ 开始向上的一条推导的长链。

但是我们需要考虑 $P$ 值重复，例如 $A_2 = A_2 + A_3 + A_4$ 的情况。实际上这并不是问题，因为很明显可以将 $A_3 + A_4$ 视作整体处理。

因此我们的策略便是，构建出一颗以 $1$ 为根的树，从下到上推导每一层的正负性，低一层的正负性决定更高一层的。