Blog - Floating Ocean
0%

Codeforces - Round 849 Div 4

发表于 更新于
本文字数： 7.5k 阅读时长 ≈ 14 分钟
阅读次数： Valine：

Contestant. Rank 3392. Rating -15.

代码略去了快读模板

A. Codeforces Checking

题意

给定一个字符，判断是否在 字符串中出现。

思路

数组记录 + 读数组。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        boolean[] have = new boolean[26];
        for(char each : "codeforces".toCharArray()) have[each - 'a'] = true;
        while(t -- > 0){
            console.println(have[console.next().toCharArray()[0] - 'a'] ? "YES" : "NO");
        }
        console.close();
    }

}

语法题 x1

B. Following Directions

题意

给定一个由 组成的字符串，分别代表向上、下、左、右移动一个单位距离。输出从原点开始移动，途中是否经过 。

思路

模拟。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt();
            String step = console.next();
            int x = 0, y = 0;
            for(char each : step.toCharArray()){
                if(each == 'L') x --;
                else if(each == 'R') x ++;
                else if(each == 'U') y ++;
                else y --;
                if(x == 1 && y == 1){
                    console.println("YES");
                    continue nxt;
                }
            }
            console.println("NO");
        }
        console.close();
    }
}

语法题 x2

C. Prepend and Append

题意

给定一个二进制字符串，定义操作为在字符串左端拼接上 并在右端拼接上 ，或者在字符串左端拼接上 并在右端拼接上 。给定的字符串为一个原字符串经过多次操作后得到的。输出最小的原字符串。

思路

遍历，找到第一个位置，满足两端的值相同。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt();
            String in = console.next();
            int cnt = 0;
            for(int i=0;i<n/2;i++){
                if((in.charAt(i) == '0' && in.charAt(n - i - 1) == '1') || (in.charAt(i) == '1' && in.charAt(n - i - 1) == '0')) cnt ++;
                else break;
            }
            console.println(n - cnt * 2);
        }
        console.close();
    }
}

签到题 x3

D. Distinct Split

题意

给定一个字符串，将字符串分割为两个字符串，第一个字符串中不同字母的数量和第二个字符串中不同字母的数量之和最大，并输出这个最大值。

思路

维护一个前缀不同字母数量和后缀不同字母数量，然后枚举每一位，求 的最大值。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt();
            char[] s = console.next().toCharArray();
            boolean[] ok1 = new boolean[26], ok2 = new boolean[26];
            int[] pre = new int[n + 2], suf = new int[n + 2];
            for(int i=1;i<=n;i++){
                char e = s[i - 1];
                pre[i] = pre[i - 1];
                if(!ok1[e - 'a']) pre[i] ++;
                ok1[e - 'a'] = true;
            }
            for(int i=n;i>=1;i--){
                char e = s[i - 1];
                suf[i] = suf[i + 1];
                if(!ok2[e - 'a']) suf[i] ++;
                ok2[e - 'a'] = true;
            }
            int ans = 0;
            for(int i=0;i<n;i++){
                ans = Math.max(ans, pre[i] + suf[i + 1]);
            }
            console.println(ans);
        }
        console.close();
    }
}

略微有点不签到起来了（（

E. Negatives and Positives

题意

给定一个数组 ，定义操作为选两个相邻的元素并将它们都取相反数。输出任意次操作后数组的总和的最大值。

思路

首先，因为操作数量不限制，我们不妨来考虑选几个连续的相邻元素。

举个例子，如 ，我们从第一位开始操作到倒数第二位，操作看起来是这样的：

显然，只要是连续的操作，那么每次操作等效于移动负号的位置。

或者，换句话说，我们完全不需要考虑 “相邻” 这个条件，跳着操作是完全可行的。

那么，我们只需升序排序，然后将负数一对一对取反。

当然，若负数的数量为奇数，那么对于最后剩余的那个奇数，我们只需将其和最小的非负数比较绝对值即可。若负数的绝对值较大，那么直接把负数和最小非负数的符号交换一下即可。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt();
            long[] a = new long[n];
            long sum = 0;
            int cnt = 0;
            for(int i=0;i<n;i++){
                int cur = console.nextInt();
                sum += cur;
                a[i] = cur;
                if(a[i] < 0) cnt ++;
            }
            Arrays.sort(a);
            for(int i=0;i<cnt/2*2;i++) sum -= 2 * a[i];
            if(cnt % 2 == 1){
                int p = cnt / 2 * 2;
                if(p + 1 < n){
                    if(-a[p] > a[p + 1]){
                        sum -= 2 * a[p];
                        sum -= 2 * a[p + 1];
                    }
                }
            }
            console.println(sum);
        }
        console.close();
    }
}

简单思维题，但是也可以dp~

F. Range Update Point Query

题意

给定一个数组 以及 个询问，询问为下列情况任选其一：

  1. 给定 ，将 内的所有数更新为每个数 十进制下每一位的和；
  2. 给定 ，输出 。

输出询问所要求的内容。

思路

