Practice.

代码略去了快读模板

A. Add Plus Minus Sign

题意

给定一个长度为 \(n\) 的二进制字符串，输出 \(n-1\) 个加减运算符，满足最后的结果的绝对值最小。

思路

无视第一位，配对 \(1,1\)，对每一对输出 \(-,+\)，剩余的 \(1\) 输出 \(-\)，剩余的 \(0\) 输出任意符号。

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

对应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();
        while(t -- > 0){
            int n = console.nextInt();
            char[] input = console.next().toCharArray();
            int pre = -1, now = input[0] - '0';
            char[] ans = new char[n - 1];
            if(now == 1) pre = -2;
            for(int i=0;i<n-1;i++){
                now = input[i + 1] - '0';
                if(now == 0) ans[i] = '+';
                else{
                    if(pre == -1) pre = i;
                    else{
                        if(pre != -2) ans[pre] = '+';
                        ans[i] = '-';
                        pre = -1;
                    }
                }
            }
            if(pre != -1 && pre != -2) ans[pre] = '+';
            console.println(String.valueOf(ans));
        }
        console.close();
    }
}

略微简单的打卡题

B. Coloring

题意

给定 \(m\) 种颜色的数量，总量为 \(n\)，将长度为 \(n\) 的序列染上色，满足所有长度为 \(k\) 的连续子序列内没有相同的颜色，输出方案是否存在。

思路

我们不妨开一个数组记录所有的数量，然后降序排序。

显然，若一个颜色 \(p\) 在 \(x\) 位置出现了，那么在 \([x + 1, x + k - 1]\) 内都不能出现 \(p\)，那么我们不妨将序列按 \(k\) 分段，那么段数即为 \(d = \lceil \frac{n}{k} \rceil\)。

遍历排序后的数组，若 \(a_i > d\)，那么就是无解的，输出 \(NO\) 即可，否则，我们只需将剩余的最少的颜色取出来和它一起配对为一个长为 \(d\) 的组合。

当然，配对次数过多时，我们会发现段数会减少 \(1\)，此时若能满足条件，就可以直接输出 \(YES\) 了。

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

对应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();
        while(t -- > 0){
            int n = console.nextInt(), m = console.nextInt(), k = console.nextInt();
            Integer[] a = new Integer[m];
            for(int i=0;i<m;i++) a[i] = console.nextInt();
            Arrays.sort(a, Comparator.comparingInt(o -> -o));
            int d = n / k + (n % k == 0 ? 0 : 1), l = n % k;
            boolean ans = true;
            for(int i=0;i<n;i++){
                int cur = a[i];
                if(cur > d) {
                    ans = false;
                    break;
                }
                if(l == 0) break;
                l --;
                if(l == 0) d --;
            }
            console.println(ans ? "YES" : "NO");
        }
        console.close();
    }
}

有点小贪心，因为不用考虑拿什么出来组合

C. Ice and Fire

题意

对于 \(n\) 个选手，选手 \(i\) 的能力值为 \(i\)。给定一个长为 \(n - 1\) 的二进制字符串 \(s\)，\(s_i\) 表示第 \(i\) 次比赛的输赢判定，\(0\) 则能力值低者胜，否则高者胜。对于所有 \(x \in [2,n]\)，输出选择不超过 \(x\) 个选手进行比赛，最后有多少个选手有机会成为胜者。

比赛机制为选择任意两个选手进行比赛，直至剩余最后一人，判定该选手为胜者。

思路

显然地，最后的获胜情况和最后一个输赢判定有直接关系。

更进一步地说，最后一段相同连续区间的长度决定了胜者的数量。

举一个例子，若 \(s\) 为 \(\ldots,1,0,0,0,0\)，那么能力值最大的三个选手一定不可能成为赢家，而恰好剩余的选手经过一定的排序都可以成为赢家。

因而，我们唯一关心的就是从后往前第一个不同的字符出现的位置，对于所有 \(x\)，输出数量即可。

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

对应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();
        while(t -- > 0){
            int n = console.nextInt();
            char[] in = console.next().toCharArray();
            int p0 = 1, p1 = 1;
            for(int i=1;i<n;i++){
                int now = in[i - 1] - '0';
                if(now == 0){
                    p0 = i + 1;
                    console.print(p1 + " ");
                }else{
                    p1 = i + 1;
                    console.print(p0 + " ");
                }
            }
            console.println();
        }
        console.close();
    }
}

想通了就很简单的思维题