菜鸡 fa_555 会把一些动态简要地记在这里。主要还是留给自己以后看的。

所有代码不保证包括无关紧要的部分

---

这个傻逼现在精神状态和身体状态都不好。脑子里啥东西都没有，连续爆零了好几场比赛。

咕咕咕。

---

[模板]单调队列优化多重背包

problem

一个背包，容积为 $C$。$n$ 种物品，第 $i$ 种的价值、体积、数量分别为 $v_i, c_i, s_i$。

选出若干个物品，使得它们的体积之和不超过背包容积，且最大化它们的价值之和。求出这个最大价值。

solution

首先可以把第 $i$ 种物品拆成 $s_i$，当成 01 背包来做。复杂度是 $O(nC^2)$ 的。

考虑优化。一种简单的优化是二进制拆分，即对于一个 $s_i$，一定能拆分成 $2^0, 2^1, 2^2, \cdots, 2^k, s_i - \sum_{j = 1}^k {2^j}$ 的 $O(\log s_i)$ 个数。可以证明 $\forall i \in [1, s_i]$ 都可以由这些数中的若干个相加得到。复杂度是 $O(nC \log C)$ 的。

二进制优化不是最优秀的。利用单调队列优化，可以将复杂度优化到 $O(nC)$。令 $f_{i, j}$ 为前 $i$ 种物品占用体积为 $j$ 时的最大价值，考虑状态转移方程：

$$f(i, j) = \max{ \{f(i - 1, j - kc_i) + kv_i\}} \ (0 \le k \le s_i)$$

换一下下标，假设已经求出 $f_{s - 1}$，现在要求 $f_s$。
$f_s(i) = f_{s - 1}(i - kv) + kw \ (0 \le k \le a)$
$f_{s - 1}(0), f_{s - 1}(v), f_{s - 1}(2v), \cdots$ 可以更新 $f_s(0), f_s(v), f_s(2v), \cdots$
$f_{s - 1}(1), f_{s - 1}(v + 1), f_{s - 1}(2v + 1), \cdots$ 可以更新 $f_s(1), f_s(v + 1), f_s(2v + 1), \cdots$
任意两组之间不会影响。我们把第一组重编号，得到如下的新转移：
$f_s(i) = f_{s - 1}(i - k) + kw \ (0 \le k \le a)$
现在决策区间变成连续的了，可以使用 单调队列求出答案。

code

/* struct Deque { ... } q, w; */

int f[40003];

int dp() {
  int N, C, ans = 0, tmp = 0;
  cin >> N >> C;
  for (int v, c, s; N; --N) {
    cin >> v >> c >> s;
    if (!c) { tmp += s * v; continue; }
    dmin(s, C / c);
    for (int j = 0, K; j < c; ++j) {
      K = (C - j) / c;
      q.clear(), w.clear();
      for (int k = 0, now; k <= K; ++k) {
        now = f[j + k * c] - k * v;
        while (q.size() && now >= q.back())
          q.pop_back(), w.pop_back();
        q.push_back(now), w.push_back(k);
        while (k - w.front() > s)
          q.pop_front(), w.pop_front();
        dmax(f[j + k * c], q.front() + k * v);
        dmax(ans, f[j + k * c]);
      }
    }
  }
  return ans + tmp;
}

---

AGC034E Complete Compress

problem

给定一颗 $n$ 个结点的树，某些结点上有棋子（恰好一颗）。

可以进行若干次操作，每次操作将两颗不相邻的棋子均向中间移动一步。

判断能否通过若干次操作使得所有的棋子都在一个点上。如果能，求最小操作次数。

solution

口古口古口古

code

using iarrN = int[2003];

char c[2003];
int tot, ans = inf;
iarrN mn, mx, siz, head;

