CSP-S 卷

（归并第 $k$ 小）已知两个长度均为 $n$ 的有序数组 a1 和 a2（均为递增序，但不保证严格单调递增），并且给定正整数 $k$（$1\le k\le 2n$），求数组 a1 和 a2 归并排序后的数组里第 $k$ 小的数值。

试补全程序。

1  #include <bits/stdc++.h>
2  using namespace std;
3 
4  int solve(int *a1, int *a2, int n, int k) {
5      int left1 = 0, right1 = n - 1;
6      int left2 = 0, right2 = n - 1;
7      while (left1 <= right1 && left2 <= right2) {
8          int m1 = (left1 + right1) >> 1;
9          int m2 = (left2 + right2) >> 1;
10          int cnt = ①;
11          if (②) {
12              if (cnt < k) left1 = m1 + 1;
13              else right2 = m2 - 1;
14          } else {
15              if (cnt < k) left2 = m2 + 1;
16              else right1 = m1 - 1;
17          }
18      }
19      if (③) {
20          if (left1 == 0) {
21              return a2[k - 1];
22          } else {
23              int x = a1[left1 - 1], ④;
24              return std::max(x, y);
25          }
26      } else {
27          if (left2 == 0) {
28              return a1[k - 1];
29          } else {
30              int x = a2[left2 - 1], ⑤;
31              return std::max(x, y);
32          }
33      }
34  }

（匠人的自我修养）一个匠人决定要学习 $n$ 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $n$（$1\le n\le10^3$），以及已有经验值（$\le10^7$）。

接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值（$\le10^7$），以及学会第 $i$ 个技术后可获得的经验值（$\le10^4$）。

接下来 $n$ 行。第 $i$ 行的第一个数 $m_i$（$0\le m_i<n$），表示第 $i$ 个技术的相关技术数量。紧跟着 $m_i$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号。

输出最多能学会的新技术个数。

下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。

1  #include <cstdio>
2  using namespace std;
3  const int maxn = 1001;
4 
5  int n;
6  int cnt[maxn];
7  int child[maxn][maxn];
8  int unlock[maxn];
9  int points;
10  int threshold[maxn], bonus[maxn];
11 
12  bool find() {
13      int target = -1;
14      for (int i = 1; i <= n; ++i)
15          if (① && ②) {
16              target = i;
17              break;
18          }
19      if (target == -1)
20          return false;
21      unlock[target] = -1;
22      ③;
23      for (int i = 0; i < cnt[target]; ++i)
24          ④;
25      return true;
26  }
27 
28  int main() {
29      scanf("%d%d", &n, &points);
30      for (int i = 1; i <= n; ++i) {
31          cnt[i] = 0;
32          scanf("%d%d", &threshold[i], &bonus[i]);
33      }
34      for (int i = 1; i <= n; ++i) {
35          int m;
36          scanf("%d", &m);
37          ⑤;
38          for (int j = 0; j < m; ++j) {
39              int fa;
40              scanf("%d", &fa);
41              child[fa][cnt[fa]] = i;
42              ++cnt[fa];
43          }
44      }
45      int ans = 0;
46      while (find())
47          ++ans;
48      printf("%d\n", ans);
49      return 0;
50  }

（取石子）Alice 和 Bob 两个人在玩取石子游戏。他们制定了 $n$ 条取石子的规则，第 $i$ 条规则为：如果剩余石子的个数大于等于 $a[i]$ 且大于等于 $b[i]$，那么他们可以取走 $b[i]$ 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 $n$（$1\le n\le64$），以及石子个数 $m$（$\le10^7$）。

接下来 $n$ 行。第 $i$ 行有两个正整数 $a[i]$ 和 $b[i]$。（$1\le a[i]\le10^7,1\le b[i]\le64$）

如果先取石子的人必胜，那么输出 Win，否则输出 Loss。

提示：可以使用动态规划解决这个问题。由于 $b[i]$ 不超过 $64$，所以可以使用 $64$ 位无符号整数去压缩必要的状态。status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

代码说明：

~ 表示二进制补码运算符，它将每个二进制位的 $0$ 变为 $1$、$1$ 变为 $0$；

