0%

Codeforces - Polynomial Round 2022 Div 1 plus 2

Practice.

代码略去了快读模板

A. Add Plus Minus Sign

题意

给定一个长度为 的二进制字符串,输出 个加减运算符,满足最后的结果的绝对值最小。

思路

无视第一位,配对 ,对每一对输出 ,剩余的 输出 ,剩余的 输出任意符号。

时间复杂度:

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

题意

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

思路

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

显然,若一个颜色 位置出现了,那么在 内都不能出现 ,那么我们不妨将序列按 分段,那么段数即为

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

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

时间复杂度:

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

题意

对于 个选手,选手 的能力值为 。给定一个长为 的二进制字符串 表示第 次比赛的输赢判定, 则能力值低者胜,否则高者胜。对于所有 ,输出选择不超过 个选手进行比赛,最后有多少个选手有机会成为胜者。

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

思路

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

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

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

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

时间复杂度:

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

想通了就很简单的思维题