# Codeforces Round 667 (CF1409) 题解

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

# 题目描述

初始有两个数aabb,每次可以选择其中一个,加上或减去[1,10][1,10]中的任意一个数,问至少多少次操作后能让a=ba=b

# 题解

签到题。显然差距大于等于1010的时候应该尽量用1010,所以ans=ab10ans=\left\lceil\frac{|a-b|}{10}\right\rceil

时间复杂度O(1)O(1)

参考代码(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))
1
2
3
4
5
6
7
8
9
10
11
12
13

# Problem B - Minimum Product (opens new window)

# 题目描述

给定axa\geq x以及byb\geq y,每次可以将aabb减去11,但需要保持axa\geq xbyb\geq y始终成立。最多操作nn次后,所能得到的最小的aba\cdot b是多少?

# 题解

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

时间复杂度O(1)O(1)

参考代码(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)
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)

# 题目描述

给定正整数x<yx<y,要求构造一个同时包含x,yx,y,总共nn项且均为正整数的等差数列,并且这个等差数列的最大值最小。

# 题解

假设这个等差数列的公差d>0d>0,显然有yx=kdy-x=kd,其中1kn11\leq k\leq n-1,因此yx0modky-x\equiv0\mod k

不妨从大到小枚举kk(这样等于是从小到大枚举dd)。当我们找到第一个能够整除yxy-xkk时,就得到了满足条件的最小的dd。可以证明,此时的等差数列最大值就是我们要求的最小结果。

假设d=d0d=d_0时小于xx的最多安排mm项,则d>d0d>d_0时小于xx的至多安排mm项(如果d>d0d>d_0能安排m+1m+1项,d=d0d=d_0至少也能安排m+1m+1项)。d=d0d=d_0时大于xx的一共nm1n-m-1项,因此最大值为x+(nm1)d0x+(n-m-1)d_0。而在d>d0d>d_0时,大于xx的至少nm1n-m-1项,从而最大值大于等于x+(nm1)d>x+(nm1)d0x+(n-m-1)d>x+(n-m-1)d_0

时间复杂度O(n)O(n)

参考代码(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
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)

# 题目描述

给定一个数nn,每次操作可以使nn11,问至少多少次操作后,可以使nn的各位数字之和不超过ss

# 题解

显然要使数位和减小,必须将数字变成00。因为要求最少操作次数,所以我们从最后一位开始,逐步尝试修改。每次修改后需要将前一位加11,如果有进位,还需要处理进位问题。在整个过程中,我们不断更新当前的数位和。当数位和第一次满足要求时,我们就找到了答案。

时间复杂度O(log10n)O(\log_{10}n)

参考代码(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)
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)

# 题目描述

二维空间中有nn个点,每个点的坐标为(xi,yi)(x_i,y_i)。现在你可以设置两个平台,每个平台的宽度为kk,要求平台平行于xx轴设置。问至多能接到多少个小球。

# 题解

首先,平台可以放在y=y=-\infty处,所以点的yy值并不需要考虑。

两个平台显然不应该有重叠部分,因为我们总可以固定其中一个,然后将另一个向旁边移动使得它们不重叠,并且总共接到的小球数只会增加而不会减少。

另一方面,我们总可以将平台的起点设置在某一个小球对应的xx处。因为如果平台的起点xsx_s没有小球,我们总可以将平台向右移动,直到遇到一个小球,而总共接到的小球数只会增加而不会减少。

所以,我们可以对xx进行排序,然后用双指针求出从第ii位开始放一个平台所能够得到的最大小球数L[i]L[i]。得到L[i]L[i]后,我们再得到后缀最大值R[i]R[i],也即从ii位及之后位置开始放一个平台所能够得到的最大小球数。

最后,我们的答案就是max(L[i]+R[i+L[i]])\max(L[i]+R[i+L[i]])

时间复杂度O(nlogn)O(n\log n),瓶颈是排序。

参考代码(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();
  }
}
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)

# 题目描述

给定字符串ss和一个长度为22的字符串tt,至多对ss进行KK次修改,每次修改可以将任意位置的字母替换为任意其他字母。问修改后的字符串,最多包含多少个与tt相同的子序列?

# 题解

首先,如果tt的两个字母相同(假设都为aa),我们可以单独处理,直接将ss中所有非aa字母都尽可能改为aa即可,假设最后可以得到mmaa,那么最后的答案就是m(m1)2\frac{m(m-1)}{2}

如果tt的两个字母不同(设为aabb),我们可以进行动态规划。令dp[i][j][k]dp[i][j][k]表示前ii位有jjaa,用了kk次修改可以得到的最大子序列数目。对于下一位,我们可以讨论是否将其修改为bb和是否将其修改为aa,从而对状态进行转移。因为dp[i+1]dp[i+1]只与dp[i]dp[i]有关,所以可以用滚动数组优化空间。

时间复杂度O(s2k)O(|s|^2k)

参考代码(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();
}
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