^ 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$，反之为 $1$。

ull 标识符表示它前面的数字是 unsigned long long 类型。

试补全程序。

1  #include <cstdio>
2  #include <algorithm>
3  using namespace std;
4 
5  const int maxn = 64;
6 
7  int n, m;
8  int a[maxn], b[maxn];
9  unsigned long long status, trans;
10  bool win;
11 
12  int main() {
13      scanf("%d%d", &n, &m);
14      for (int i = 0; i < n; ++i)
15          scanf("%d%d", &a[i], &b[i]);
16      for (int i = 0; i < n; ++i)
17          for (int j = i + 1; j < n; ++j)
18              if (a[i] > a[j]) {
19                  swap(a[i], a[j]);
20                  swap(b[i], b[j]);
21              }
22      status = ①;
23      trans = 0;
24      for (int i = 1, j = 0; i <= m; ++i) {
25          while (j < n && ②) {
26              ③;
27              ++j;
28          }
29          win = ④;
30          ⑤;
31      }
32      puts(win ? "Win" : "Loss");
33      return 0;
34  }

（分数背包）小 S 有 $n$ 块蛋糕，编号从 $1$ 到 $n$。第 $i$ 块蛋糕的价值是 $w_i$，体积是 $v_i$。他有一个大小为 $B$ 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 $B$。

他打算选择一些蛋糕装入盒子，他希望盒里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $\alpha$（$0<\alpha<1$），并将一块价值是 $w$、体积为 $v$ 的蛋糕切割成两块，其中一块的价值是 $\alpha w$、体积是 $\alpha v$，另一块的价值是 $(1-\alpha)w$、体积是 $(1-\alpha)v$。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如 $n=3$，$B=8$，三块蛋糕的价值分别是 $4$、$4$、$2$，体积分别是 $5$、$3$、$2$。那么最优的方案就是将体积为 $5$ 的蛋糕切成两份，一份体积是 $3$，价值是 $2.4$，另一份体积是 $2$，价值是 $1.6$，然后把体积是 $3$ 的那部分和后两块蛋糕打包装盒子。最优的价值之和是 $8.4$，故程序输出 $42/5$。

输入的数据范围为：$1\le n\le1000$，$1\le B\le10^5$，$1\le w_i,v_i\le100$。

提示：将所有的蛋糕按照性价比 $w_i/v_i$ 从大到小排序后进行贪心选择。

试补全程序。

1  #include <cstdio>
2  using namespace std;
3 
4  const int maxn = 1005;
5 
6  int n, B, w[maxn], v[maxn];
7 
8  int gcd(int u, int v) {
9      if (v == 0)
10          return u;
11      return gcd(v, u % v);
12  }
13 
14  void print(int w, int v) {
15      int d = gcd(w, v);
16      w = w / d;
17      v = v / d;
18      if (v == 1)
19          printf("%d\n", w);
20      else
21          printf("%d/%d\n", w, v);
22  }
23 
24  void swap(int &x, int &y) {
25      int t = x; x = y; y = t;
26  }
27 
28  int main() {
29      scanf("%d %d", &n, &B);
30      for (int i = 1; i <= n; i ++) {
31          scanf("%d%d", &w[i], &v[i]);
32      }
33      for (int i = 1; i < n; i ++)
34          for (int j = 1; j < n; j ++)
35              if (①) {
36                  swap(w[j], w[j + 1]);
37                  swap(v[j], v[j + 1]);
38              }
39      int curV, curW;
40      if (②) {
41          ③
42      } else {
43          print(B * w[1], v[1]);
44          return 0;
45      }
46 
47      for (int i = 2; i <= n; i ++)
48          if (curV + v[i] <= B) {
49              curV += v[i];
50              curW += w[i];
51          } else {
52              print(④);
53              return 0;
54          }
55      print(⑤);
56      return 0;
57  }

