Contestant. Rank 9289. Rating -54 (+446 -500).
A. Koxia and Whiteboards
题意
给定序列 \(a\) , \(b\) , 执行 \(m\) 次操作，对于第 \(j\) 次操作，将序列 \(a\) 中任意数值修改为 \(b_j\) ，输出操作之后序列 \(a\) 的总和的最大值。
思路1
注意到题目所给 \(n\) 和 \(m\) 很小，因而我们可以遍历 \(b_j\)，在每次替换前 \(sort\) 一遍 \(a\) 数组，然后替换 \(a_0\) 即可。
一句话，暴力+模拟。
时间复杂度：\(O(mn \log 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(), 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
先大胆假设：既然对于 \(a\) 中的修改是任意的，那么我们只要把 \(a\) 升序排序，依次用降序排序的 \(b\) 中的值替换即可。
假设如此，但需要注意到一点：操作的顺序是不能更改的。
因此，在排序前，我们需要一并存下来 \(b_i\) 的下标。在替换时，我们需要记录访问到的 \(b_i\) 所存原下标的最大值 \(imax\)，如果 \(imax \neq m-1\)，那么肯定还有一些较小的值等待替换，这些值显然是小于剩下的 \(a_i\) 的。所以，我们可以贪心的认为，我们只需找到替换后的一个合适的 \(a_p\)，用 \(b_{m-1}\) 替换即可。
那么，我们来考虑如何选取这个 \(a_p\)：
因为替换后的 \(a\) 序列是先递减后递增的，那么最小值将出现在最后一次替换的 \(b_j\) 和未替换的第一个 \(a_{i+1}\) （ \(b_j\) 替换 \(a_i\) ）之间，即 \(a_p=\min(a_{i+1}, b_j)\)。当然，肯定要判一下 \(i\) 的大小，不能越界。
时间复杂度：\(O(n \log 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(), 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
题意
给定 \(n\)，\(k\)，求出一种 \(n\) 的排列 \(p\)，使得对于每个长度为 \(k\) 的连续子序列中，最大值和最小值的和最小。
思路
既然要让最大值和最小值的和最小，那么我们就需要让最大值出现的次数尽量少，最小值出现的次数尽量多。
因而，结合区间的移动，我们可以先降序地输出 \(k-1\) 个数，然后再输出 \(1\)，此时1出现的次数被最大化。
同理，那么我们就可以在降序输出后升序输出 \(k\) 个数，然后重复上述2个步骤，循环输出至无数可输出为止。
当然，可以证明交替输出和上述思路得到的序列性质是一样的。
时间复杂度：\(O(n)\)
对应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
题意
给定序列 \(a\) ，判断是否存在 \(x\) ，满足对于任意不同的两个下标 \(i\) , \(j\) ，都有 \(gcd(a_i+x,a_j+x)=1\)。
做法
- 显然不能出现重复数值
- 考虑每个质数 \(t\) , 遍历序列 \(a\) , 统计所有 \(a_i \% t\) 出现的次数，若全都大于2，判定NO
对于第二步的数学证明
- 假设 \(a_u\) 和 \(a_v\) 同余于质数 \(p\)，那么 \(a_u+x\) 和 \(a_v+x\) 同余于 \(p\)。
- 在1的条件下，要使 \(gcd(a_u+x,a_v+x)\) 不被 \(p\) 整除，则必须满足 \((x + a_u) \not\equiv 0 \pmod p\) 。
- 因而，我们需要存在至少一个 \(a_i \% p\) 的值 \(j\) ，满足 \(x \equiv (p-j) \pmod p\)，这样，我们就可以使用 中国剩余定理 (CRT) 解出 \(x\)。
- 任取一个 \(j\) ，若它的出现次数 \(cnt_j\geq2\)，那么存在 \(x\) 符合条件1的条件。此时，根据上面的证明，可以得出\(x \not\equiv (p-j) \pmod p\) 。
- 由上述证明，若所有 \(cnt_i\geq2\)，那么无法解出 \(x\) ，判定为NO。
对于上述证明的具体例子
判定YES的一个例子：
对于下面的输入
1
3
5 7 10取 \(p = 2\)，则可得取余后的序列 \(1, 1, 0\)，此时 \(cnt_0<2\)，\(cnt_1\geq2\)，有 \(x \equiv 2-0 \pmod 2\)
取 \(p = 3\)，则可得取余后的序列 \(2, 1, 1\)，此时 \(cnt_1\geq2\)，\(cnt_2<2\)，有 \(x \equiv 3-2 \pmod 3\)
...
对于每一个 \(p\) ，都有一个同余方程组，可根据 \(CRT\) 求出 \(x\) 的一个通解。从而，我们可以联立后解出 \(x\)。
判定NO的一个例子：
对于下面的输入
1
11
6 9 12 14 16 17 18 20 25 28 30取 \(p = 5\)，则可得取余后的序列 \(1,4,2,4,1,2,3,0,0,3,0\)，此时对于任意 \(j\)，都有 \(cnt_j\geq2\)，因而我们无法找到一个式子满足\(x \equiv (p-j) \pmod p\)，从而无法解得 \(x\) 。
中国剩余定理 (CRT)
对于 \(m_1, m_2, ...,m_n\)，满足 \(gcd(m_1,m_2,..,m_n)=1\)，则对于如下形式的一元线性同余方程组
\(\begin{cases} x \equiv a_1 \pmod{m_1}\\ x \equiv a_2 \pmod{m_2}\\ \cdots\\ x \equiv a_n \pmod{m_n} \end{cases}\)
计算 \(M=\prod\limits_{i=1}^n m_i,M_i=\dfrac{M}{m_i}\)，即 \(M_i\) 是除 \(m_i\) 之外其他整数的乘积；
设 \(t_i\) 为 \(M_i\) 模 \(m_i\) 的逆元，即求 \(t_i = (M_i)^{-1}\pmod{m_i}\)；
上述方程组的通解为：\(x=a_1t_1M_1+a_2t_2M_2+...+a_nt_nM_n+kM，k\in Z\) 。模 \(M\) 后，只有一个解 \(x=a_1t_1M_1+a_2t_2M_2+...+a_nt_nM_n\)。
更加直观的做法
枚举所有元素，若有重复则判NO；
枚举所有 \(2 \sim n/2\) 的数 \(p\)，若模 \(p\) 后的序列所有数字出现的次数都大于 \(2\)，那么判NO。
第二步的可行性
肉眼可见，当 \(n\) 足够大时，判断素数的步骤是超时的，但因为我们是从小到大枚举的，因而我们可以保证所有合数在被枚举到之前都已经被判断过，且加上对于合数的可行性判断后，时间复杂度在合理范围内。
对于右边界 \(n/2\)，我们考虑抽屉原理：将 \(n+1\) 个物品放入 \(n\) 个抽屉，肯定有至少一个抽屉有两个物品。
那么，对于 \(n\) 个物品，放入大于 \(n/2\) 个抽屉中，我们肯定无法让所有抽屉都放上 \(2\) 个物品。
因而，我们只需遍历到 \(n/2\) 即可。
时间复杂度：\(O\left(\frac{n^2}{\log n} \right)\)
对应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");
}
}
}数论得多看看力，有时候可以多尝试一些数据来找寻规律。