2023年湖南理工学院程序设计竞赛新生赛 解题报告(简化版) | 珂学家 | 思维场
跳棋Ⅰ
https://ac.nowcoder.com/acm/contest/71419/A
前言
周末参加了一场赛氪组织的比赛，从上午9点做到下午2点，实在饿坏了，就错过这场比赛。
因为自己思维题比较弱，就把这场心心念念的比赛补了下。
欢迎关注
A. 跳棋Ⅰ
思路: 思维+数学
这个跳棋1比跳棋2难太多了, ^_^.
感觉这题，因为一枚子做炮架子，然后彼此互相做炮架子，这样应该是最快的。
形式地话，假设炮架距离为x, 类似这样的函数
f(x) = 2x + n / x + c, c为常数
如果求函数值最大，那x在[1, sqrt(n)]之间
可以三分求解，也可以枚举x在[1, sqrt(n)]
这题难在思维，还有尾巴的处理。
1. 枚举
时间复杂度
import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.function.Function;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
// 评估函数
// 1. 先构建炮架子
// 2. 互相跳跃
// 3. 最后收敛工作
Function<Integer, Integer> evaluate = (x) -> {
int start = x - 2;
int mid = (n - x) / (x - 1);
int r = x + mid * (x - 1);
int l = r - (x - 1);
// 最后收敛那个
int end = 0;
if (r < n - 1) {
end = (2 * r - n - l) + 1 + (n - 1 - r);
} else {
end = n - l - 1;
}
return start + mid + end;
};
int res = n - 2;
// 枚举长度(根号级别)
for (int i = 2; i <= n/i; i++) {
int r = evaluate.apply(i);
res = Math.min(res, r);
}
System.out.println(res);
}
}
2. 三分
时间复杂度，有待确定正确性
import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.function.Function;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
Function<Integer, Integer> evaluate = (x) -> {
int start = x - 2;
int mid = (n - x) / (x - 1);
int r = x + mid * (x - 1);
int l = r - (x - 1);
// 最后收敛那个
int end = 0;
if (r < n - 1) {
end = (2 * r - n - l) + 1 + (n - 1 - r);
} else {
end = n - l - 1;
}
return start + mid + end;
};
int res = n - 2;
// 三分框架
int l = 2, r = n;
while (r - l >= 3) {
int d = (r - l) / 3;
int m1 = l + d;
int m2 = r - d;
int res1 = evaluate.apply(m1);
int res2 = evaluate.apply(m2);
if (res1 <= res2) {
r = m2;
} else {
l = m1;
}
}
// 放宽一些的范围，计算
// 放宽为3会wa，这个三分有点虚, T_T
int skip = 10;
for (int i = Math.max(2, l - skip); i <= Math.min(n, r + skip); i++) {
res = Math.min(res, evaluate.apply(i));
}
System.out.println(res);
}
}
B. 跳棋Ⅱ
思路: 欧几里得距离 + 思维
核心：对称跳跃，任一一点的跳跃都是等价的，不会使得结果更优，也不会更差
C. 完美数
思路: 预处理枚举
因为指数增长很快，在10^9范围内，其实没几个数，可以打表维护，然后查询比对就行
D. 棋盘变换
思路: 模拟+贪心
时间复杂度为
E. 区间递增
思路: 单调栈上二分
唯一涉及数据结构的题。
对于一个区间，每次剔除掉一个元素，使得表达式最小。那一定是形成了相邻逆序对。
最终稳定下来，一定构成一个非递减的子序列。
注意这里不是求LIS, 而是基于单调栈构建非递减序列(和最小稳定表达式吻合)
也是离线做法，把查询根据右端点进行排序，那每个查询所对应结果，即是
单调栈上二分
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt(), q = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 离线计算
List<int[]>[]g = new List[n];
Arrays.setAll(g, x -> new ArrayList<>());
for (int i = 0; i < q; i++) {
int l = sc.nextInt() - 1, r = sc.nextInt() - 1;
g[r].add(new int[] {l, i});
}
// 单调栈上二分
int[] res = new int[q];
List<int[]> mono = new ArrayList<>();
for (int i = 0; i < n; i++) {
int v = arr[i];
while (!mono.isEmpty() && mono.get(mono.size() - 1)[0] > v) {
mono.remove(mono.size() - 1);
}
mono.add(new int[] {v, i});
for (int[] e: g[i]) {
int l = 0, r = mono.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
int[] cur = mono.get(m);
if (cur[1] < e[0]) {
l = m + 1;
} else {
r = m - 1;
}
}
int s = mono.size() - l;
res[e[1]] = (i - e[0] + 1) - s;
}
}
System.out.println(Arrays.stream(res).mapToObj(String::valueOf).collect(Collectors.joining("\n")));
}
}
F. 费解的gcd
思路: 正难则反，离线计算+逆序建构
gcd的操作，很难撤销维护，尤其这种随机点撤销。
所幸 正难则反
可以把撤销过程，看成逆序构建gcd
因此，这题的思路，也是离线计算，逆向构建gcd(正向删除)
import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static long mod = 998244353l;
static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt(), q = sc.nextInt();
// 逆向思维
long[] arr = new long[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
}
// 保存操作序列
Set<Integer> hash = new HashSet<>();
Deque<Integer> op = new ArrayDeque<>();
for (int i = 0; i < q; i++) {
int v = sc.nextInt();
if (v != 0) {
hash.add(v);
}
op.push(v);
}
// 回到最后的点
long gv = 0;
for (int i = 1; i <= n; i++) {
if (!hash.contains(i)) gv = gcd(gv, arr[i]);
}
// 逆序回放
long res = 0;
while (!op.isEmpty()) {
int v = op.pop();
if (v == 0) {
res = (res + gv) % mod;
} else {
gv = gcd(gv, arr[v]);
}
}
System.out.println(res);
}
}
G. 梦中HNIST
思路：模拟
很像五子棋的落子判定逻辑
H. 混乱大枪战
思路: 公式推导，排序贪心
感觉这类题出的真好，一度又想搬出反悔堆来了
假定选定自爆的人为b1, b2, ..., bn
那其他人为k1，k2, ..., km
L(i)为生命值，B(i)为伤害值, L为所有人的生命总和
最后这个公式一推，就能发现，就是从f(i)=L(i)+B(i)挑选最小的几个数，使得满足其和大于等于总生命值
因此f(i)=L(i)+B(i)，然后从大到小排序，然后贪心直到总和大于等于L，此时自爆个数一定是最小的。
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
// 定义 f函数 = life + attack
Long[] f = new Long[n];
long s = 0;
for (int i = 0; i < n;i ++) {
long u = sc.nextInt(), v = sc.nextInt();
s += u;
f[i] = u + v;
}
// 对f函数排序
Arrays.sort(f, Comparator.comparingLong(x -> -x));
// 贪心
int ans = 0;
long tmp = 0;
for (int i = 0; i < n; i++) {
tmp += f[i];
if (tmp >= s) {
ans = i + 1;
break;
}
}
System.out.println(ans);
}
}
I. 集！挡！波！它又来了！
思路：模拟 + 数学
这题有个前置条件
- 必须保证自己积蓄了1点能量
- 对方最后一步没有挡，有效波
满足这2个条件下的方案数
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
char[] str = sc.next().toCharArray();
int acc = 0;
long res = 1; // n <= 30
for (int i = 0; i < n - 1; i++) {
if (str[i] == 'B') {
} else {
// 集, 挡二选一
res *= 2;
}
if (str[i] == 'J') acc++;
}
if (str[n - 1] == 'D' || (str[n - 1] == 'B' && acc > 0)) {
System.out.println(0);
} else {
// 这个-1，其实是小小的容斥
System.out.println(res - 1);
}
}
}
}
投递中国移动北京等公司10个岗位 >