# Codeforces Round 667 (CF1409) 题解
# Problem A - Yet Another Two Integers Problem (opens new window)
# 题目描述
初始有两个数和,每次可以选择其中一个,加上或减去中的任意一个数,问至少多少次操作后能让。
# 题解
签到题。显然差距大于等于的时候应该尽量用,所以。
时间复杂度。
参考代码(Python 3)
def read_int():
return int(input())
def read_ints():
return map(int, input().split(' '))
t = read_int()
for case_num in range(t):
a, b = read_ints()
delta = abs(a - b)
print(delta // 10 + (1 if delta % 10 != 0 else 0))
2
3
4
5
6
7
8
9
10
11
12
13
# Problem B - Minimum Product (opens new window)
# 题目描述
给定以及,每次可以将或减去,但需要保持和始终成立。最多操作次后,所能得到的最小的是多少?
# 题解
在时,我们一定有,所以我们应当尽可能减小一个数,如果还有操作机会,再去减小另一个数。分别考虑一下先减小和先减小的情况即可。
时间复杂度。
参考代码(Python 3)
import sys
def read_int():
return int(sys.stdin.readline())
def read_ints():
return map(int, sys.stdin.readline().split(' '))
t = read_int()
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)
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)
# 题目描述
给定正整数,要求构造一个同时包含,总共项且均为正整数的等差数列,并且这个等差数列的最大值最小。
# 题解
假设这个等差数列的公差,显然有,其中,因此。
不妨从大到小枚举(这样等于是从小到大枚举)。当我们找到第一个能够整除的时,就得到了满足条件的最小的。可以证明,此时的等差数列最大值就是我们要求的最小结果。
假设时小于的最多安排项,则时小于的至多安排项(如果能安排项,至少也能安排项)。时大于的一共项,因此最大值为。而在时,大于的至少项,从而最大值大于等于。
时间复杂度。
参考代码(Python 3)
def read_int():
return int(input())
def read_ints():
return map(int, input().split(' '))
t = read_int()
for case_num in range(t):
n, x, y = read_ints()
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
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)
# 题目描述
给定一个数,每次操作可以使加,问至少多少次操作后,可以使的各位数字之和不超过。
# 题解
显然要使数位和减小,必须将数字变成。因为要求最少操作次数,所以我们从最后一位开始,逐步尝试修改。每次修改后需要将前一位加,如果有进位,还需要处理进位问题。在整个过程中,我们不断更新当前的数位和。当数位和第一次满足要求时,我们就找到了答案。
时间复杂度。
参考代码(Python 3)
import sys
def read_int():
return int(sys.stdin.readline())
def read_ints():
return map(int, sys.stdin.readline().split(' '))
t = read_int()
for case_num in range(t):
n, s = read_ints()
a = [0] + [int(i) for i in str(n)]
ds = sum(a)
cost = 0
idx = len(a) - 1
radix = 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
radix *= 10
idx -= 1
print(cost)
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)
# 题目描述
二维空间中有个点,每个点的坐标为。现在你可以设置两个平台,每个平台的宽度为,要求平台平行于轴设置。问至多能接到多少个小球。
# 题解
首先,平台可以放在处,所以点的值并不需要考虑。
两个平台显然不应该有重叠部分,因为我们总可以固定其中一个,然后将另一个向旁边移动使得它们不重叠,并且总共接到的小球数只会增加而不会减少。
另一方面,我们总可以将平台的起点设置在某一个小球对应的处。因为如果平台的起点没有小球,我们总可以将平台向右移动,直到遇到一个小球,而总共接到的小球数只会增加而不会减少。
所以,我们可以对进行排序,然后用双指针求出从第位开始放一个平台所能够得到的最大小球数。得到后,我们再得到后缀最大值,也即从位及之后位置开始放一个平台所能够得到的最大小球数。
最后,我们的答案就是。
时间复杂度,瓶颈是排序。
参考代码(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() {
int n, k;
read(n), read(k);
vector<int> x(n), y(n);
for (int i = 0; i < n; ++i)
read(x[i]);
for (int i = 0; i < n; ++i)
read(y[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;
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
# Problem F - Subsequences of Length Two (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;
read(n), read(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();
}
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