Practice.

A. A+B?

题意

给定一个形如 的字符串，输出答案。。

思路

模拟。

时间复杂度：

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

题意

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

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

思路

模拟。

时间复杂度：

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

题意

给定两个整数 ，构造长度为 且严格递增的数组 ，其中 $a{k - 1} \leq n[a_2 - a_1, a_3 - a_2, \ldots a_k - a{k - 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){
            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

题意

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

思路

由题意，我们需要满足 $|ai - x| \leq |a{i + 1} - x|$。

我们不妨先来考虑 $ai < a{i + 1}$ 的情况：

1. $x \leq aia_i \leq a{i + 1}$，恒成立；
2. $x \geq a{i + 1}a_i \geq a{i + 1}$，不成立；
3. $ai < x < a{i + 1}x - ai \leq a{i + 1} - xx \leq \lfloor \frac{ai + a{i + 1}}{2} \rfloor$。

综上所述，$x \le \lfloor \frac{ai + a{i+1}}{2} \rfloor$。

同理，当 $ai > a{i + 1}x \ge \lceil \frac{ai + a{i+1}}{2} \rceil$。

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

时间复杂度：

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

简单的拆绝对值分类讨论