（最优子序列）取 $m=16$，给出长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$（$0\le a_i<2^m$）。对于一个二进制数 $x$，定义其分值 $w(x)$ 为 $x+\operatorname{popcnt}(x)$，其中 $\operatorname{popcnt}(x)$ 表示 $x$ 二进制表示中 $1$ 的个数。对于一个子序列 $b_1,b_2,\ldots,b_k$，定义其子序列分值 $S$ 为 $w(b_1\oplus b_2)+w(b_2\oplus b_3)+\cdots+w(b_{k-1}\oplus b_k)$。其中 $\oplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$。求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数 $n$（$1\le n\le40000$）。接下来一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

提示：考虑优化朴素的动态规划算法，将前 $m/2$ 位和后 $m/2$ 位分开计算。

Max[x][y] 表示当前的子序列下一个位置的高 $8$ 位是 $x$、最后一个位置的低 $8$ 位是 $y$ 时的最大价值。

试补全程序。

1  #include <iostream>
2 
3  using namespace std;
4 
5  typedef long long LL;
6 
7  const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
8  const LL INF = 1000000000000000LL;
9  LL Max[MS + 4][MS + 4];
10 
11  int w(int x)
12  {
13      int s = x;
14      while (x)
15      {
16          ①;
17          s++;
18      }
19      return s;
20  }
21 
22  void to_max(LL &x, LL y)
23  {
24      if (x < y)
25          x = y;
26  }
27 
28  int main()
29  {
30      int n;
31      LL ans = 0;
32      cin >> n;
33      for (int x = 0; x <= MS; x++)
34          for (int y = 0; y <= MS; y++)
35              Max[x][y] = -INF;
36      for (int i = 1; i <= n; i++)
37      {
38          LL a;
39          cin >> a;
40          int x = ②, y = a & MS;
41          LL v = ③;
42          for (int z = 0; z <= MS; z++)
43              to_max(v, ④);
44          for (int z = 0; z <= MS; z++)
45              ⑤;
46          to_max(ans, v);
47      }
48      cout << ans << endl;
49      return 0;
50  }

（魔法数字）小 H 的魔法数字是 $4$。给定 $n$，他希望用若干个 $4$ 进行若干次加法、减法和整除运算得到 $n$。但由于小 H 计算能力有限，计算过程中只能出现不超过 $M=10000$ 的正整数。求至少可能用到多少个 $4$。

例如，当 $n=2$ 时，有 $2=(4+4)/4$，用到了 $3$ 个 $4$，是最优方案。

试补全程序。

1  #include <iostream>
2  #include <cstdlib>
3  #include <climits>
4 
5  using namespace std;
6 
7  const int M = 10000;
8  bool Vis[M + 1];
9  int F[M + 1];
10 
11  void update(int &x, int y) {
12      if (y < x)
13          x = y;
14  }
15 
16  int main() {
17      int n;
18      cin >> n;
19      for (int i = 0; i <= M; i++)
20          F[i] = INT_MAX;
21      ①;
22      int r = 0;
23      while (②) {
24          r++;
25          int x = 0;
26          for (int i = 1; i <= M; i++)
27              if (③)
28                  x = i;
29          Vis[x] = 1;
30          for (int i = 1; i <= M; i++)
31              if (④) {
32                  int t = F[i] + F[x];
33                  if (i + x <= M)
34                      update(F[i + x], t);
35                  if (i != x)
36                      update(F[abs(i - x)], t);
37                  if (i % x == 0)
38                      update(F[i / x], t);
39                  if (x % i == 0)
40                      update(F[x / i], t);
41              }
42      }
43      cout << F[n] << endl;
44      return 0;
45  }

（容器分水）有两个容器，容器 $1$ 的容量为 $a$ 升，容器 $2$ 的容量为 $b$ 升；同时允许下列三种操作：

1. FILL(i)：用水龙头将容器 $i$（$i\in\{1,2\}$）灌满水；
2. DROP(i)：将容器 $i$ 的水倒进下水道；
3. POUR(i,j)：将容器 $i$ 的水倒进容器 $j$。完成此操作后，要么容器 $j$ 被灌满，要么容器 $i$ 被清空。

求只使用上述两个容器和三种操作，获得恰好 $c$ 升水的最少操作数和操作序列。上述 $a,b,c$ 均为不超过 $100$ 的正整数，且 $c\le\max\{a,b\}$。

