B
题目大意：设 $n, m, \ell$ 为正整数。你做了一个不幸的决定，要在弗雷迪·法兹熊披萨店当夜间保安，这里有 $m$ 个机械玩偶，编号为 $1, \ldots, m$，等着吓你一跳。夜晚持续 $\ell$ 秒，编号为 $1, \ldots, \ell$。第 $j$ 个机械玩偶有一个危险等级 $d_j$，初始时 $d_1 = \ldots = d_m = 0$。
数据范围：$1 \le t \le 10^4$，$1 \leq n, m, \ell \leq 2 \cdot 10^5$，$n \leq \ell$，$1 \leq m \cdot \ell \leq 2 \cdot 10^5$，$1 \leq a_1 < \ldots < a_n \leq \ell$，$\sum m \cdot \ell \le 2 \cdot 10^5$。
思路：
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| void solve() {
int n, m, l;
cin >> n >> m >> l;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
vl d(m);
int l1 = 0, r = 1e9, mid;
int ans = -1;
vi tem;
int res = 0;
rep(i, 0, n - 1) {
if (i == 0) {
if (a[i] == 1)
continue;
else
tem.push_back(a[i]);
continue;
}
tem.push_back(a[i] - a[i - 1]);
}
if (a[n - 1] != l) res = l - a[n - 1];
int m1 = sz(tem);
auto check = [&](int mid) -> bool {
fill(all(d), 0LL);
int maxx = 0;
rep(i, 0, m1 - 1) {
int tem2 = m1 - i + 1;
if (tem2 >= m) {
sort(all(d));
ll te = tem[i];
rep(j, 1, m) {
ll diff = (j == m) ? 0 : (d[j] - d[j - 1]);
ll cnt = diff * j;
if (j < m && te >= cnt) {
te -= cnt;
} else {
ll tem3 = d[j - 1] + te / j;
ll re = te % j;
rep(v, 0, j - 1) { d[v] = tem3 + (v >= j - re ? 1 : 0); }
break;
}
}
sort(all2(d));
d[0] = 0;
} else {
sort(all2(d));
sort(d.begin(), d.begin() + tem2);
ll te = tem[i];
rep(j, 1, tem2) {
ll diff = (j == tem2) ? 0 : (d[j] - d[j - 1]);
ll cnt = diff * j;
if (j < tem2 && te >= cnt) {
te -= cnt;
} else {
ll tem3 = d[j - 1] + te / j;
ll re = te % j;
rep(v, 0, j - 1) { d[v] = tem3 + (v >= j - re ? 1 : 0); }
break;
}
}
sort(all2(d));
d[0] = 0;
}
}
sort(all2(d));
return d[0] + res <= mid;
};
while (l1 <= r) {
mid = (l1 + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else
l1 = mid + 1;
}
cout << ans << endl;
return;
}
|
C
题目大意：设 $n,h$ 为正整数。Swampy 鳄鱼需要给他的浴缸注水，需要帮他引来水。Swampy 的家上方有一个 $h \times n$ 的网格，由泥土和水瓷砖组成，$n$ 列编号为 $1, \ldots, n$。在第 $i$ 列的最底部，有 $a_i$ 个瓷砖是泥土，剩下的顶端都是水瓷砖。为了把水送到 Swampy，你可以在任意不是泥土的瓷砖上安装排水口。安装排水口后，所有能够通过仅向下、向左或向右移动且不经过泥土瓷砖而到达排水口的水瓷砖都会被引走。
数据范围：$1 \le t \le 10^3$，$1 \leq n \leq 2000, 1 \leq h \leq 10^9$，$1 \leq a_i \leq h$，$\sum n \le 2000$。
思路：
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| void solve() {
int n;
ll h;
cin >> n >> h;
vl pre(n);
vl suf(n);
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) a[i] = h - a[i];
ll maxx = LLONG_MIN;
rep(i, 0, n - 1) {
ll tot = 0;
ll tem = LLONG_MAX;
frep(j, i, 0) {
tem = min(tem, a[j]);
tot += tem;
}
pre[i] = tot;
}
frep(i, n - 1, 0) {
ll tot = 0;
ll tem = LLONG_MAX;
rep(j, i, n - 1) {
tem = min(tem, a[j]);
tot += tem;
}
suf[i] = tot;
}
vl cnt(n);
rep(i, 0, n - 1) {
cnt[i] = pre[i] + suf[i] - a[i];
maxx = max(maxx, cnt[i]);
}
rep(i, 0, n - 1) {
int idx = i;
rep(j, i + 1, n - 1) {
if (a[j] < a[idx]) idx = j;
maxx = max(maxx, cnt[i] + cnt[j] - cnt[idx]);
}
}
cout << maxx << endl;
return;
}
|
D
题目大意：给定两个正整数 $n$ 和 $k$。你得到了一棵有 $n$ 个顶点的树（见注释$^*$），编号为 $1, \ldots, n$。
数据范围：$1 \le t \le 10^4$，$3 \leq n \leq 5 \cdot 10^5$，$1 \leq k, v \leq n$，$1 \leq a, b \leq n, a \neq b$，$\sum n \le 5 \cdot 10^5$。
思路：
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
29
30
| void solve() {
int n, k, v, x, y;
cin >> n >> k >> v;
v--;
vvi ma(n);
rep(i, 1, n - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
}
vi dis(n, 1);
auto dfs = [&](this auto&& dfs, int x, int pa) -> void {
bool isleaf = true;
dis[x] = INT_MAX / 3;
for (int& p : ma[x]) {
if (p == pa) continue;
isleaf = false;
dfs(p, x);
if (dis[x] + dis[p] < k + 3) dis[x] = 1;
dis[x] = min(dis[x], dis[p] + 1);
}
if (isleaf) dis[x] = 1;
};
dfs(v, -1);
if (dis[v] == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
return;
}
|
E1
题目大意：这是一道构造题。本题和其它版本的不同之处在于，需要构造一个答案，或者报告无法实现，并且 $0 \leq b_i \leq 10^9$。只有在你解决了该题所有版本后，才可以进行 hack 操作。“大师工匠”不喜欢重复性工作——修复基地、十五次升级大本营，以及又做一题关于 MEX 的编程题。因此，这不会是你平常遇到的 MEX 问题。
数据范围：$1 \le t \leq 10^4$，$1 \leq n \leq 2 \times 10^5$，$0 \leq a_i \leq 10^9$，$\sum n \le 2 \times 10^5$。
思路：
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
vi b(n);
vector<bool> vis(n + 1, false);
rep(i, 0, n - 1) {
if (a[i] <= n) vis[a[i]] = true;
}
bool flag = true;
rep(i, 0, n - 1) {
if (i >= 1 && a[i] > a[i - 1]) {
flag = false;
break;
}
if (a[i] < n - i - 1 || a[i] > n) {
flag = false;
break;
}
}
if (!flag) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
vi tem;
rep(i, 0, n) {
if (vis[i])
continue;
else
tem.push_back(i);
}
rep(i, 0, n - 1) {
if (i == 0) {
b[i] = tem.back();
tem.pop_back();
continue;
}
if (a[i] == a[i - 1]) {
b[i] = tem.back();
tem.pop_back();
} else {
b[i] = 1e9;
}
}
rep(i, 0, n - 1) cout << b[i] << ' ';
cout << endl;
return;
}
|
E2
题目大意：这是该题目的计数版本。与其他版本的区别在于，本题需要统计满足 $0 \leq b_i \leq n$ 的构造方案数量。只有你完成了本题的所有版本，才可以进行 hack。大师建筑师不喜欢重复性的任务——修补基地、升级城镇大厅十五次、还有更多关于 MEX 的编程题。所以，这不是一个普通的 MEX 题目。对于任意正整数 $k$，定义整数集合 $S$ 的 $k$-mex 为 $S$ 中未出现的第 $k$ 小非负整数。
数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 2\times 10^5$，$0 \leq a_i \leq 10^9$，$\sum n \le 2\times 10^5$。
思路：
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| const int MOD = 1e9 + 7;
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
ll ans = 1;
vi b(n);
vector<bool> vis(n + 1, false);
rep(i, 0, n - 1) {
if (a[i] <= n) vis[a[i]] = true;
}
bool flag = true;
rep(i, 0, n - 1) {
if (i >= 1 && a[i] > a[i - 1]) {
flag = false;
break;
}
if (a[i] < n - i - 1 || a[i] > n) {
flag = false;
break;
}
}
if (!flag) {
cout << 0 << endl;
return;
}
vi pre(n + 1);
rep(i, 0, n) {
if (vis[i])
pre[i] = pre[i - 1];
else
pre[i] = pre[i - 1] + 1;
}
rep(i, 0, n - 1) {
if (i >= 1 && a[i] == a[i - 1]) {
ans *= 1LL * (a[i] - (n - i - 1));
ans %= MOD;
} else {
ans *= 1LL * (i + 1);
ans %= MOD;
}
}
cout << ans << endl;
return;
}
|
