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.

咕咕。