A - Line Breaks
Info
科斯佳有一个由 $n$ 个拉丁字母组成的文字 $s$ 。他还必须在两张纸条上书写文字。第一张纸条可以容纳 $m$ 个字符，而第二张纸条可以容纳尽可能多的字符。
科斯佳必须选择一个数字 $x$ ，并在第一条上写下 $s$ 中的第一个 $x$ 字，而其余所有字都写在第二条上。为了节省空间，这些单词的书写没有间隙，但每个单词必须完全写在一张纸条上。
由于第二条上的空间非常宝贵，科斯佳要求您选择最大可能的数字 $x$ ，使所有单词 $s_1, s_2, \dots, s_x$ 都能写在长度为 $m$ 的第一条上。
科斯佳有一个由 $n$ 个拉丁字母组成的文字 $s$ 。他还必须在两条长条上书写文字。第一张纸条可以容纳 $m$ 个字符，而第二张纸条可以容纳尽可能多的字符。科斯佳必须选择一个数字 $x$ ，并在第一条上写下 $s$ 中的第一个 $x$ 字，而其余所有字都写在第二条上。为了节省空间，单词的书写是没有间隙的，但每个单词必须完全写在一个条带上。由于第二条上的空间非常宝贵，科斯佳要求您选择最大可能的数字 $x$ ，使所有单词 $s_1, s_2, \dots, s_x$ 都能写在长度为 $m$ 的第一条上。
Solution
读入字符串数组排序后取前几个就行。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void solve() {
int n, m;
cin >> n >> m;
std::vector<int> vec(n);
for (int i = 0; i < n; i ++) {
std::string s;
cin >> s;
vec[i] = s.length();
}
int l = 0;
int i;
for (i = 0; i < n; i ++) {
l += vec[i];
if (l > m)
break;
}
cout << i << "\n";
}
|
B - Transfusion
Info
给你一个长度为 $n$ 的数组 $a$ 。在一次操作中，你可以从 $2$ 到 $n-1$ （含）之间选取索引 $i$ ，并执行以下操作之一：
- 将 $a_{i-1}$ 减少 $1$ ，然后将 $a_{i+1}$ 增加 $1$ 。
- 将 $a_{i+1}$ 减少 $1$ ，然后将 $a_{i-1}$ 增加 $1$ 。
每次运算后，所有数值都必须为非负。你能在任意多次运算后使所有元素相等吗？
Solution
我们经过观察可以发现一个重要的性质：即奇数位上的数字可以和奇数位上的数字转移，偶数位上的数字可以和偶数位上的数字转移。因此我们可以把奇数位上的数字偶数位上的数字想象成两个不同的数组。为了使所有元素相等，我们首先让数组各自内部相等，然后再检查两个数组相等后的值是否一致就行。
Code
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;
cin >> n;
std::vector<int> a(n + 1);
long long s1 = 0, s2 = 0;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
if (i % 2)
s1 += a[i];
else
s2 += a[i];
}
long long n1 = (n + 1) / 2, n2 = n / 2;
long long a1 = s1 / n1, a2 = s2 / n2;
if (a1 != a2) {
cout << "NO\n";
return;
}
if (a1 * n1 != s1 or a2 * n2 != s2) {
cout << "NO\n";
return;
}
cout << "YES\n";
}
|
C - Unintersting Number
Info
给你一个长度不超过 $10^5$ 的数字 $n$ 。
你可以多次进行以下运算：选择其中一位数字，将其平方，然后用运算结果替换原来的数字。结果必须是一位数字（也就是说，如果您选择数字 $x$ ，那么 $x^2$ 的值必须小于 $10$ ）。
通过这些运算，有可能得到一个能被 $9$ 整除的数吗？
Solution
考虑到我们只能选择数字 $3$ 或 $2$（因为其他的数字的平方要么等于它本身，要么大于十）。我们注意到 $10 \mod 9 = 1$，因此整个数对于 $9$ 的余数就会等于
每一位数字关于 $9$ 的余数的和。（让我想起了 2024 江西省赛的 G 题）。
然后枚举即可。
Code
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
|
void solve() {
// 2 -> 4 or 3 -> 9
// delta 2 -> 4 = +2
// delta 3 -> 9 = -3
std::string s;
int n2 = 0, n3 = 0;
cin >> s;
int sum = 0;
for (int i = 0; i < s.size(); i ++) {
if (s[i] == '2')
n2 ++;
if (s[i] == '3')
n3 ++;
if (s[i] == '9')
continue;
sum += s[i] - '0';
}
if (!(sum % 9)) {
cout << "YES\n";
return;
}
int d = sum % 9;
for (int i = 0; i <= n2; i ++) {
for (int j = 0; j <= n3; j ++) {
if (!((d + 2 * i - 3 * j) % 9)) {
cout << "YES\n";
return;
}
}
}
cout << "NO\n";
}
|
D - Digital string maximization
Info
给你一个字符串 $s$ ，由从 $0$ 到 $9$ 的数字组成。在一次运算中，您可以选取该字符串中除 $0$ 或最左边数字之外的任意一个数字，将其减少 $1$ ，然后将其与左边的数字对调。
例如，从字符串 $1023$ 中进行一次运算，可以得到 $1103$ 或 $1022$ 。
找出经过任意多次运算后可以得到字典序最大的字符串。
Solution
因为考虑到数字最多移动 $10$ 次，所以我们完全可以写一个暴力模拟。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void solve() {
std::string s;
cin >> s;
int n = 100;
while (true) {
int cnt = 0;
for (int i = 0; i < s.length(); i ++) {
for (int j = i + 1; j < i + 10 and j < s.length(); j ++) {
if (s[j] - 1 > s[j - 1]) {
cnt ++;
s[j] -= 1;
std::swap(s[j], s[j - 1]);
} else {
break;
}
}
}
if (!cnt)
break;
}
cout << s << "\n";
}
|
E - Three Strings
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void solve() {
std::string a, b, c;
cin >> a >> b >> c;
int la = a.length(), lb = b.length(), lc = c.length();
std::vector<std::vector<int>> dp(la + 1, std::vector<int>(lb + 1, 0x7f7f7f7f));
dp[0][0] = 0;
for (int i = 0; i < la; i ++) {
dp[i + 1][0] = dp[i][0] + (a[i] != c[i]);
}
for (int i = 0; i < lb; i ++) {
dp[0][i + 1] = dp[0][i] + (b[i] != c[i]);
}
for (int i = 1; i <= la; i ++) {
for (int j = 1; j <= lb; j ++) {
dp[i][j] = std::min(dp[i - 1][j] + (a[i - 1] != c[i + j - 1]), dp[i][j - 1] + (b[j - 1] != c[i + j - 1]));
}
}
cout << dp[la][lb] << "\n";
}
|
F - Maximum modulo equality
Code
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
|
struct node {
int value = 0;
int lazy = 0;
int l = 0;
int m = 0;
int r = 0;
node* left = nullptr;
node* right = nullptr;
node(int v, int a, int b) {
value = v;
l = a;
r = b;
m = l + ((r - l) >> 1);
}
int gcd(int a, int b) {
if (a <= l and r <= b)
return value;
int p = 0;
if (a <= m)
p = std::gcd(p, left->gcd(a, b));
if (b > m)
p = std::gcd(p, right->gcd(a, b));
return p;
}
};
node* build(std::vector<int> &arr, int l, int r) {
if (l == r) {
return new node(arr[l], l, r);
}
node* p = new node(0, l, r);
p->left = build(arr, l, p->m);
p->right = build(arr, p->m + 1, r);
p->value = std::gcd(p->left->value, p->right->value);
return p;
}
void solve() {
int n, q;
cin >> n >> q;
std::vector<int> a(n + 1);
std::vector<int> d(n + 1);
a[0] = 0;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
d[i] = std::abs(a[i] - a[i - 1]);
}
node* root = build(d, 1, n);
while (q --) {
int l, r;
cin >> l >> r;
if (l == r) {
cout << "0 ";
continue;
}
cout << root->gcd(l + 1, r) << " ";
}
cout << "\n";
}
|
G - Tree Destruction
Code
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
|
void dfs(int v, int p, std::vector<std::vector<int>> &vec, std::vector<std::pair<int, int>> &dp) {
dp[v].first = vec[v].size();
int m1 = -1, m2 = -1;
for (int u : vec[v]) {
if (u == p) {
continue;
}
dfs(u, v, vec, dp);
dp[v].first = std::max(dp[v].first, dp[u].first + (int)vec[v].size() - 2);
m2 = std::max(m2, dp[u].first);
if (m1 < m2)
std::swap(m1, m2);
}
dp[v].second = dp[v].first;
if (m2 != -1) {
dp[v].second = m1 + m2 + vec[v].size() - 4;
}
}
void solve() {
int n;
std::cin >> n;
std::vector<std::vector<int>> vec(n + 1);
for (int i = 1; i < n; i ++) {
int u, v;
std::cin >> u >> v;
vec[u].push_back(v);
vec[v].push_back(u);
}
std::vector<std::pair<int, int>> dp(n + 1);
dfs(1, 1, vec, dp);
int ans = 0;
for (int i = 1; i <= n; i ++) {
ans = std::max(ans, std::max(dp[i].first, dp[i].second));
}
std::cout << ans << "\n";
}
|