Practice.

A. A+B?

题意

给定一个形如 \(a+b\) 的字符串，输出答案。\(a, b \in [0, 9]\)。

思路

模拟。

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

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){
            String[] a = scanner.next().split("\\+");
            System.out.println(Integer.parseInt(a[0]) + Integer.parseInt(a[1]));
        }
    }
}

过于签到，应该有语言可以一行解决吧

B. Matrix Rotation

题意

给定一个 \(2 \times 2\) 的矩阵，定义操作为将矩阵旋转 \(90°\)，输出任意次操作后，能否使矩阵满足下面的条件：

每一行的第一个元素小于第二个元素；
每一列的第一个元素小于第二个元素。

思路

模拟。

时间复杂度：\(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();
        nxt:
        while(t -- > 0){
            int a = scanner.nextInt(), b = scanner.nextInt(), c = scanner.nextInt(), d = scanner.nextInt();
            for(int i=0;i<4;i++){
                if(a < b && b < d && a < c && c < d){
                    System.out.println("YES");
                    continue nxt;
                }
                int tmp = b; b = a; a = c; c = d; d = tmp;
            }
            System.out.println("NO");
        }
    }
}

模拟就完事了

C. Different Differences

题意

给定两个整数 \(k, n\)，构造长度为 \(k\) 且严格递增的数组 \(a\)，其中 \(a_{k - 1} \leq n\)。输出一种构造，使数组 \([a_2 - a_1, a_3 - a_2, \ldots a_k - a_{k - 1}]\) 内不相同的元素数量最大。

思路

若数组无长度和大小限制，那么我们只需输出以 \(1\) 为首项和公差的等差数列的前 \(n\) 项和即可。

考虑到限制，我们在输出第 \(i\) 项的时候，还因考虑它的最大值 \(i + n - k\)，取一个最小值即可。

时间复杂度：\(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 k = scanner.nextInt(), n = scanner.nextInt();
            int a = 1;
            for(int i=1;i<=k;i++){
                System.out.printf("%d ", Math.min(a, i + n - k));
                a += i;
            }
            System.out.println();
        }
    }
}

简单构造题

D. Absolute Sorting

题意

给定一个数组 \(a\)，所有元素均为正整数。输出一个 \(x\)，满足将所有数减掉 \(x\) 后取绝对值后的序列不递减。若无解，输出 \(-1\)。

思路

由题意，我们需要满足 \(|a_i - x| \leq |a_{i + 1} - x|\)。

我们不妨先来考虑 \(a_i < a_{i + 1}\) 的情况：

\(x \leq a_i\)，那么原式化为 \(a_i \leq a_{i + 1}\)，恒成立；
\(x \geq a_{i + 1}\)，那么原式化为 \(a_i \geq a_{i + 1}\)，不成立；
\(a_i < x < a_{i + 1}\)，那么原式化为 \(x - a_i \leq a_{i + 1} - x\)，即 \(x \leq \lfloor \frac{a_i + a_{i + 1}}{2} \rfloor\)。

综上所述，\(x \le \lfloor \frac{a_i + a_{i+1}}{2} \rfloor\)。

同理，当 \(a_i > a_{i + 1}\) 时，\(x \ge \lceil \frac{a_i + a_{i+1}}{2} \rceil\)。

因而，我们只需求出左端点的最大值 \(l\) 和右端点的最小值 \(r\)，然后判断 \(l \leq r\) 是否成立即可。

时间复杂度：\(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();
            int pre = scanner.nextInt();
            int l = 0, r = Integer.MAX_VALUE;
            for(int j = 1; j < n; j++)
            {
                int cur = scanner.nextInt();
                if(pre > cur)
                    l = Math.max(l, (pre + cur + 1) / 2);
                if(pre < cur)
                    r = Math.min(r, (pre + cur) / 2);
                pre = cur;
            }
            System.out.println(l <= r ? l : -1);
        }
    }
}

简单的拆绝对值分类讨论