# Educational Codeforces Round 92 (CF1389) 题解
# Problem A - LCM Problem (opens new window)
# 题目描述
给定范围(),找出两个数和(),使得。
# 题解
首先,我们有。证明很简单,设,,,显然有,则。
那么就可以贪心地给出答案了,如果,我们可以使用这组答案;否则无解。
时间复杂度。
参考代码(C++)
#include <cstdio>
#include <iostream>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int l, r;
read(l), read(r);
if (r >= l * 2)
printf("%d %d\n", l, l * 2);
else
printf("-1 -1\n");
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
# Problem B - Array Walk (opens new window)
# 题目描述
有到共个位置,从开始,初始分数为,每次可以向左或向右移动,并得到所在位置的分数,但不能连续两次向左移动。总共移动()次,其中至多左移()次。求能够取得的最高分数。
# 题解
我们总可以把最后的总得分分为两部分,一部分是的总分(其中)是最远走到的位置,剩下的则是,其中为第次向左走时所在的位置。假设向左走次,则我们向右的最远距离。另一方面,我们应当在最大的位置来回左右走,这样一定优于在别的位置用掉向左的机会。所以我们可以预计算出的前缀最大值,最后的最高分数就是
其中为前缀和。
时间复杂度。
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int n, k, z;
read(n), read(k), read(z);
vector<int> a(n), s(n + 1), l(n);
for (int i = 0; i < n; ++i) {
read(a[i]), s[i + 1] = s[i] + a[i];
if (i >= 1)
l[i] = max(l[i - 1], a[i] + a[i - 1]);
}
int ans = s[k + 1];
for (int j = 1; j <= z && 2 * j <= k; ++j)
ans = max(ans, l[k + 1 - j * 2] * j + s[k + 1 - j * 2]);
printf("%d\n", ans);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
# Problem C - Good String (opens new window)
# 题目描述
左循环一位和右循环一位得到的字符串相同的字符串称为“好字符串”。问给定字符串至少删去几个字母可以变为“好字符串”?
# 题解
“好字符串”等价于。所以我们可以枚举最后的循环节,然后看原始字符串中最多包含多少个这一循环节。
时间复杂度,其中为字母表中的字母数(本题为)。
参考代码(C++)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
string s;
cin >> s;
int n = s.size();
vector<int> cnt(10);
for (char c : s)
cnt[c - '0']++;
int ans = n - *max_element(cnt.begin(), cnt.end());
for (int i = 0; i < 10; ++i)
for (int j = 0; j < 10; ++j) {
vector<char> t{(char)(i + '0'), (char)(j + '0')};
int tot = 0, idx = 0;
for (char c : s) {
if (c == t[idx]) {
idx++;
if (idx == 2)
tot++, idx = 0;
}
}
ans = min(ans, n - tot * 2);
}
printf("%d\n", ans);
}
};
int main() {
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
# Problem D - Segment Intersections (opens new window)
# 题目描述
最开始有和个。每次可以选择任一区间,将其变为或。定义区间总重叠长度
问最少操作多少次,可以使得?
# 题解
不妨假设(否则交换即可)。
第一种情况是,也即两段初始不相交。这就意味着对于每一对区间,最开始有次操作是不提升总和的。之后有次操作可以以的代价提升总和,再之后需要以的代价提升总和。令。如果,那么我们即使把每一对区间都变成也不够,总需要使用到代价为的操作。否则,假设,我们需要比较对对区间进行操作(激活,再进行代价为的操作),以及对对区间进行操作(激活,进行代价为的操作,剩余次数用代价为的操作完成)。为什么不需要考虑以及更小的值呢?因为激活的花费总小于代价为的操作比起代价为的操作所能够节省的。
第二种情况是,也即两段初始相交,这样就没有激活的代价,之后有次代价为的操作,再之后是代价为的操作。注意有两种特殊情况需要单独考虑:
- ,也即一开始已经满足条件。
- ,此时,只能进行代价为的操作。
对于一般情况,因为没有激活成本,所以一定先用代价为的操作,如果还不够,再用代价为的操作。
时间复杂度。
参考代码(C++)
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int n, k;
read(n), read(k);
int l1, r1, l2, r2;
read(l1), read(r1), read(l2), read(r2);
if (l1 > l2) {
swap(l1, l2);
swap(r1, r2);
}
ll ans;
if (r1 < l2) {
int start = l2 - r1, supply = r2 - l1;
int need = (k - 1) / supply + 1;
if (need > n) {
ans = (ll)n * (start + supply) + 2 * (k - n * supply);
} else {
ans = (ll)need * start + k;
if (need > 1)
ans = min(ans, (ll)(need - 1) * (start + supply) +
(k - (need - 1) * supply) * 2);
}
} else {
ll current = (ll)n * (min(r1, r2) - l2);
if (current >= k) {
ans = 0;
} else {
k -= current;
int supply = l2 - l1 + abs(r2 - r1);
if (supply == 0) {
ans = 2 * k;
} else {
int need = (k - 1) / supply + 1;
if (need <= n)
ans = k;
else
ans = (ll)n * supply + 2 * (k - n * supply);
}
}
}
printf("%lld\n", ans);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
# Problem E - Calendar Ambiguity (opens new window)
# 题目描述
某个国家,一年有个月,每个月有天,每个星期有天()。每年的第一天也一定是星期一(最后一个星期可能是不完整的)。一个数对()被称为“混淆对”,当且仅当月天和月天是一个星期中的同一天。问一共有多少“混淆对”。
# 题解
不妨翻译一下,月天和月天是一个星期中的同一天,其实就是说。
令,则。因为,所以在时,有种取法。不妨假设,我们尝试写出随的变化。
显然可以分组聚合后再进行等差数列求和。
参考代码(C++)
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
class Solution {
public:
void solve() {
int m, d, w;
read(m), read(d), read(w);
if (m == 1 || d == 1) {
printf("0\n");
return;
}
int g = gcd(d - 1, w);
int k = w / g;
int t = min(m, d);
int t0 = t / k * k, t1 = t % k;
ll ans = (ll)t0 * (t0 / k - 1) / 2 + t1 * (t0 / k);
printf("%lld\n", ans);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
# Problem F - Bicolored Segments (opens new window)
待补做。
# Problem G - Directing Edges (opens new window)
待补做。