2023-12-09 11:48 已编辑東京大学 golang 发布于浙江

关注

2023年湖南理工学院程序设计竞赛新生赛解题报告(简化版) | 珂学家 | 思维场

跳棋Ⅰ

https://ac.nowcoder.com/acm/contest/71419/A

前言

alt

周末参加了一场赛氪组织的比赛，从上午9点做到下午2点，实在饿坏了，就错过这场比赛。

因为自己思维题比较弱，就把这场心心念念的比赛补了下。

欢迎关注

珂朵莉牛客周赛专栏

珂朵莉牛客小白月赛专栏

A. 跳棋Ⅰ

思路: 思维+数学

这个跳棋1比跳棋2难太多了, ^_^.

感觉这题，因为一枚子做炮架子，然后彼此互相做炮架子，这样应该是最快的。

形式地话，假设炮架距离为x, 类似这样的函数

f(x) = 2x + n / x + c, c为常数

如果求函数值最大，那x在[1, sqrt(n)]之间

可以三分求解，也可以枚举x在[1, sqrt(n)]

这题难在思维，还有尾巴的处理。

1. 枚举

时间复杂度 $\sqrt n$

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. 三分

时间复杂度 $O(logn)$ ，有待确定正确性

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. 棋盘变换

思路: 模拟+贪心

时间复杂度为 $O(nm)$

E. 区间递增

思路: 单调栈上二分

唯一涉及数据结构的题。

对于一个区间，每次剔除掉一个元素，使得表达式最小。那一定是形成了 $arr[i] > arr[i 1]$ 相邻逆序对。

最终稳定下来，一定构成一个非递减的子序列。

注意这里不是求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为所有人的生命总和

alt

最后这个公式一推，就能发现，就是从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);
            }
        }

    }

}