试补全程序。

1  #include <bits/stdc++.h>
2  using namespace std;
3  const int N = 110;
4 
5  int f[N][N];
6  int ans;
7  int a, b, c;
8  int init;
9 
10  int dfs(int x, int y) {
11      if (f[x][y] != init)
12          return f[x][y];
13      if (x == c || y == c)
14          return f[x][y] = 0;
15      f[x][y] = init - 1;
16      f[x][y] = min(f[x][y], dfs(a, y) + 1);
17      f[x][y] = min(f[x][y], dfs(x, b) + 1);
18      f[x][y] = min(f[x][y], dfs(0, y) + 1);
19      f[x][y] = min(f[x][y], dfs(x, 0) + 1);
20      int t = min(a - x, y);
21      f[x][y] = min(f[x][y], ①);
22      t = min(x, b - y);
23      f[x][y] = min(f[x][y], ②);
24      return f[x][y];
25  }
26 
27  void go(int x, int y) {
28      if (③)
29          return;
30      if (f[x][y] == dfs(a, y) + 1) {
31          cout << "FILL(1)" << endl;
32          go(a, y);
33      } else if (f[x][y] == dfs(x, b) + 1) {
34          cout << "FILL(2)" << endl;
35          go(x, b);
36      } else if (f[x][y] == dfs(0, y) + 1) {
37          cout << "DROP(1)" << endl;
38          go(0, y);
39      } else if (f[x][y] == dfs(x, 0) + 1) {
40          cout << "DROP(2)" << endl;
41          go(x, 0);
42      } else {
43          int t = min(a - x, y);
44          if (f[x][y] == ④) {
45              cout << "POUR(2,1)" << endl;
46              go(x + t, y - t);
47          } else {
48              t = min(x, b - y);
49              if (f[x][y] == ⑤) {
50                  cout << "POUR(1,2)" << endl;
51                  go(x - t, y + t);
52              } else
53              assert(0);
54          }
55      }
56  }
57 
58  int main() {
59      cin >> a >> b >> c;
60      ans = 1 << 30;
61      memset(f, 127, sizeof f);
62      init = **f;
63      if ((ans = dfs(0, 0)) == init - 1)
64          cout << "impossible";
65      else {
66          cout << ans << endl;
67          go(0, 0);
68      }
69  }

（第 $k$ 小路径）给定一张有 $n$ 个点、$m$ 条边的有向无环图，顶点编号从 $0$ 到 $n-1$。

对于一条路径，定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 $k$ 小的路径。保证存在至少 $k$ 条路径。上述参数满足 $1\le n,m\le 10^5$ 和 $1\le k\le 10^{18}$。

在程序中，先求出从每个点出发的路径数量，超过 $10^{18}$ 的数都用 $10^{18}$ 表示。然后根据 $k$ 的值和每个顶点的路径数量确定路径的起点，再类似地依次求出路径中的每个点。

试补全程序。

1  #include <iostream>
2  #include <algorithm>
3  #include <vector>
4 
5  const int MAXN = 100000;
6  const long long LIM = 1000000000000000000ll;
7 
8  int n, m, deg[MAXN];
9  std::vector<int> E[MAXN];
10  long long k, f[MAXN];
11 
12  int next(std::vector<int> cand, long long &k) {
13      std::sort(cand.begin(), cand.end());
14      for (int u : cand) {
15          if (①) return u;
16          k -= f[u];
17      }
18      return -1;
19  }
20 
21  int main() {
22      std::cin >> n >> m >> k;
23      for (int i = 0; i < m; ++i) {
24          int u, v;
25          std::cin >> u >> v; // 一条从 u 到 v 的边
26          E[u].push_back(v);
27          ++deg[v];
28      }
29      std::vector<int> Q;
30      for (int i = 0; i < n; ++i)
31      if (!deg[i]) Q.push_back(i);
32      for (int i = 0; i < n; ++i) {
33          int u = Q[i];
34          for (int v : E[u]) {
35              if (②) Q.push_back(v);
36              --deg[v];
37          }
38      }
39      std::reverse(Q.begin(), Q.end());
40      for (int u : Q) {
41          f[u] = 1;
42          for (int v : E[u]) f[u] = ③;
43      }
44      int u = next(Q, k);
45      std::cout << u << std::endl;
46      while (④) {
47          ⑤;
48          u = next(E[u], k);
49          std::cout << u << std::endl;
50      }
51      return 0;
52  }

