Contestant. Rank 3574. Rating +50 (+400 -350).

A. Hall of Fame

题意

给定一个只有 和 的长度为 的字符串，对于第 个字符， 表示将 照亮， 表示将 照亮。对于该字符串，允许选择一个 ，将 和 对应的字符交换，该操作最多可执行一次。判断是否可以将所有点照亮。若无需交换，输出 ；若交换后才满足条件，输出 ；若无法满足条件，输出 。

思路

很显然，只要出现 的排列，就一定可以满足条件。

那么，我们首先可以寻找第一个 之后有没有 ，只要找到了 就直接输出 即可。

否则，我们就需要寻找 ，并将其交换，并输出 对应的下标。

否则，输出 即可。

时间复杂度：

对应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){
            int n = scanner.nextInt();
            char[] a = scanner.next().toCharArray();
            int l = 0, r = 0, lr = -1;
            boolean preR = false;
            for(int i=0;i<a.length;i++){
                if(i < a.length - 1 && lr == -1 && a[i] == 'L' && a[i + 1] == 'R') lr = i + 1;
                if(a[i] == 'R') preR = true;
                else if(preR){
                    System.out.println(0);
                    continue nxt;
                }
            }
            System.out.println(lr);
        }
    }
}

简单思维题

B. MKnez’s ConstructiveForces Task

题意

给定数组的长度 ，构造一个非零数组 ，满足对于任何 ，有 $s1+s_2+…+s_n=s_i+s{i+1}NOYES$，以及所构造的数组。

思路

将等式右边移到左边，那么我们只需满足任意取出两个数后数组的和都为 即可。那么很显然，当 为偶数时，我们只需构造一个 的数组即可。

而当 为奇数的时候，既然等式左边有 项，而右边有 项，若仍然考虑相邻数的和相等的构造方式的话，我们不妨让这个相等的和为 ，这样的话，式子将会变为 ，那么多出来的项 即为 。因而，令 ，我们只需构造 即可。

时间复杂度：

对应AC代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t-- > 0){
            int n = scanner.nextInt();
            if(n == 3) System.out.println("NO");
            else{
                System.out.println("YES");
                if(n % 2 == 0){
                    for(int i=0;i<n/2;i++) System.out.print("1 -1 ");
                }else{
                    int w = n / 2;
                    System.out.printf("%d ", 1 - w);
                    for(int i=0;i<n/2;i++) System.out.printf("%d %d ", w, 1 - w);
                }
                System.out.println();
            }
        }
    }
}

既然是成对的，那就让和也成对呗

C. Least Prefix Sum

题意

给定一个数组 ，定义一次操作为任取一个数并将其改为它的相反数。输出最少的操作数，使 的前 项和为 的所有前 项和（）中的最小值。

思路

对于题给式子 ，

当 时，将不等式左边移到右边，我们可以得到第一个条件：以 为结尾的不包括 的后缀和均为非正数。

同理，当 时，将不等式右边移到左边，我们可以得到第二个条件：以 为第一项的前缀和均为非负数。

因为上述两者差不多，我们不妨来考虑前者。

显然，在遍历所有后缀和的时候，我们不可以在发现某一项不满足时直接把这一项取相反数，因为我们不能保证后面的项比这一项小，而将最大值取反才是最优解。

因此，为了每次查询的复杂度降到一个合理的值，我们可以采用优先队列。

时间复杂度：

对应AC代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t-- > 0) {
            int n = scanner.nextInt(), m = scanner.nextInt();
            long[] a = new long[n + 1];
            for(int i=1;i<=n;i++) a[i] = scanner.nextInt();
            PriorityQueue<Long> positive = new PriorityQueue<>((o1, o2) -> Math.toIntExact(o2 - o1));
            PriorityQueue<Long> negative = new PriorityQueue<>(Comparator.comparingLong(o -> o));
            long cnt = 0, sum = 0;
            for(int i=m;i>=2;i--){
                sum += a[i];
                if(a[i] > 0) positive.offer(a[i]);
                while(sum > 0) {
                    sum -= 2 * positive.poll();
                    cnt ++;
                }
            }
            sum = 0;
            for(int i=m + 1;i<=n;i++){
                sum += a[i];
                if(a[i] < 0) negative.offer(a[i]);
                while(sum < 0) {
                    sum -= 2 * negative.poll();
                    cnt ++;
                }
            }
            System.out.println(cnt);
        }
    }
}

优先队列yyds