Decade
CodeForces Round 849
Zhongjun Qiu 元婴开发者
  2025-04-09 22:34:14   2025-04-29 21:27:59    2.2k Words  10 Mins  

A - Codeforces Checking [Easy] 题解

B - Following Directions [Easy] 题解

C - Prepend and Append [Easy] 题解

D - Distinct Split [Easy] 题解

E - Negatives and Positives [Easy] 题解

F - Range Update Point Query [Easy] 题解

G1 - Teleporters (Easy Version) [Medium] 题解

G2 - Teleporters (Hard Version) [Hard] 题解

A - Codeforces Checking

A - Codeforces Checking

就是给你一个字符，判断它是不是在单词“codeforces”里。

思路

暴力

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

代码

1
2
3
def solve():
    x = input()
    print("yes" if x in "codeforces" else "no")

B - Following Directions

B - Following Directions

给你一个字符串表示移动方向，看移动过程中有没有经过点（1， 1）。

思路

数据量很小，直接模拟；到了点（1， 1）就return true。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solve():
    n = int(input())
    s = input()
    x, y = 0, 0
    for i in range(n):
        c = s[i]
        if c == 'U': y += 1
        if c == 'D': y -= 1
        if c == 'L': x -= 1
        if c == 'R': x += 1
        if x == 1 and y == 1:
            print("yes")
            return
    print("no")

C. Prepend and Append

C - Prepend and Append

有一个操作每次可以将字符串头部和尾部加上0、1或1、0。给你一个字符串，返回可以经过任意次操作可得到它的最短字符串。

思路

反向思考，每次操作删去首尾0、1。直到首尾为0、0或1、1或字符串为空。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

代码

1
2
3
4
5
6
def solve():
    n = int(input())
    s = input()
    t = 0
    while t < n//2 and s[t]+s[n-t-1] in '010': t += 1
    print(n-t*2)

D. Distinct Split

D - Distinct Split

让我们把一个字符串x的f(x)函数表示为该字符串包含的不同字符的数量。例如f(abc)=3, f(bbbb)=1和f(babacaba)=3。

给定一个字符串ss，把它分成两个非空字符串a和b，使f(a)+f(b)为最大可能值。换句话说，找出f(a)+f(b)的最大可能值，使a+b=ss。

思路

枚举分割点，分别维护两边不同字符的数量。

考虑到Set比较耗时，可以用两个数组来记录出现不同字符的数目：增加后字符数量为1就+1，删除后字符数量为0就-1。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solve():
    n = int(input())
    s = input()
    a, b, c1, c2, ans = [0]*26, [0]*26, 0, 0, 0
    for x in s:
        i = ord(x)-ord('a')
        b[i] += 1
        if b[i] == 1: c2 += 1
    for x in s:
        i = ord(x)-ord('a')
        a[i] += 1
        if a[i] == 1: c1 += 1
        b[i] -= 1
        if b[i] == 0: c2 -= 1
        ans = max(ans, c1+c2)
    print(ans)

E. Negatives and Positives

E - Negatives and Positives

给定一个由n个元素组成的数组a，求该数组在执行以下任意次数的操作后可能具有的最大和。

选择2个相邻的元素，翻转它们的符号。换句话说，选择一个索引i，使1≤i≤n-1，并指定ai=-ai，ai+1=-ai+1。

思路

一眼看去像是贪心，但不敢贪😅；这题动态规划思路很好像，还是老老实实DP。

对于每个数而言，只有两种可能情况：翻转和不翻转（和背包问题很像，可以看看这篇文章这篇文章）。

于是定义dp[i][0]:不翻转第i个数可以得到的最大值 dp[i][1]翻转第i个数可以得到的最大值:

递推：不反转就直接把第i个数和前面可以得到的最大值相加；否则第i个数和第i-1个数也要翻转。

dp[i-1][0]表示i-1个数没有翻转，此时dp[i-1][0]-a[i-1]就是前i-2个数最大值，再减去a[i-1]和a[i]就行。

dp[i-1][1]表示i-1个数没有翻转，此时dp[i-1][0]+a[i-1]就是前i-2个数最大值，再减去-a[i-1]和a[i]就行。（因为此时啊a[i-1]翻转过了，变成了-a[i-1]）

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

代码

1
2
3
4
5
6
7
8
9
def solve(): 
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[0]*2 for i in range(n+1)]
    dp[1][0], dp[1][1] = a[0], int(-1e18)
    for i in range(2, n+1):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])+a[i-1]
        dp[i][1] = max(dp[i-1][0]-2*a[i-2], dp[i-1][1]+2*a[i-2])-a[i-1]
    print(max(dp[n][0], dp[n][1]))

Tips

dp[1][0], dp[1][1] = a[0], int(-1e18) 初始化要思考下。

单独翻转第一个数是不可能的，所以要设置为无穷小。（比可能的最小值小就行了，一开始写成-1e9，怒wa）

F. Range Update Point Query

F - Range Update Point Query

给定一个数组a1,a2,……,an，你需要处理两类共计q的更新和查询。

1 l r - 对于每个有l≤i≤r的索引i，将ai的值更新为ai的各个位数上的数字之和。

2 x - 输出a[x]。

思路

看到题干，一眼线段树。但这题只涉及区间修改和单点查询，用树状数组更简单。两种数据结构详见数据结构

还要注意所有可能的数最多更新三次就不会变了。

  • 时间复杂度：O(nlog n)
  • 空间复杂度：O(n)

