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

A1. Gardener and the Capybaras (easy version)

题意

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

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

1. 是 的前缀，但；
2. 。

思路

我们分成两个情况考虑：

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);
            }
        }
    }
}

写得有点过度码农了