void dfs(int u, int f) {
  mx[u] = mn[u] = 0, siz[u] = c[u] == '1';
  int son = 0;
  for (int i = head[u], v; i; i = e[i].nxt) {
    if ((v = e[i].to) == f) continue;
    dfs(v, u);
    siz[u] += siz[v], mx[u] += mx[v];
    if (mx[v] > mx[son]) son = v;
  }
  if (mn[son] > mx[u] - mx[son])
    mn[u] = mn[son] + mx[son] - mx[u] + siz[u];
  else mn[u] = siz[u] + (mx[u] & 1);
  mx[u] += siz[u];
}

int main() {
  int N;
  scanf("%d%s", &N, c + 1);
  for (int i = 1, u, v; i < N; ++i) {
    scanf("%d%d", &u, &v);
    addEdge(u, v), addEdge(v, u);
  }
  for (int i = 1; i <= N; ++i) {
    dfs(i, 0);
    if (mn[i] - siz[i] == 0)
      ans = std::min(ans, (mx[i] - siz[i]) >> 1);
  }
  printf("%d", ans == inf ? -1 : ans);
  return 0;
}

---

[POI2011]Lightning Conductor

problem

给定长度为 $n$ 的序列 $a$，对于每个 $i \in [1, n]$，求出一个最小的非负整数 $p$ 使得 $\forall j \in [1, n], a_j \le a_i + p - \sqrt{|i - j|}$。

solution

肉眼可见决策单调性。然而还是不会维护，抄了题解。

code

struct Node { int l, r, x; };

int N, z[500003];
double f[500003], _sqrt[500003];
std::deque<Node> q;

inline bool check(int x, int y, int k) {
  return z[x] + _sqrt[k - x] > z[y] + _sqrt[k - y];
}

void process() {
  q.clear();
  Node now{1, N, 1};
  for (int i = 2, l, r, mid; i <= N; ++i) {
    if (z[i] < z[now.x]) continue;
    for (l = i, r = N; l <= r; ) {
      mid = (l + r) >> 1;
      if (check(now.x, i, mid)) l = mid + 1;
      else r = mid - 1;
    }
    if (l > N) continue;
    if (l < now.l) {
      now = q.front();
      q.pop_front();
      --i;
      continue;
    }
    now.r = r;
    q.push_front(now);
    now = {l, N, i};
  }
  q.push_front(now);
  now = q.back();
  q.pop_back();
  for (int i = 1; i <= N; ++i) {
    if (now.r < i) now = q.back(), q.pop_back();
    f[i] = std::max(f[i], z[now.x] + _sqrt[i - now.x]);
  }
}

int main() {
  cin >> N;
  for (int i = 1; i <= N; ++i) {
    cin >> z[i], f[i] = z[i];
    _sqrt[i] = sqrt(i);
  }
  process();
  std::reverse(z + 1, z + N + 1);
  std::reverse(f + 1, f + N + 1);
  process();
  for (int i = N; i >= 1; --i)
    cout << std::max((int)ceil(f[i]) - z[i], 0) << '\n';
  cout.flush();
  return 0;
}

---

AGC035D Add and Remove

solution

爆搜就完事了嗷

---

P3978 [TJOI2015]概率论

problem

求 $n$ 个结点的有根二叉树的叶子个数的期望。

solution

自己并不会做，考虑抄仓鼠的题解。

对于一个叶子，可以用一个 pair 描述：去掉该叶子的二叉树，在该二叉树的哪个位置添加这个叶子。

每个叶子和每个 pair 一一对应，考虑计数这个 pair。

去掉该叶子的二叉树有 $N - 1$ 个点，数目为 $\mathrm{Cat}_{N - 1}$。

对于一个 $N - 1$ 个点的二叉树，考虑又多少个空位可以放。总共有 $2(N - 1)$ 个空位，但是有 $N - 2$ 个点已经占据了一个空位。所以有 $N$ 个空位可以添加叶子。

两个方案数相乘，再除以 $\mathrm{Cat}_N$，化简一下发现答案是 $N(N + 1) / (4N - 2)$。

---

P2900 [USACO08MAR]Land Acquisition G

problem

