Contestant. Rank 9289. Rating -54 (+446 -500).

A. Koxia and Whiteboards

题意

给定序列 , , 执行 次操作，对于第 次操作，将序列 中任意数值修改为 ，输出操作之后序列 的总和的最大值。

思路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 n = scanner.nextInt(), m = scanner.nextInt();
            int[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = scanner.nextInt();
            for(int i=0;i<m;i++) {
                Arrays.sort(a, 0, n);
                a[0] = scanner.nextInt();
            }
            long ans = 0;
            for(int i=0;i<n;i++) ans += a[i];
            System.out.println(ans);
        }
    }
}

思路2

先大胆假设：既然对于 中的修改是任意的，那么我们只要把 升序排序，依次用降序排序的 中的值替换即可。

假设如此，但需要注意到一点：操作的顺序是不能更改的。

因此，在排序前，我们需要一并存下来 $bib_iimaximax \neq m-1a_ia_pb{m-1}$ 替换即可。

那么，我们来考虑如何选取这个 ：

因为替换后的 序列是先递减后递增的，那么最小值将出现在最后一次替换的 $bja{i+1}bja_ia_p=min(a{i+1}, b_j)i$ 的大小，不能越界。

时间复杂度：

对应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();
            int[] a = new int[n];
            int[][] b = new int[m][2];
            for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
            for (int i = 0; i < m; i++) b[i] = new int[]{i, scanner.nextInt()};
            int lastB = b[m - 1][1];
            Arrays.sort(a);
            Arrays.sort(b, (o1, o2) -> o2[1] - o1[1]);
            long ans = 0;
            int i = 0, j = 0, lastChange = 0, lastChangedI = 0, approached = 0;
            for (; i < n && j < m; i++) {
                if (a[i] < b[j][1]) {
                    approached = Math.max(approached, b[j][0]);
                    lastChange = b[j][1];
                    lastChangedI = i;
                    ans += b[j++][1];
                }
                else ans += a[i];
            }
            for (; i < n; i++) ans += a[i];
            if(j == 0) ans = ans - a[0] + lastB;
            else if(j < m && approached != m - 1) {
                ans = ans - (lastChangedI + 1 > n - 1 ? lastChange : Math.min(lastChange, a[lastChangedI + 1])) + lastB;
            }
            System.out.println(ans);
        }
    }
}

有时候很简单的签到题不要想太多

B. Koxia and Permutation

题意

给定 ，，求出一种 的排列 ，使得对于每个长度为 的连续子序列中，最大值和最小值的和最小。

思路

既然要让最大值和最小值的和最小，那么我们就需要让最大值出现的次数尽量少，最小值出现的次数尽量多。

因而，结合区间的移动，我们可以先降序地输出 个数，然后再输出 ，此时1出现的次数被最大化。

同理，那么我们就可以在降序输出后升序输出 个数，然后重复上述2个步骤，循环输出至无数可输出为止。

当然，可以证明交替输出和上述思路得到的序列性质是一样的。

时间复杂度：

对应AC代码

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d %d", &n, &k);
        int l = 1, r = n, now = k - 1;
        for (int i = 1; i <= n; i++) {
            printf("%d ", now > 0 ? r-- : l++);
            now--;
            if (now == 1 - k) now = k - 1;
        }
        printf("\n");
    }
}

思维题还是要多做做，写太慢了。

而且如果用java写的话，需要使用快读，否则会超时。

C. Koxia and Number Theory

题意

给定序列 ，判断是否存在 ，满足对于任意不同的两个下标 , ，都有 。

做法

1. 显然不能出现重复数值
2. 考虑每个质数 , 遍历序列 , 统计所有 出现的次数，若全都大于2，判定NO

对于第二步的数学证明

1. 假设 和 同余于质数 ，那么 和 同余于 。
2. 在1的条件下，要使 不被 整除，则必须满足 。
3. 因而，我们需要存在至少一个 的值 ，满足 ，这样，我们就可以使用 中国剩余定理 (CRT) 解出 。
4. 任取一个 ，若它的出现次数 ，那么存在 符合条件1的条件。此时，根据上面的证明，可以得出 。
5. 由上述证明，若所有 ，那么无法解出 ，判定为NO。

对于上述证明的具体例子

判定YES的一个例子：

对于下面的输入

1
3
5 7 10

取 ，则可得取余后的序列 ，此时 ，，有

取 ，则可得取余后的序列 ，此时 ，，有

…

对于每一个 ，都有一个同余方程组，可根据 求出 的一个通解。从而，我们可以联立后解出 。

判定NO的一个例子：

对于下面的输入

1
11
6 9 12 14 16 17 18 20 25 28 30

取 ，则可得取余后的序列 ，此时对于任意 ，都有 ，因而我们无法找到一个式子满足，从而无法解得 。

中国剩余定理 (CRT)

对于 ，满足 ，则对于如下形式的一元线性同余方程组

(1) 计算 ，即 是除 之外其他整数的乘积；

(2) 设 为 模 的逆元，即求 ；

(3) 上述方程组的通解为： 。模 后，只有一个解 。

更加直观的做法

1. 枚举所有元素，若有重复则判NO；

2. 枚举所有 的数 ，若模 后的序列所有数字出现的次数都大于 ，那么判NO。

第二步的可行性

肉眼可见，当 足够大时，判断素数的步骤是超时的，但因为我们是从小到大枚举的，因而我们可以保证所有合数在被枚举到之前都已经被判断过，且加上对于合数的可行性判断后，时间复杂度在合理范围内。

对于右边界 ，我们考虑抽屉原理：将 个物品放入 个抽屉，肯定有至少一个抽屉有两个物品。

那么，对于 个物品，放入大于 个抽屉中，我们肯定无法让所有抽屉都放上 个物品。

因而，我们只需遍历到 即可。

时间复杂度：

对应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();
            long[] a = new long[n];
            for(int i=0;i<n;i++) a[i] = scanner.nextLong();
            for(int i=1;i<n;i++) for(int j=i-1;j>=0;j--) if(a[i] == a[j]){
                System.out.println("NO");
                continue nxt;
            }
            for(int i=2;i<=n / 2;i++){
                int[] m = new int[i];
                boolean f = false;
                for(int j=0;j<n;j++) m[(int)(a[j] % i)] ++;
                for(int j=0;j<i;j++) {
                    if(m[j] < 2) {
                        f = true;
                        break;
                    }
                }
                if(!f){
                    System.out.println("NO");
                    continue nxt;
                }
            }
            System.out.println("YES");
        }
    }

}

数论得多看看力，有时候可以多尝试一些数据来找寻规律。