Contestant. Rank 7746. Rating -64 (+186 -250).

A. Greatest Convex

题意

给定 \(k\)，输出满足条件的 \(x\)，使 \(x!+(x-1)!\) 为 \(k\) 的倍数。

思路

\(x!+(x-1)!=(x-1)!(x+1)\)，显然，令 \(x+1=k\) 即可，答案即为 \(k-1\)。

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

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

题意

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

思路

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

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

所以，我们只需统计需要移动的元素数量 \(sum\)，然后输出 \(\lfloor \frac{sum}{k} \rfloor\) 即可，因为每次移动我们可以选多个。

时间复杂度：\(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();
        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

题意

给定数组 \(a\) 以及其长度 \(n\)，规定 \(1 \leq a_i \leq n\)。构造两个排列 \(p\)，\(q\)，满足 \(\max(p_i,q_i)=a_i\)。若能构造，输出 \(YES\) 以及其中一种构造，否则输出 \(NO\)。

思路1

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

并且，我们可以发现，排序后的数组，若出现元素满足 \(a_i<i\)，那么也无法构造（可以使用反证法）

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

遍历数组，将重复两次的数分散到两个数组内，做拆分（此时可排除出现三次及以上的数）；
遍历数组，如果 \(a_i\) 在 \(p\) 内，那么寻找不在 \(q\) 中的最大值，将其放入 \(q\)，反之亦如此。

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

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

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

首先，这种思路无法通过 \(Test3\)。

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

时间复杂度约为\(O(n^2)\)，无法通过

对应AC代码

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