# # Codeforces Round 667 (CF1409) 题解

## # Problem A - Yet Another Two Integers Problem (opens new window)

### # 题解

def read_int():
return int(input())

return map(int, input().split(' '))

for case_num in range(t):
delta = abs(a - b)
print(delta // 10 + (1 if delta % 10 != 0 else 0))

1
2
3
4
5
6
7
8
9
10
11
12
13

## # Problem B - Minimum Product (opens new window)

### # 题解

$a时，我们一定有$(a-1)b，所以我们应当尽可能减小一个数，如果还有操作机会，再去减小另一个数。分别考虑一下先减小$a$和先减小$b$的情况即可。

import sys

for case_num in range(t):
a, b, x, y, n = read_ints()
n1 = min(n, a - x)
ans = (a - n1) * (b - min(n - n1, b - y))
n2 = min(n, b - y)
ans = min(ans, (b - n2) * (a - min(n - n2, a - x)))
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

## # Problem C - Yet Another Array Restoration (opens new window)

### # 题解

def read_int():
return int(input())

return map(int, input().split(' '))

for case_num in range(t):
d = y - x
for i in range(n - 1, 0, -1):
if d % i == 0:
d //= i
l = min(n - (i + 1), (x - 1) // d)
ans = [x - l * d + i * d for i in range(n)]
print(' '.join(map(str, ans)))
break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

## # Problem D - Decrease the Sum of Digits (opens new window)

### # 题解

import sys

for case_num in range(t):
a = [0] + [int(i) for i in str(n)]
ds = sum(a)
cost = 0
idx = len(a) - 1
while ds > s:
if a[idx] > 0:
cost += (10 - a[idx]) * radix
ds -= a[idx]
a[idx] = 0
ds += 1
a[idx - 1] += 1
i = idx - 1
while a[i] >= 10:
a[i - 1] += 1
a[i] -= 10
ds -= 9
i -= 1
idx -= 1
print(cost)

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

## # Problem E - Two Platforms (opens new window)

### # 题解

#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() {
int n, k;
vector<int> x(n), y(n);
for (int i = 0; i < n; ++i)
for (int i = 0; i < n; ++i)
sort(x.begin(), x.end());
vector<int> L(n + 1), R(n + 1);
int r = 0;
for (int l = 0; l < n; ++l) {
while (r + 1 < n && x[r + 1] <= x[l] + k)
r++;
R[l] = L[l] = r - l + 1;
}
for (int i = n - 1; i >= 0; --i)
R[i] = max(R[i], R[i + 1]);
int ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, L[i] + R[i + L[i]]);
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
46
47
48
49
50
51
52
53
54
55

## # Problem F - Subsequences of Length Two (opens new window)

### # 题解

#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;
string s, t;
cin >> s >> t;
if (t[0] == t[1]) {
int cnt = 0;
for (char c : s)
cnt += c == t[0];
int hi = min(n, cnt + k);
printf("%d", hi * (hi - 1) / 2);
} else {
char a = t[0], b = t[1];
vector<vector<int>> g(n + 1, vector<int>(k + 1, -1));
g[0][0] = 0;
for (int i = 0; i < n; ++i) {
vector<vector<int>> ng(g);
for (int j = 0; j <= i; ++j)
for (int p = 0; p <= k; ++p) {
if (g[j][p] == -1)
continue;

// Set to b
if (s[i] == b)
ng[j][p] = max(ng[j][p], g[j][p] + j);
else if (p < k)
ng[j][p + 1] = max(ng[j][p + 1], g[j][p] + j);

// Set to a
if (s[i] == a)
ng[j + 1][p] = max(ng[j + 1][p], g[j][p]);
else if (p < k)
ng[j + 1][p + 1] = max(ng[j + 1][p + 1], g[j][p]);
}
g = move(ng);
}
int ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= k; ++j)
ans = max(ans, g[i][j]);
printf("%d", ans);
}
}
};

int main() {
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