# # Educational Codeforces Round 92 (CF1389) 题解

## # Problem A - LCM Problem (opens new window)

### # 题解

#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;
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;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem B - Array Walk (opens new window)

### # 题目描述

$1$$N$$N$个位置，从$1$开始，初始分数为$a_1$，每次可以向左或向右移动，并得到所在位置的分数，但不能连续两次向左移动。总共移动$k$$1\leq k\leq N-1$）次，其中至多左移$z$$0\leq z\leq\min(5,k)$）次。求能够取得的最高分数。

### # 题解

$\max_{x=0}^z(L_{k+1-2x}\cdot x+S_{k+1-2x})$

#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;
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;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem C - Good String (opens new window)

### # 题解

“好字符串”等价于$\forall i, s_i=s_{i+2}$。所以我们可以枚举最后的循环节，然后看原始字符串中最多包含多少个这一循环节。

#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;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem D - Segment Intersections (opens new window)

### # 题目描述

$I=\sum_{i=1}^n intersection([al_i,ar_i],[bl_i,br_i])$

### # 题解

• $I_0\geq k$，也即一开始已经满足条件。
• $l_1=r_1,l_2=r_2$，此时$l_2-l_1+|r_2-r_1|=0$，只能进行代价为$2$的操作。

#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;
int l1, r1, l2, 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;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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

## # Problem E - Calendar Ambiguity (opens new window)

### # 题解

$GCD(w,d-1)=g$，则$y-x\equiv0\mod\frac{w}{g}$。因为$x，所以在$y=y_i$时，$x$$\left\lfloor\frac{y_i-1}{w/g}\right\rfloor$种取法。不妨假设$\frac{w}{g}=3$，我们尝试写出$\left\lfloor\frac{y_i-1}{w/g}\right\rfloor$$y_i$的变化。

$y_i=1,2,3,4,5,6,7,8,9,10,\cdots$

$\left\lfloor\frac{y_i-1}{w/g}\right\rfloor=0,0,0,1,1,1,2,2,2,3,\cdots$

#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;
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;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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