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

A1. Gardener and the Capybaras (easy version)

题意

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

对于两个字符串 \(x\)，\(y\)，若 \(x < y\)，当且仅当下面任意一个条件成立：

\(x\) 是 \(y\) 的前缀，但\(x \neq y\)；
\(x_1='a',y_1='b'\)。

思路

我们分成两个情况考虑：

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

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

对应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)

题意

参见 \(A1\) 题。差别是数据量更大。

思路

参见 \(A1\) 题。

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

对应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

题意

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

思路

将每个数转为二进制，记录二进制下每一位有多少个数为 \(1\)。

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

若没有一个数满足上面的条件，输出 \(NO\)。

不宜开二维数组。

时间复杂度：\(O(nk)\)

对应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

题意

给定两个数 \(n,x\)，输出满足 \(n\&(n+1)\&(n+2)\&...\&m=x\) 的 \(m\) 值，若不存在，输出 \(-1\)。

思路

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

其次，我们只能让一些低位变成 \(0\)，所以我们可以遍历每一位，此处可以分类讨论：

\(n\) 中是 \(0\) ，但 \(x\) 中是 \(1\) ：无解，结束遍历；
\(n\) 中是 \(1\) ，但 \(x\) 中是 \(0\) ：标记此点，且该点以后若 \(x\) 中出现 \(1\)，那么为无解，结束遍历；
\(n\) 中是 \(0\) ，且 \(x\) 中是 \(0\) ：若未遇到 \(2\) 类情况，那么记录下最后一个满足本情况的点 \(last0\)；
\(n\) 中是 \(1\) ，且 \(x\) 中是 \(1\) ：既然匹配，那么 \(last0\) 应标为 \(-1\)，否则会影响整体的值。

最后，对于 \(n\)，在 \(last0\) 的位置将其改为 \(1\)，并把 \(last0\) 后的位置改为 \(0\)，转换为十进制输出即可。

时间复杂度：\(O(n)\)左右

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

写得有点过度码农了