给定 $n$ 个二元组，第 $i$ 个为 $(a_i, b_i)$，将这些二元组分成若干组，每组的费用是其中 $\max{ \{a_i b_i\}}$。求最小总费用。

solution

可以发现，若两个二元组 $i, j$ 满足 $a_i \ge a_j \wedge b_i \ge b_j$，则 $j$ 不会对答案有贡献。可以将数据处理成 $a$ 递增 $b$ 递减的形式，则最优解每一组一定是连续的一段。

可以得到一个 $O(n^2)$ 的转移方程

$$f_i = \min{ \{f_j + a_{j + 1}b_i\}} \ (0 \le j < i)$$

这个方程是有决策单调性的，考虑斜率优化。假设 $j, k$ 满足 $0 \le k < j < i$，若 $j$ 比 $k$ 更优，那么有

$$f_j + a_{j + 1}b_i < f_k + a_{k + 1}b_i \\ f_j - f_k < b_i(a_{k + 1} - a_{j + 1}) \\ b_i > \frac{f_j - f_k}{a_{k + 1} - a_{j + 1}}$$

维护一个下凸壳就可以斜率优化了。总复杂度 $O(n \log n)$。

code

int top, q[50003];
long long f[50003];

struct Node {
  int a, b;
} z[50003]; 

inline double slope(int i, int j) {
  return 1.0 * (f[i] - f[j]) / (z[j + 1].a - z[i + 1].a);
}

int main() {
  int N, N_ = 0;

  cin >> N;
  for (int i = 1; i <= N; ++i)
    cin >> z[i].a >> z[i].b;
  std::sort(z + 1, z + N + 1, [](Node lhs, Node rhs) {
    if (lhs.a != rhs.a) return lhs.a > rhs.a;
    return lhs.b > rhs.b;
  });
  for (int i = 1; i <= N; ++i)
    if (z[i].b > z[N_].b) z[++N_] = z[i];
  N = N_;
  for (int i = 1, h = 1, t = 1; i <= N; ++i) { // q: []
    while (h < t && slope(q[h], q[h + 1]) <= z[i].b) ++h;
    f[i] = f[q[h]] + 1ll * z[q[h] + 1].a * z[i].b;
    while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i)) --t;
    q[++t] = i;
  }
  printf("%lld", f[N]);
  return 0;
}

---

P3195 [HNOI2008]玩具装箱

problem

给定长为 $n$ 的序列 $a$，将序列分成若干段，若 $i \sim j$ 为一段，花费为 $(j - i + \sum_{k = i}^j{a_k} - L)^2$。

solution

容易写出这样的状态转移方程：

$$f_i = \min{ \{f_j + (s_i - s_j + i - j - 1 - L)^2\}}$$

其中 $s_i = \sum_{j = 1}^i{a_i}$。这个方程直接维护是 $O(n^2)$ 的。

令 $S_i = s_i + i, L’ = L + 1$ 得

$$f_i = f_j + (S_i - S_j - L')^2 \\ 2S_i(S_j + L') + f_i = f_j + S_i^2+(S_j + L')^2$$

令 $f_i = b, 2S_i = k$，就出现了若干条直线

$$y = kx + b$$

其中 $x_j = S_j + L’, y_j = f_j + x_i^2$，$S_i$ 对于每个 $i$ 是确定的。我们要做的就是最小化截距 $b$，即要维护一个下凸壳。可以用单调队列 $O(n)$ 地维护。

code

using db = double;

int L, q[50003];
db f[50003], S[50003];

inline db sqr(db x) {
  return x * x;
}

inline db X(int i) {
  return S[i] + L;
}

inline db Y(int i) {
  return f[i] + sqr(S[i] + L);
}

inline db slope(int i, int j) {
  return (Y(i) - Y(j)) / (X(i) - X(j));
}

long long dp() {
  int N;

  cin >> N >> L;
  ++L;
  for (int i = 1, t; i <= N; ++i) {
    cin >> t;
    S[i] = t + S[i - 1];
  }
  for (int i = 1; i <= N; ++i)
    S[i] += i;

  for (int i = 1, h = 1, t = 1; i <= N; ++i) {
    while (h < t && slope(q[h], q[h + 1]) <= 2 * S[i]) ++h;
    f[i] = f[q[h]] + sqr(S[i] - X(q[h]));
    while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i)) --t;
    q[++t] = i;
  }
  return f[N];
}