首先，询问 的操作具有收敛性，在 的范围内，第一次操作后的最大值只有 ，那么我们不难发现，对于一个数，我们最多只能操作 次，超过 次后值一定不变。

我们定义一个数组 ， 表示第 位已经操作了多少遍。

因而，我们只需考虑一个问题：怎么让区间更新和单点查询效率更高呢？

没错，就是线段树。

不难发现，我们只需套上线段树的板子，然后略微修改即可。

时间复杂度：不会分析

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, a[200005][4], d[600000], b[600000];

void update(int l, int r, int c, int s, int t, int p) {
    if (l <= s && t <= r) {
        d[p] += (t - s + 1) * c, b[p] += c;  // 如果区间被包含了，直接得出答案
        return;
    }
    int m = s + ((t - s) >> 1);
    if (b[p])
        d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
        b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
    b[p] = 0;
    if (l <= m)
        update(l, r, c, s, m, p << 1);  // 本行和下面的一行用来更新p*2和p*2+1的节点
    if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
    d[p] = d[p << 1] + d[(p << 1) | 1];  // 计算该节点区间和
}

int getsum(int l, int r, int s, int t, int p) {
    if (l <= s && t <= r) return d[p];
    int m = s + ((t - s) >> 1);
    if (b[p])
        d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
        b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
    b[p] = 0;
    int sum = 0;
    if (l <= m)
        sum =getsum(l, r, s, m, p << 1);  // 本行和下面的一行用来更新p*2和p*2+1的答案
    if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);
    return sum;
}

signed main() {
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while(t --) {
        memset(a, 0, sizeof a);
        memset(d, 0, sizeof d);
        memset(b, 0, sizeof b);
        int q;
        cin >> n >> q;
        for (int i = 1; i <= n; i++) {
            int cur;
            cin >> cur;
            a[i][0] = cur;
            for(int j=1;j<=3;j++){
                int x = a[i][j - 1];
                while(x > 0){
                    a[i][j] += x % 10;
                    x /= 10;
                }
            }
        }
        while (q--) {
            int i1;
            cin >> i1;
            if(i1 == 1){
                int l, r;
                cin >> l >> r;
                update(l, r, 1, 1, n, 1);
            }else{
                int w;
                cin >> w;
                int t = getsum(w, w, 1, n, 1);
                t = min(3ll, t);
                cout << a[w][t] << '\n';
            }
        }
    }
    return 0;
}

不可以用Set的lower_bound来略微优雅一点地暴力，会炸

G1. Teleporters (Easy Version)

题意

给定一个数组 以及一个整数 ， 为硬币的总数量， 表示该传送点需要的硬币数量。定义每自主移动一步会扣除 个硬币，传送点是否使用是可选的，若使用传送点，将会使人物传送到原点，同时消耗对应数量的硬币。初始状态下，人物一定在原点，输出可使用传送点的最大数量。

思路

将 数组的所有数加上离原点的距离，升序排序 然后枚举即可。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt(), c = console.nextInt();
            int[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = console.nextInt() + (i + 1);
            Arrays.sort(a);
            int cnt = 0;
            for(int i=0;i<n;i++){
                c -= a[i];
                if(c < 0) break;
                cnt ++;
            }
            console.println(cnt);
        }
        console.close();
    }
}

略微有点么签到

G2. Teleporters (Hard Version)

题意

在 的基础上，传送点可以传送到原点 或 ，但人物的初始位置一定是原点。

思路

显然，我们一定得枚举，若讨论的话，会特别复杂。

我们考虑存储 加上离两端距离的最小值，以及其加上离原点的最大值，按照前者升序排序。

然后，我们枚举所有点，对于所枚举到的点 ，我们将其视为第一个使用的传送点，那么剩余的硬币数量即为 。

也许我们可以像前一题那样直接遍历，但那样显然太复杂了。

我们不妨用前缀和 + 二分的方式，这样便可快速找出最大的满足条件的数量了。

当然，使用前缀和要考虑排除当前作为第一个传送点的点。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt(), c = console.nextInt();
            long[][] a = new long[n][2];
            for(int i=0;i<n;i++) {
                int cur = console.nextInt();
                a[i] = new long[]{cur + Math.min(i + 1, n - i), cur + i + 1};
            }
            Arrays.sort(a, Comparator.comparingLong(o -> o[0]));
            long[] pre = new long[n + 1];
            for(int i=1;i<=n;i++) pre[i] = pre[i - 1] + a[i - 1][0];
            long cnt = 0;
            for(int i=0;i<n;i++){
                long nc = c - a[i][1];
                int l = 0, r = n, mid, max = 0;
                while(l <= r){
                    mid = (l + r) >> 1;
                    if(pre[mid] - ((mid > i) ? a[i][0] : 0) <= nc){
                        max = Math.max(mid + (mid > i ? 0 : 1), max);
                        l = mid + 1;
                    }else r = mid - 1;
                }
                cnt = Math.max(cnt, max);
            }
            console.println(cnt);
        }
        console.close();
    }
}

草，赛时一直在分类讨论，快死了