0%

Codeforces - Round 842 Div 2

Contestant. Rank 7746. Rating -14 (+186 -200).

A. Greatest Convex

题意

给定 ,输出满足条件的 ,使 的倍数。

思路

,显然,令 即可,答案即为

时间复杂度:

对应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){
            System.out.println(scanner.nextInt() - 1);
        }
    }
}

怎么会有这么签到的题

B. Quick Sort

题意

给定整数 以及一个排列 ,定义一次操作为选择 个数并将其升序移至排列末尾。输出最少操作数,使整个排列升序。

思路

显然,最后的排列一定是 ,那么,我们不妨先来考虑单个元素是否需要移至后面。

对于一个元素 ,如果它的前面没有出现 ,那么显然我们只有将他移动至最后才能让排列成功构造出来,否则我们就无需操作。

所以,我们只需统计需要移动的元素数量 ,然后输出 即可,因为每次移动我们可以选多个。

时间复杂度:

对应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(), k = scanner.nextInt();
            boolean[] a = new boolean[n + 1];
            int sum = 0;
            for(int i=0;i<n;i++){
                int cur = scanner.nextInt();
                a[cur] = true;
                if(cur != 1){
                    if(!a[cur - 1]) {
                        a[cur] = false;
                        sum ++;
                    }
                }
            }
            System.out.println((int) Math.ceil((double) sum / k));
        }
    }
}

从一个推向多个是否合理呢

C. Elemental Decompress

题意

给定数组 以及其长度 ,规定 。构造两个排列 ,满足 。若能构造,输出 以及其中一种构造,否则输出

思路1

显然,一个数不能出现三次及以上,否则无法构造。

并且,我们可以发现,排序后的数组,若出现元素满足 ,那么也无法构造(可以使用反证法

那么,我们可以降序排序数组,并执行下面的两个操作:

  1. 遍历数组,将重复两次的数分散到两个数组内,做拆分(此时可排除出现三次及以上的数);
  2. 遍历数组,如果 内,那么寻找不在 中的最大值,将其放入 ,反之亦如此。

遍历结束后,若全都填满了就是有解,输出即可。

时间复杂度:

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:while(t -- > 0){
            int n = console.nextInt();
            int[][] a = new int[n + 1][2];
            boolean[] inp = new boolean[n + 1], inq = new boolean[n + 1];
            for(int i=1;i<=n;i++) a[i] = new int[]{i, console.nextInt()};
            Arrays.sort(a, 1, n + 1, Comparator.comparingInt(o -> -o[1]));
            int[] p = new int[n + 1], q = new int[n + 1];
            for(int i=1;i<=n;i++){
                int k = a[i][0], v = a[i][1];
                if(inp[v] && inq[v]){
                    console.println("NO");
                    continue nxt;
                }
                if(inp[v]){
                    q[k] = v;
                    inq[v] = true;
                }else{
                    p[k] = v;
                    inp[v] = true;
                }
            }
            int rp = n, rq = n;
            for(int i=1;i<=n;i++){
                int k = a[i][0];
                if(p[k] == 0){
                    while(inp[rp]) rp --;
                    inp[rp] = true;
                    if(rp > q[k]){
                        console.println("NO");
                        continue nxt;
                    }
                    p[k] = rp --;
                }else{
                    while(inq[rq]) rq --;
                    inq[rq] = true;
                    if(rq > p[k]){
                        console.println("NO");
                        continue nxt;
                    }
                    q[k] = rq --;
                }
            }
            for(int i=1;i<=n;i++){
                if(!inp[i] && !inq[i]){
                    console.println("NO");
                    continue nxt;
                }
            }
            console.println("YES");
            for(int i=1;i<=n;i++) console.print(p[i] + " ");
            console.println();
            for(int i=1;i<=n;i++) console.print(q[i] + " ");
            console.println();
        }
        console.close();
    }

    //快读模板,此处略去
    //public static class Console implements Closeable {}
}

思路2

首先,这种思路无法通过

若未考虑到 思路 中第二个结论,那么我们可以考虑使用链表的方式,遍历排序后的数组的时候,我们可以把求得的解对应的元素删去,从而获取到我们想要的元素。

时间复杂度约为,无法通过

对应AC代码

在赛时可以思考能否得出一些特定的结论出来