（最大值之和）给定整数序列 $a_0,\ldots,a_{n-1}$，求该序列所有非空连续子序列的最大值之和。上述参数满足 $1\le n\le 10^5$ 和 $1\le a_i\le 10^8$。

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$（其中 $0\le l\le r<n$）表示，对应的序列为 $a_l,a_{l+1},\ldots,a_r$。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 [1,2,1,2] 时，要计算子序列 [1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1]、[2,1,2]、[1,2,1,2] 的最大值之和，答案为 $18$。注意，[1,1] 和 [2,2] 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，其中有一些值相同的子序列，但由于它们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

以下程序使用分治算法，时间复杂度为 $O(n\log n)$。试补全程序。

1  #include <iostream>
2  #include <algorithm>
3  #include <vector>
4 
5  const int MAXN = 100000;
6 
7  int n;
8  int a[MAXN];
9  long long ans;
10 
11  void solve(int l, int r) {
12      if (l + 1 == r) {
13          ans += a[l];
14          return;
15      }
16      int mid = (l + r) >> 1;
17      std::vector<int> pre(a + mid, a + r);
18      for (int i = 1; i < r - mid; ++i) ①;
19      std::vector<long long> sum(r - mid + 1);
20      for (int i = 0; i < r - mid; ++i) sum[i + 1] = sum[i] + pre[i];
21      for (int i = mid - 1, j = mid, max = 0; i >= l; --i) {
22          while (j < r && ②) ++j;
23          max = std::max(max, a[i]);
24          ans += ③;
25          ans += ④;
26      }
27      solve(l, mid);
28      solve(mid, r);
29  }
30 
31  int main() {
32      std::cin >> n;
33      for (int i = 0; i < n; ++i) std::cin >> a[i];
34      ⑤;
35      std::cout << ans << std::endl;
36      return 0;
37  }

（序列合并）问题：有两个长度为 $N$ 的单调不降序列 $A$ 和 $B$，序列的每个元素都是小于 $10^9$ 的非负整数。在 $A$ 和 $B$ 中各取一个数相加可以得到 $N^2$ 个和，求其中第 $K$ 小的和。上述参数满足 $N \le 10^5$ 和 $1 \le K \le N^2$。

1  #include <iostream>
2  using namespace std;
3 
4  const int maxn = 100005;
5 
6  int n;
7  long long k;
8  int a[maxn], b[maxn];
9 
10  int* upper_bound(int *a, int *an, int ai) {
11      int l = 0, r = ①;
12      while (l < r) {
13          int mid = (l+r)>>1;
14          if (②) {
15              r = mid;
16          } else {
17              l = mid + 1;
18          }
19      }
20      return ③;
21  }
22 
23  long long get_rank(int sum) {
24      long long rank = 0;
25      for (int i = 0; i < n; ++i) {
26          rank += upper_bound(b, b+n, sum - a[i]) - b;
27      }
28      return rank;
29  }
30 
31  int solve() {
32      int l = 0, r = ④;
33      while (l < r) {
34          int mid = ((long long)l+r)>>1;
35          if (⑤) {
36              l = mid + 1;
37          } else {
38              r = mid;
39          }
40      }
41      return l;
42  }
43 
44  int main() {
45      cin >> n >> k;
46      for (int i = 0; i < n; ++i) cin >> a[i];
47      for (int i = 0; i < n; ++i) cin >> b[i];
48      cout << solve() << endl;
49  }

（次短路）已知一个有 $n$ 个点、$m$ 条边的有向图 $G$，并且给定图中的两个点 $s$ 和 $t$，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行 -1；如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。