---

AGC002E Candy Piles

problem

桌上有 $n \ (1 \le n \le 10^5)$ 堆糖果，第 $i$ 堆有 $a_i \ (1 \le a_i \le 10^9)$ 个。

两人轮流进行操作：

1. 将当前最大的一堆全部吃完；
2. 将每堆吃掉一个。

吃完的人输。判断先手或后手必胜。

solution

将序列降序排序（图 1）。两个操作分别代表去掉最左边一行或最下面一列。

我们将原图转化为网格图。这样，操作就转化为了两个玩家向右/上移动一步（图 2），接触到边界的人输。

根据博弈论的一般规律可以整一个 $O(\sum a_i)$ 的 dp 出每个点的结果（图 3，’x’ 代该点表先手必败，’o’ 表示该点先手必胜），但这显然过不去。

有一个 $O(n)$ 的做法：从原点向右上扩张出一个可行的最大的正方形，然后分别向右/上移动。如果最大步数均为偶数，则先手必败；否则先手必胜。

code

bool solve(int N, int *z) {
  std::sort(z + 1, z + N + 1, std::greater<int>());
  for (int i = 1; i <= N; ++i)
    if (z[i + 1] < i + 1) {
      int j = i;
      while (z[j + 1] >= i) ++j;
      return ((z[i] - i) | (j - i)) & 1;
    }
  return 0;
}

---

SP11414 COT3 - Combat on a tree

---

UVA1697 Baggage

这是一道 ACM WF 的 A 题。

---

CF611H New Year and Forgotten Tree

---

P2860 [USACO06JAN]Redundant Paths G

problem

给定一个 $n$ 个结点 $m$ 条边的无向连通图。要求在这张图上加入一些边，使得任意两个结点间都有至少两条没有公共边的路径，求所有合法方案中加入边数的最小值。

solution

考虑钦定一个点为根向外 dfs，转化为有向图，并将边双连通分量进行缩点，形成一棵 dfs 树。答案显然为这棵树的叶子个数的一半上取整。

code

实现时注意一些细节，比如双向边可以按照编号奇偶性划为一组同时标记。

using iarrN = int[5003];

std::bitset<20013> vis;
int N, M, top, tot = 1, dft, cntDCC;
iarrN U, V, s, bel, dfn, low, deg, head;

struct Edge {
  int nxt, to;
} e[20013];

void tarjan(int u) {
  s[++top] = u;
  dfn[u] = low[u] = ++dft;
  for (int i = head[u], v; i; i = e[i].nxt) {
    if (vis[i]) continue;
    if (!dfn[v = e[i].to]) {
      vis.set(i), vis.set(i ^ 1);
      tarjan(v);
      vis.reset(i ^ 1), vis.reset(i ^ 1);
      dmin(low[u], low[v]);
    } else dmin(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    ++cntDCC;
    do bel[s[top]] = cntDCC; while (s[top--] != u);
  }
}

int main() {
  cin >> N >> M;
  for (int i = 1; i <= M; ++i) {
    cin >> U[i] >> V[i];
    addEdge(U[i], V[i]), addEdge(V[i], U[i]);
  }
  tarjan(1);
  for (int i = 1; i <= M; ++i)
    if (bel[U[i]] != bel[V[i]])
      ++deg[bel[U[i]]], ++deg[bel[V[i]]];
  int ans = 0;
  for (int i = 1; i <= cntDCC; ++i)
    if (deg[i] == 1) ++ans;
  printf("%d", (ans + 1) >> 1);
  return 0;
}