B
题目大意：有 $n$ 个斐波那契立方体，其中第 $i$ 个立方体的边长等于 $f_i$，这里 $f_i$ 是第 $i$ 个斐波那契数。在这个问题中，斐波那契数的定义如下： - $f_{1} = 1$ - $f_{2} = 2$ - $f_{i} = f_{i - 1} + f_{i - 2}$ （当 $i > 2$ 时） 还有 $m$ 个空盒子，其中第 $i$ 个盒子的宽度为 $w_i$，长度为 $l_i$，高度为 $h_i$。
数据范围：$1 \le t \le 10^{3}$，$2 \le n \le 10$，$1 \le m \le 2 \cdot 10^{5}$，$1 \le w_i, l_i, h_i \le 150$，$\sum m \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
| using i128 = __int128_t;
void solve() {
ll n, m, x, y, z;
cin >> n >> m;
vector<trl> ma;
vl f(n + 1);
f[1] = 1, f[2] = 2;
rep(i, 3, n) f[i] = f[i - 1] + f[i - 2];
string res = "";
rep(i, 0, m - 1) {
cin >> x >> y >> z;
vl tem = {x, y, z};
ranges::sort(tem);
if (tem[2] >= f[n] + f[n - 1] && tem[1] >= f[n] && tem[0] >= f[n])
res.push_back('1');
else
res.push_back('0');
}
cout << res << endl;
return;
}
|
C
题目大意：给定一个由 $n$ 个整数构成的数组 $a_1, a_2, \dots, a_n$。每次操作，你可以执行以下两种操作之一： - 选择一个位置 $i$（$1 < i \le n$），将第 $i$ 个元素左侧的所有元素都赋值为 $a_i$，即将所有 $a_j$（$1 \le j < i$）赋值为 $a_i$。该操作的代价为 $(i - 1) \cdot a_i$。- 选择一个位置 $i$（$1 \le i < n$），将第 $i$ 个元素右侧的所有元素都赋值为 $a_i$，即将所有 $a_j$（$i < j \le n$）赋值为 $a_i$。该操作的代价为 $(n - i) \cdot a_i$。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 5 \times 10^5$，$1 \le a_i \le n$，$\sum n \le 5 \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
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
bool flag = true;
rep(i, 1, n - 1) {
if (a[i] != a[i - 1]) {
flag = false;
break;
}
}
if (flag) {
cout << 0 << endl;
return;
}
ll ans = LLONG_MAX;
vector<pll> tem;
int las = 0;
rep(i, 0, n - 1) {
if ((i > 0 && a[i] != a[i - 1])) {
tem.emplace_back(las, i - 1);
las = i;
}
if (i == n - 1) tem.emplace_back(las, i);
}
for (auto& [x, y] : tem) {
ans = min(ans, a[x] * x + a[y] * (n - 1 - y));
}
cout << ans << endl;
return;
}
|
D
题目大意：新学期即将开始，需要为第一天制定课程表。学院共有 $n$ 个班级和 $m$ 个教室。已知每个班级在第一天恰好有 $6$ 节课，并且所有班级的第 $k$ 节课在同一时间进行。每节课都必须安排在一个教室中，并且同一时间同一个教室不能被多个班级使用。每个教室都有自己的编号（至少为三位数），该编号除最后两位外的所有数字表示教室所在的楼层。楼层之间可以通过楼梯移动；对于任意楼层 $x>1$，可以下到 $x-1$ 层，也可以上到 $x+1$ 层；从第一层只能上到第二层；从第 $10^7$ 层（即最高层）只能下到第 $9999999$ 层。院长办公室决定制定课程表，使得学生在楼层间的移动尽可能多，即所有班级在楼层间的总移动次数最大。
数据范围：$1 \le t \le 10^{3}$，$1 \le n \le m \le 10^{5}$，$100 \le a_i < 10^9$，$\sum m \le 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
| void solve() {
int n, m;
cin >> n >> m;
vector<int> a(m);
for (int i = 0; i <= m - 1; i++) cin >> a[i];
vector<vector<int>> res(n, vector<int>(7, 0));
ranges::sort(a);
int tem = n / 2;
for (int i = 0; i <= tem - 1; i++) res[i][1] = a[i];
for (int i = n - 1; i > tem - 1; i--) res[i][1] = a[m - (n - i)];
for (int j = 2; j <= 6; j++) {
if (j % 2 == 0) {
for (int i = 0; i <= tem - 1; i++) res[i][j] = a[m - i - 1];
for (int i = n - 1; i > tem - 1; i--) res[i][j] = a[n - 1 - i];
} else {
for (int i = 0; i <= tem - 1; i++) res[i][j] = a[i];
for (int i = n - 1; i > tem - 1; i--) res[i][j] = a[m - (n - i)];
}
}
for (auto p : res) {
for (int i = 1; i <= 6; i++) cout << p[i] << ' ';
cout << endl;
}
return;
}
|
E
题目大意：给定一个只包含拉丁字母前 $3$ 个字母的字符串 $s$，即字符串中的每个字符都是 $a$、$b$ 或 $c$。同时给定 $q$ 个操作。每个操作会给定两个字母 $x$ 和 $y$（均为 $a$、$b$ 或 $c$），对于每个操作，必须执行以下两种操作之一： - 将字符串 $s$ 中任意（一个）出现的字母 $x$ 改为字母 $y$（如果 $x$ 至少出现一次）； - 什么都不做。目标是按照给定顺序执行所有操作，使得字符串 $s$ 最终字典序最小。
数据范围：$1 \le t \le 10^{3}$，$1 \le n, q \le 2 \times 10^{5}$，$\sum n \le 2 \times 10^{5}$，$\sum q \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
51
52
53
54
55
56
57
58
59
| using i128 = __int128_t;
void solve() {
ll n, q;
cin >> n >> q;
string s;
char x, y;
cin >> s;
set<ll> ma[3][3];
rep(i, 0, q - 1) {
cin >> x >> y;
ma[x - 'a'][y - 'a'].insert(i);
}
rep(i, 0, n - 1) {
int tem = s[i] - 'a';
if (!tem) continue;
if (tem == 1) {
if (!ma[1][0].empty()) {
ma[1][0].erase(ma[1][0].begin());
s[i] = 'a';
continue;
}
if (!ma[1][2].empty() && !ma[2][0].empty()) {
auto x = ma[2][0].upper_bound(*ma[1][2].begin());
if (x != ma[2][0].end()) {
auto y = ma[1][2].lower_bound(*x);
--y;
ma[1][2].erase(y);
ma[2][0].erase(x);
s[i] = 'a';
continue;
}
}
} else if (tem == 2) {
if (!ma[2][0].empty()) {
ma[2][0].erase(ma[2][0].begin());
s[i] = 'a';
continue;
}
if (!ma[2][1].empty() && !ma[1][0].empty()) {
auto x = ma[1][0].upper_bound(*ma[2][1].begin());
if (x != ma[1][0].end()) {
auto y = ma[2][1].lower_bound(*x);
--y;
ma[2][1].erase(y);
ma[1][0].erase(x);
s[i] = 'a';
continue;
}
}
if (!ma[2][1].empty()) {
ma[2][1].erase(ma[2][1].begin());
s[i] = 'b';
continue;
}
}
}
cout << s << endl;
return;
}
|