1  #include <cstdio>
2  #include <queue>
3  #include <utility>
4  #include <cstring>
5  using namespace std;
6 
7  const int maxn = 2e5+10, maxm = 1e6+10, inf = 522133279;
8 
9  int n, m, s, t;
10  int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
11  int dis[maxn<<1], *dis2;
12  int pre[maxn<<1], *pre2;
13  bool vis[maxn<<1];
14 
15  void add(int a, int b, int c) {
16      ++tot;
17      nxt[tot] = head[a];
18      to[tot] = b;
19      w[tot] = c;
20      head[a] = tot;
21  }
22 
23  bool upd(int a, int b, int d, priority_queue<pair<int, int>> &q) {
24      if (d >= dis[b]) return false;
25      if (b < n) ①;
26      q.push(②);
27      dis[b] = d;
28      pre[b] = a;
29      return true;
30  }
31 
32  void solve() {
33      priority_queue<pair<int, int> > q;
34      q.push(make_pair(0, s));
35      memset(dis, ③, sizeof(dis));
36      memset(pre, -1, sizeof(pre));
37      dis2 = dis+n;
38      pre2 = pre+n;
39      dis[s] = 0;
40      while (!q.empty()) {
41          int aa = q.top().second; q.pop();
42          if (vis[aa]) continue;
43          vis[aa] = true;
44          int a = aa % n;
45          for (int e = head[a]; e; e = nxt[e]) {
46              int b = to[e], c = w[e];
47              if (aa < n) {
48                  if (!upd(a, b, dis[a]+c, q))
49                      ④;
50              } else {
51                  upd(n+a, n+b, dis2[a]+c, q);
52              }
53          }
54      }
55  }
56 
57  void out(int a) {
58      if (a != s) {
59          if (a < n) out(pre[a]);
60          else out(⑤);
61      }
62      printf("%d%c", a%n+1, " \n"[a == n+t]);
63  }
64 
65  int main() {
66      scanf("%d%d%d%d", &n, &m, &s, &t);
67      s--, t--;
68      for (int i = 0; i < m; ++i) {
69          int a, b, c;
70          scanf("%d%d%d", &a, &b, &c);
71          add(a-1, b-1, c);
72      }
73      solve();
74      if (dis2[t] == inf) puts("-1");
75      else {
76          printf("%d\n", dis2[t]);
77          out(n+t);
78      }
79  }

（RMQ 区间最值问题）给定序列 $a_0,\ldots,a_{n-1}$ 和 $m$ 次询问，每次询问给定 $l,r$，求 $\max\{a_l,\ldots,a_r\}$。

为了解决该问题，有一个算法叫 the Method of Four Russians，其时间复杂度为 $O(n+m)$，步骤如下：

1. 建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。

2. 对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。

3. 注意新的问题为 $\pm1\ RMQ$，即相邻两点的深度差一定为 $1$。

下面解决这个 $\pm1\ RMQ$ 问题，“序列”指 Euler 序列：

1. 设 $t$ 为 Euler 序列长度，取 $b=\left\lceil\frac{\log_2 t}{2}\right\rceil$，将序列每 $b$ 个分为一大块，使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度为 $O\!\left(\frac{t}{b}\log t\right)=O(n)$。

2. 对于一个块内的 RMQ 问题，也需要 $O(1)$ 的算法。由于差分数组有 $2^{b-1}$ 种，可以预处理出所有情况下的最值位置，预处理复杂度为 $O(b2^b)$，不超过 $O(n)$。

3. 最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。

试补全程序。