代码

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
static int n, m, a[] = new int[N], tr[] = new int[N];
static void add(int x, int v){
    for (int i = x;i <= n;i += i&-i) tr[i] += v;
}
static int sum(int x){
    int res = 0;
    for (int i = x;i > 0;i -= i&-i) res += tr[i];
    return res;
}
static int get(int t, int cnt){
    while (cnt != 0 && t > 9){
        int tp = 0;
        while (t != 0){
            tp += t%10;
            t /= 10;
        } t = tp;
        cnt--;
    }return t;
}
static void solve() throws Exception{
    n = ni(); m = ni();
    Arrays.fill(a, 0); Arrays.fill(tr, 0);
    for (int i = 1;i <= n;i++) a[i] = ni();
    for (int i = 0;i < m;i++){
        int op = ni();
        if (op == 1){
            int l = ni(), r = ni();
            add(l, 1); add(r+1, -1);
        }else{
            int t = ni();
            out.println(get(a[t], sum(t)));
        }
    }
}

Tips

多组测试用例的题目，对于全局变量一定要初始化！！！

即Arrays.fill(a, 0); Arrays.fill(tr, 0);，不然会死的很惨。

G1. Teleporters (Easy Version)

G1 - Teleporters (Easy Version)

考虑到数线上的点0,1,…,n。在每一个点1,2,…,n上有一个传送器。在i点，你可以做以下事情。

  • 向左移动一个单位：花费1枚硬币。

  • 向右移动一个单位：需要花费1个硬币。

  • 在第i点使用一个传送器，如果它存在的话：它需要花费ai硬币。结果，你会被传送到0点。

  • 一旦你使用了一个传送器，你就不能再使用它了。

你有c硬币，你从0点开始。你最多可以使用多少个传送器？

思路

可以发现，每次到一个点传送后都回到原点。即到达每个点使用传送器的总消耗是独立的，等于 到该点的花费+该店使用传送的花费。

即预处理所有点的花费，从小到大排序，看最多能支持几次。（其实可以前缀和+二分，但懒😅）

  • 时间复杂度：O(nlog n)
  • 空间复杂度：O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
def solve(): 
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    cost = [i+1+a[i] for i in range(n)]
    cost.sort()
    ans, s = 0, 0
    for i in cost:
        s += i
        if s <= m:
            ans += 1
        else: break
    print(ans)

G2. Teleporters (Hard Version)

G2 - Teleporters (Hard Version)

与EASY版本不同的是使用传送后，可以回到点0，也可以回到点n+1。

思路

与EASY版本一样，如果我们不考虑第一个去的点，问题对每个点来说仍然是独立的，但这一次门户的成本是min(a[i]+i,a[i]+n+1-i)（因为我们可以从0点或n+1点来到一个门户）。因此，我们再次按成本对传送门进行排序。但是这一次，我们需要确保第一个拿下的传送门是从0点去的，所以我们将遍历所有的点，并检查如果我们把它作为第一个传送门，我们能拿下的最大传送门数量。

这里就需要用二分找到每次可以去的点的最大值。（与常规二分不同，需要单独对当前遍历到的点处理）

  • 时间复杂度：O(nlog n)
  • 空间复杂度：O(n)

代码

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
static int n, c;
static long a[] = new long[N], cost[][] = new long[N][2];
static void solve() throws Exception{
    n = ni(); c = ni();
    Arrays.fill(a, 0);
    for (int i = 1;i <= n;i++) cost[i] = new long[]{0, 0};
    for (int i = 1;i <= n;i++) a[i] = ni();
    for (int i = 1;i <= n;i++){
        cost[i][0] = min(i+a[i], n-i+1+a[i]);
        cost[i][1] = i;
    }
    Arrays.sort(cost, 1, n+1, (x,y)->Long.compare(x[0], y[0]));
    for (int i = 1;i <= n;i++) cost[i][0] += cost[i-1][0];
    int ans = 0;
    for (int i = 1;i <= n;i++){
        int l = 1, r = n, dx = i;
        long first = cost[i][1]+a[(int)cost[i][1]];
        if (first > c) continue;
        while (l <= r){
            int m = l+r >> 1;
            long cur = cost[m][0];
            if (m < dx) cur += first;
            else cur += first-cost[dx][0]+cost[dx-1][0];
            if (cur <= c) l = m+1;
            else r = m-1;
        }
        ans = max(ans, r<dx?r+1:r);
    }out.println(ans);
}
CodeForces Round 849
2025/04/09/CodeForces-Round-849/
Author
Zhongjun Qiu
Published
2025-04-09 22:34
License
 REWARD AUTHOR
 Comments
Comment plugin failed to load
Loading comment plugin
  1. A - Codeforces Checking
    1. 思路
    2. 代码
  2. B - Following Directions
    1. 思路
    2. 代码
  3. C. Prepend and Append
    1. 思路
    2. 代码
  4. D. Distinct Split
    1. 思路
    2. 代码
  5. E. Negatives and Positives
    1. 思路
    2. 代码
    3. Tips
  6. F. Range Update Point Query
    1. 思路
    2. 代码
    3. Tips
  7. G1. Teleporters (Easy Version)
    1. 思路
    2. 代码
  8. G2. Teleporters (Hard Version)
    1. 思路
    2. 代码
  1. A - Codeforces Checking
    1. 思路
    2. 代码
  2. B - Following Directions
    1. 思路
    2. 代码
  3. C. Prepend and Append
    1. 思路
    2. 代码
  4. D. Distinct Split
    1. 思路
    2. 代码
  5. E. Negatives and Positives
    1. 思路
    2. 代码
    3. Tips
  6. F. Range Update Point Query
    1. 思路
    2. 代码
    3. Tips
  7. G1. Teleporters (Easy Version)
    1. 思路
    2. 代码
  8. G2. Teleporters (Hard Version)
    1. 思路
    2. 代码