div1+2

A.

存在一个 $i \geq x$ 就是 YES。

B.

首先如果 $n$ 是一个偶数，那么无解。

$\lfloor\frac{n-1}{2}\rfloor$ 和 $\lceil \frac{n+1}{2}\rceil$ 一奇一偶，递归构造即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> ff;
auto f = [&](auto f, int x) -> void {
    if (x == 1) {
        return;
    }
    int y1 = (x + 1) / 2;
    int y2 = (x - 1) / 2;
    if (y1 % 2 == 1) {
        f(f, y1);
        ff.emplace_back(1);
    } else {
        f(f, y2);
        ff.emplace_back(2);
    }
};

C.

首先答案有一个固定的上界，是全部删完之后加一个 $1$，因为不允许为空，即为 $n \times c + d$。

确定这个上界之后，枚举 $a_i$，假定最后的排列是 $[1, a_i]$，计算贡献即可。

D.

模拟题，记得开 ll。

E.

如果我选定了一个点，遍历到了一整个连通块，那么我一定找一个和联通块有边，且 $a_i$ 最小的一个点，来判断是否可行，这个很容易引导到一个启发式合并的思路，但是没有必要真的去启发式合并。

只需要维护一个堆，类似 dij 一样扩展就可以了。

F.

首先假设所有的叶子结点的深度为 $dep_i$，那么一定有 $\sum (\frac{1}{m})^{dep_i} = 1$。（显然）

然后考虑一个答案 $x$ 是否合法：

首先有 $a_i + dep_i \leq x$，那么可以得到 $\sum (\frac{1}{m})^{x-a_i} \leq \sum (\frac{1}{m})^{dep_i} = 1$

也就是 $\sum m^{a_i} \leq m^x$。

可以用线段树/珂朵莉树维护。

G.

如果使用 $dp_{i, j, k}$ 来表示前 $i$ 个的最大前缀和是 $j$，当前为 $k$，那么复杂度是 $n^3$ 。

每一维都删不掉，但是可以考虑反过来。

$f_i = \max(f_{i+1}+a_i, 0)$ ，用 $f_i$ 来表示 $[i, n]$ 的前缀最大值。

这启发我们可以设计状态 $dp_{i, j}$ 表示当前考虑到 $i$，$f_{i + 1} = j$ 的贡献。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vector<long long> p(n), q(n);
for (int i = 0; i < n; i++) {
  long long x, y;
  cin >> x >> y;
  p[i] = x * inverse(y) % P;
  q[i] = P + 1 - p[i];
}

vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
for (int i = 0; i <= n; i++) {
  cin >> dp[0][i];
}
for (int i = 0; i < n; i++) {
  for (int j = 0; j <= n; j++) {
    if (j + 1 <= n) {
      dp[i + 1][j] += dp[i][j + 1] * p[i] % P; // +1
      if (dp[i + 1][j] >= P) {
        dp[i + 1][j] -= P;
      }
    }
    dp[i + 1][j] += dp[i][max(j - 1, 0)] * q[i] % P; // -1
    if (dp[i + 1][j] >= P) {
      dp[i + 1][j] -= P;
    }
  }
  cout << dp[i + 1][0] << " ";
}
cout << "\n";

H.

咕咕。