1  #include <iostream>
2  #include <cmath>
3 
4  using namespace std;
5 
6  const int MAXN = 100000, MAXT = MAXN << 1;
7  const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB;
8 
9  struct node {
10      int val;
11      int dep, dfn, end;
12      node *son[2]; // son[0], son[1] 分别表示左右儿子
13  } T[MAXN];
14 
15  int n, t, b, c, Log2[MAXC + 1];
16  int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1];
17  node *root, *A[MAXT], *Min[MAXL][MAXC];
18 
19  void build() { // 建立 Cartesian 树
20      static node *S[MAXN + 1];
21      int top = 0;
22      for (int i = 0; i < n; i++) {
23          node *p = &T[i];
24          while (top && S[top]->val < p->val)
25              ①;
26          if (top)
27              ②;
28          S[++top] = p;
29      }
30      root = S[1];
31  }
32 
33  void DFS(node *p) { // 构建 Euler 序列
34      A[p->dfn = t++] = p;
35      for (int i = 0; i < 2; i++)
36          if (p->son[i]) {
37              p->son[i]->dep = p->dep + 1;
38              DFS(p->son[i]);
39              A[t++] = p;
40          }
41      p->end = t - 1;
42  }
43 
44  node *min(node *x, node *y) {
45      return ③ ? x : y;
46  }
47 
48  void ST_init() {
49      b = (int)(ceil(log2(t) / 2));
50      c = t / b;
51      Log2[1] = 0;
52      for (int i = 2; i <= c; i++)
53          Log2[i] = Log2[i >> 1] + 1;
54      for (int i = 0; i < c; i++) {
55          Min[0][i] = A[i * b];
56          for (int j = 1; j < b; j++)
57              Min[0][i] = min(Min[0][i], A[i * b + j]);
58      }
59      for (int i = 1, l = 2; l <= c; i++, l <<= 1)
60          for (int j = 0; j + l <= c; j++)
61              Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]);
62  }
63 
64  void small_init() { // 块内预处理
65      for (int i = 0; i <= c; i++)
66          for (int j = 1; j < b && i * b + j < t; j++)
67              if (④)
68                  Dif[i] |= 1 << (j - 1);
69      for (int S = 0; S < (1 << (b - 1)); S++) {
70          int mx = 0, v = 0;
71          for (int i = 1; i < b; i++) {
72              ⑤;
73              if (v < mx) {
74                  mx = v;
75                  Pos[S] = i;
76              }
77          }
78      }
79  }
80 
81  node *ST_query(int l, int r) {
82      int g = Log2[r - l + 1];
83      return min(Min[g][l], Min[g][r - (1 << g) + 1]);
84  }
85 
86  node *small_query(int l, int r) { // 块内查询
87      int p = l / b;
88      int S = ⑥;
89      return A[l + Pos[S]];
90  }
91 
92  node *query(int l, int r) {
93      if (l > r)
94          return query(r, l);
95      int pl = l / b, pr = r / b;
96      if (pl == pr) {
97          return small_query(l, r);
98      } else {
99          node *s = min(small_query(l, pl * b + b - 1), small_query(pr * b, r));
100          if (pl + 1 <= pr - 1)
101              s = min(s, ST_query(pl + 1, pr - 1));
102          return s;
103      }
104  }
105 
106  int main() {
107      int m;
108      cin >> n >> m;
109      for (int i = 0; i < n; i++)
110          cin >> T[i].val;
111      build();
112      DFS(root);
113      ST_init();
114      small_init();
115      while (m--) {
116          int l, r;
117          cin >> l >> r;
118          cout << query(T[l].dfn, T[r].dfn)->val << endl;
119      }
120      return 0;
121  }

（特殊最短路）给定一个含 $N$ 个点、$M$ 条边的带权无向图，边权非负。起点为 $S$，终点为 $T$。对于一条 $S$ 到 $T$ 的路径，可以在整条路径中，至多选择一条边作为"免费边"：当第一次经过这条被选中的边时，费用视为 $0$；如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从 $S$ 到 $T$ 的最小总费用。

以下代码求解了上述问题。试补全程序。

