0%

Codeforces - Round 843 Div 2

Contestant. Rank 6984. Rating -84 (+16 -100).

A1. Gardener and the Capybaras (easy version)

题意

给定一个由 构成的字符串,将其分成三部分 ,输出一种分法,让 成为三者中的最值。

对于两个字符串 ,若 ,当且仅当下面任意一个条件成立:

  1. 的前缀,但

思路

我们分成两个情况考虑:

  1. 遍历 ,若出现 ,那么让 单独成为中间的字符,这样中间的字符一定是最小的,直接输出即可。
  2. 如果不存在,那么我们让 的所有字符作为中间的字符串,因为第一位为 ,且足够长,一定可以保证其为最大。

时间复杂度:

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        nxt:while(t -- > 0){
            char[] a = scanner.next().toCharArray();
            int n = a.length;
            for(int i=1;i<n-1;i++){
                if(a[i] == 'a'){
                    for(int j=0;j<i;j++){
                        System.out.print(a[j]);
                    }
                    System.out.print(" a ");
                    for(int j=i+1;j<n;j++){
                        System.out.print(a[j]);
                    }
                    System.out.println();
                    continue nxt;
                }
            }
            System.out.printf("%c ", a[0]);
            for(int i=1;i<n-1;i++) System.out.print(a[i]);
            System.out.printf(" %c", a[n - 1]);
            System.out.println();
        }
    }


}

怎么会是呢,简单思维题怎么能想那么久呢

A2. Gardener and the Capybaras (hard version)

题意

参见 题。差别是数据量更大。

思路

参见 题。

时间复杂度:

对应AC代码

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

public class Main {

    public static void main(String[] args) throws Throwable{
        Console console = new Console();
        int t = console.nextInt();
        nxt:while(t -- > 0){
            char[] a = console.next().toCharArray();
            int n = a.length;
            for(int i=1;i<n-1;i++){
                if(a[i] == 'a'){
                    for(int j=0;j<i;j++){
                        console.print(a[j]);
                    }
                    console.print(" a ");
                    for(int j=i+1;j<n;j++){
                        console.print(a[j]);
                    }
                    console.println();
                    continue nxt;
                }
            }
            console.print(a[0] + " ");
            for(int i=1;i<n-1;i++) console.print(a[i]);
            console.print(" " + a[n - 1]);
            console.println();
        }
        console.close();
    }

    //快读模板 此处省略
    //public static class Console implements Closeable {}
}

java在输入多的时候记得用快读

B. Gardener and the Array

题意

给定数组 ,输出 是否有两个可不连续的不同子序列 满足 将 序列的所有数 进行 或运算 后得到的数相等。

思路

将每个数转为二进制,记录二进制下每一位有多少个数为

遍历所有数,若有一个数每一位都出现了不止 次,那么这个数可以被删去,从而和整个序列的或运算值相等。

若没有一个数满足上面的条件,输出

不宜开二维数组。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T, n, k, p;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        vector<vector<int>> c(n);
        map<int, int> cnt;
        for (int i = 0; i < n; i++) {
            scanf("%d", &k);
            for (int j = 0; j < k; j++) {
                scanf("%d", &p);
                c[i].push_back(p);
                cnt[p]++;
            }
        }
        bool res = false;
        for (int i=0;i<n;i++) {
            bool f = true;
            for (int j=0;j<c[i].size();j++) {
                if (cnt[c[i][j]] < 2) f = false;
            }
            if (f) {
                res = true;
                break;
            }
        }
        printf(res ? "Yes\n" : "No\n");
    }
}

既然不好用二维数组,那就果断vector

C. Interesting Sequence

题意

给定两个数 ,输出满足 值,若不存在,输出

思路

首先,观察可得,我们无法让 变大,因为随着 的递增,较低位会出现 ,从而使整个数减小。

其次,我们只能让一些低位变成 ,所以我们可以遍历每一位,此处可以分类讨论:

  1. 中是 ,但 中是 :无解,结束遍历;
  2. 中是 ,但 中是 :标记此点,且该点以后若 中出现 ,那么为无解,结束遍历;
  3. 中是 ,且 中是 :若未遇到 类情况,那么记录下最后一个满足本情况的点
  4. 中是 ,且 中是 :既然匹配,那么 应标为 ,否则会影响整体的值。

最后,对于 ,在 的位置将其改为 ,并把 后的位置改为 ,转换为十进制输出即可。

时间复杂度:左右

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        nxt:
        while (t-- > 0) {
            long a = scanner.nextLong(), b = scanner.nextLong();
            if (a == b) {
                System.out.println(a);
                continue;
            }
            if (b % 2 != 0) {
                System.out.println(-1);
                continue;
            }
            int[] ba = new int[64], bb = new int[64];
            int la = 0, lb = 0;
            while (a > 0) {
                ba[la++] = (int) (a % 2);
                a /= 2;
            }
            if (b == 0) {
                long ans = 1;
                for (int i = 0; i < la; i++) ans *= 2;
                System.out.println(ans);
                continue;
            }
            while (b > 0) {
                bb[lb++] = (int) (b % 2);
                b /= 2;
            }
            if (lb != la) {
                System.out.println(-1);
                continue;
            }
            int last0 = -1;
            boolean f = false;
            for (int i = 0; i < la; i++) {
                int ta = ba[la - i - 1], tb = bb[lb - i - 1];
                if (ta == tb) {
                    if (!f && ta == 0) last0 = la - i - 1;
                    if(ta == 1) last0 = -1;
                    continue;
                }
                if (ta == 0 && tb == 1) {
                    System.out.println(-1);
                    continue nxt;
                }
                if (ta == 1 && tb == 0) f = true;
            }
            if (last0 == -1) {
                System.out.println(-1);
            } else {
                long ans = 0;
                for (int i = la - 1; i > last0; i--) ans = ans * 2 + ba[i];
                ans = ans * 2 + 1;
                for (int i = last0 - 1; i >= 0; i--) ans *= 2;
                System.out.println(ans);
            }
        }
    }
}

写得有点过度码农了