1  #include <algorithm>
2  #include <iostream>
3  #include <queue>
4  #include <vector>
5  using namespace std;
6 
7  const long long INF = 1e18;
8 
9  struct Edge {
10      int to;
11      int weight;
12  };
13 
14  struct State {
15      long long dist;
16      int u;
17      int used_freebie; // 0 for not used, 1 for used
18      bool operator>(const State &other) const {
19          return dist > other.dist;
20      }
21  };
22 
23  int main() {
24      int n, m, s, t;
25      cin >> n >> m >> s >> t;
26 
27      vector<vector<Edge>> adj(n + 1);
28      for (int i = 0; i < m; ++i) {
29          int u, v, w;
30          cin >> u >> v >> w;
31          adj[u].push_back({v, w});
32          adj[v].push_back({u, w});
33      }
34 
35      vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
36      priority_queue<State, vector<State>, greater<State>> pq;
37 
38      d[s][0] = 0;
39      pq.push({0, s, ①});
40 
41      while (!pq.empty()) {
42          State current = pq.top();
43          pq.pop();
44 
45          long long dist = current.dist;
46          int u = current.u;
47          int used = current.used_freebie;
48 
49          if (dist > ②) {
50              continue;
51          }
52 
53          for (const auto &edge : adj[u]) {
54              int v = edge.to;
55              int w = edge.weight;
56 
57              if (d[u][used] + w < ③) {
58                  ③ = d[u][used] + w;
59                  pq.push({③, v, used});
60              }
61 
62              if (used == 0) {
63                  if (④ < d[v][1]) {
64                      d[v][1] = ④;
65                      pq.push({d[v][1], v, 1});
66                  }
67              }
68          }
69      }
70 
71      cout << ⑤ << endl;
72      return 0;
73  }

工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有 $n$ 条生产线（编号 $0 \sim n-1$），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为 $1$），否则正常收货（记为 $0$）。受售后压力限制，在所有发货批次中，最多只能有 $k$ 次退货（即结果为 $1$ 的次数 $\le k$）。工厂的目标是，设计最少的间接测试轮数 $w$（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。

以下程序实现了工厂的目标，包含两部分：

i) 确定 $w$ 的最小值，并设计最优测试方案；

ii) 根据测试结果推断存在缺陷的生产线。该程序确定 $w$ 最小值的方法为：

由于不同的生产线故障时，测试应当返回不同的结果，因此 $w$ 轮测试的可能结果数不应少于生产线数量。

test_subset() 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第 $1$ 批次、最高位是第 $w$ 批次）；其实现在此处未给出。

试补全程序。

程序代码

1  #include <algorithm>
2  #include <cstddef>
3  #include <iostream>
4  #include <vector>
5  using namespace std;
6  long long comb(int w, int i) {
7      if (i < 0 || i > w) {
8          return 0;
9      }
10      long long res = 1;
11      for (int t = 1; t <= i; ++t) {
12          res = res * (w - t + 1) / t;
13      }
14      return res;
15  }
16  // 计算长度为 w、1 的个数 ≤ k 的码字总数
17  long long count_patterns(int w, int k) {
18      long long total = 0;
19      for (int t = 0; t <= min(w, k); ++t) {
20          total += comb(w, t);
21      }
22      return total;
23  }
24  // 抽象测试接口
25  int test_subset(const vector<vector<int>> &plan);
26  int solve(int n, int k) {
27      // === 第 1 步：求最小 w ===
28      int w = 1;
29      while (___①___) {
30          ++w;
31      }
32      cout << w << endl;
33      // === 第 2 步：生成测试方案 ===
34      vector<vector<int>> code(n, vector<int>(w, 0));
35      int idx = 0;
36      for (int ones = 0; ones <= k && idx < n; ++ones) {
37          vector<int> bits(w, 0);
38          fill(bits.begin(), bits.begin() + ones, 1);
39          do {
40              for (int b = 0; b < w; ++b) {
41                  code[idx][b] = bits[b];
42              }
43              ++idx;
44              if (idx >= n) {
45                  break;
46              }
47          } while (std::___②___);
48      }
49      vector<vector<int>> plan(w);
50      for (int i = 0; i < w; ++i) {
51          for (int j = 0; j < n; ++j) {
52              if (___③___) {
53                  plan[i].push_back(j);
54              }
55          }
56      }
57      // === 第 3 步：调用测试接口 ===
58      int signature = test_subset(plan);
59      // === 第 4 步：结果解码 ===
60      vector<int> sig_bits(w, 0);
61      for (int i = 0; i < w; ++i) {
62          if (___④___) {
63              sig_bits[i] = 1;
64          }
65      }
66      for (int j = 0; j < n; ++j) {
67          if (___⑤___) return j;
68      }
69  }
70  int main() {
71      int n,k;
72      cin >> n >> k;
73      int ans = solve();
74      cout << ans << endl;
75      return 0;
76  }