前言

整体评价

比赛刚开始的时候，看到清一色的英语题目，就有种不祥的预感，果然......

感觉这场练习赛好难，在知识范围内是前四题，但是实际能ac 4题的却很少，是真的难。

A. Mountain sequence

要求构建一个山峰数组，求累计的方案总数

其实这题是构造题，按照要求确定山峰(最大值)后, 然后决策其他的数往那放置。

可以分组(按值)排序，然后从大到小放置。

对于某组(size=m), 则左右侧{(0, m), (1, m - 1), ..., (m, 0)} 总共m+1种方式。

所以这题显然易见，就是除最大数以外的组大小累乘。

import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int kase = sc.nextInt();
        while (kase-- > 0) {
            int n = sc.nextInt();
            TreeMap<Integer, Integer> hash = new TreeMap<>();
            for (int i = 0; i < n ;i++) {
                int v = sc.nextInt();
                hash.merge(v, 1, Integer::sum);
            }

            // treemap是保序的
            int[] arr = hash.values().stream().mapToInt(Integer::valueOf).toArray();

            long mod = 998244353l;
            long ans = 1l;
            // 这边需要把最大数的组(山峰)去掉, 所以枚举到[0, arr.length - 1)
            for (int i = 0; i < arr.length - 1; i++) {
                int m = arr[i];
                ans = ans * (m + 1) % mod;
            }

            System.out.println(ans);
        }
    }

}

B. Antiamuny wants to leaern binary search again

既然是通过次数来求可能的目标值，那完全可以逆序模拟二分.

1. 模拟二分+贪心

二分区间的时候，右侧的区间更大一些，所以尽量往右侧寻找。

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 kase = sc.nextInt();
        while (kase-- > 0) {
            int l = sc.nextInt(), r = sc.nextInt();
            int cnt = sc.nextInt();

            int ans = -1;
            while (l <= r) {
                int m = l + (r - l) / 2;
                cnt--;
                if (cnt == 0) {
                    ans = m;
                    break;
                }
                // 贪心走右侧
                l = m + 1;
            }
            System.out.println(ans);
        }
    }

}

2. 记忆化

因为这题范围为, 而

这题也可以用dp的方式求解，不过记忆化的话，更容易书写

, m表示长度，s表示次数，存在的情况对应的数字(偏移)

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    static Integer[][] opt = new Integer[100_0001][21];

    static int dfs(int l, int r, int z) {
        if (r < l) return -1;

        int span = r - l + 1;
        int mid = l + (r - l) / 2;
        if (z == 1) {
            return mid;
        }

        if (opt[span][z] != null) {
            return opt[span][z] == -1 ? -1 : opt[span][z] + l;
        }

        int r1 = dfs(l, mid - 1, z - 1);
        if (r1 != -1) {
            opt[span][z] = r1 - l;
            return r1;
        }

        int r2 = dfs(mid + 1, r, z - 1);
        if (r2 != -1) {
            opt[span][z] = r2 - l;
            return r2;
        }

        opt[span][z] = -1;
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int kase = sc.nextInt();
        while (kase-- > 0) {
            int l = sc.nextInt(), r = sc.nextInt();
            int cnt = sc.nextInt();
            System.out.println(dfs(l, r, cnt));
        }
    }

}

C. Find the maximum slope

如果把这个公式，看做斜率k=(arr[i] - arr[j])/(i-j)

那这个斜率极值(最大/最小)，必然是相邻。

反证法，假如不是相邻的元素构成的斜率最大。

结合数形，可以发现，除非在一条直线上，否则必然能找到一条更大的斜率.

因此，我们可以证明：

最大值，一定是相邻元素构造的。

那剩下的事情，就简单很多了。

按要求构建相邻两元素的差分数组。

对于区间修改，只会影响区间的边界两个点差分值。

import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.TreeMap;

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();
        }

        // treemap是维护差分的最大值
        TreeMap<Integer, Integer> range = new TreeMap<>();
        int[] diff = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            diff[i] = arr[i] - arr[i + 1];
            range.merge(Math.abs(diff[i]), 1, Integer::sum);
        }

        System.out.println(range.lastKey());
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() - 1, r = sc.nextInt() - 1;
            int x = sc.nextInt();

            // 区间修改只会影响2个端边界
            if (l > 0) {
                range.computeIfPresent(Math.abs(diff[l - 1]), (a, b) -> b > 1 ? b - 1 : null);
                diff[l - 1] -= x;
                range.merge(Math.abs(diff[l - 1]), 1, Integer::sum);
            }

            if (r + 1 < n) {
                range.computeIfPresent(Math.abs(diff[r]), (a, b) -> b > 1 ? b - 1 : null);
                diff[r] += x;
                range.merge(Math.abs(diff[r]), 1, Integer::sum);
            }
            System.out.println(range.lastKey());
        }

    }

}

这题，出题者真的太贼了，故意引入浮点数，限定值域大小，不知道多少小伙伴直接被带偏了。

D. Genealogy in the trees

因为涉及树上的祖先判定，因此dfn序是免不了的。

dfn序之后，该如何求解，成了这题的关键。

这题应该非常的经典，一种思路借鉴了何老师的做法，时间序模拟操作，树状数组支持区间查询。

另一种是 树上启发式合并，需要AVL树的支持。

1. 树状数组

预处理dfn时间序，每个对都有一个start, end时间戳

按照离线计算的思路，再构建一个操作序列

• 点对按p，的时间序start加入，按end离开, 进行bit操作
• 查询按a，的时间点，进行bit查询

这题数据量有点大，需要用快读模板。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    static class BIT {
        int n;
        int[] arr;
        public BIT(int n) {
            this.n = n;
            this.arr = new int[n + 1];
        }
        public void update(int p, int d) {
            while (p <= n) {
                arr[p] += d;
                p += p & -p;
            }
        }
        public int query(int p) {
            int res = 0;
            while (p > 0) {
                res += arr[p];
                p -= p & -p;
            }
            return res;
        }
    }

    static class Solution {

        int timestamp = 0;
        int[] start, end;

        int n;
        List<Integer> []g;

        int[] solve(int n, int[][] es, int[][] ms, int[][] qs) {
            this.n = n;
            this.start = new int[n + 1];
            this.end = new int[n + 1];

            this.g = new List[n + 1];
            Arrays.setAll(g, x -> new ArrayList<>());

            for (int i = 0; i < es.length; i++) {
                int u = es[i][0], v = es[i][1];
                g[u].add(v);
                g[v].add(u);
            }

            // 有根树，root=1
            dfs(1, -1);

            // 离线计算，转换为操作序列
            // 三元组 (time, type, time/id)
            List<int[]> ops = new ArrayList<>();
            for (int i = 0; i < ms.length; i++) {
                int p = ms[i][0], q = ms[i][1];
                ops.add(new int[] {start[p], 1, start[q]});
                ops.add(new int[] {end[p], -1, start[q]});
            }
            for (int i = 0; i < qs.length; i++) {
                int a = qs[i][0];
                ops.add(new int[] {start[a], 0, i});
            }

            ops.sort((x, y) -> {
                int r = Integer.compare(x[0], y[0]);
                if (r != 0) return r;
                return -Integer.compare(Math.abs(x[1]), Math.abs(y[1]));
            });

            int[] res = new int[qs.length];
            BIT bit = new BIT(timestamp);
            for (int[] e: ops) {
                int type = e[1];
                if (type == 0) {
                    int idx = e[2];
                    int b = qs[idx][1];
                    res[idx] = bit.query(end[b]) - bit.query(start[b] - 1);
                } else {
                    bit.update(e[2], e[1]);
                }
            }

            return res;
        }

        // 做dfn序
        void dfs(int u, int fa) {
            start[u] = ++timestamp;
            for (int v: g[u]) {
                if (v == fa) continue;
                dfs(v, u);
            }
            end[u] = ++timestamp;
        }

    }

    public static void main(String[] args) {
        AReader sc = new AReader();
        int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();

        int[][] es = new int[n - 1][2];
        for (int i = 0; i < n - 1; i++) {
            es[i][0] = sc.nextInt();
            es[i][1] = sc.nextInt();
        }
        int[][] ms = new int[m][2];
        for (int i = 0; i < m; i++) {
            ms[i][0] = sc.nextInt();
            ms[i][1] = sc.nextInt();
        }
        int[][] qs = new int[q][2];
        for (int i = 0; i < q; i++) {
            qs[i][0] = sc.nextInt();
            qs[i][1] = sc.nextInt();
        }

        Solution solution = new Solution();
        int[] res = solution.solve(n, es, ms, qs);
        System.out.println(Arrays.stream(res).mapToObj(String::valueOf)
                           .collect(Collectors.joining("\n")));
    }

    static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }
        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }
        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }
        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
        
    }

}

2. 启发式合并

先占个坑，需要名次树支持

dfn时间序做预处理

离线计算做法，每个节点有两个名次数，一个维护前缀(节点的start时间戳)，一个维护后缀(节点的end时间戳)

自底向上，做启发式合并

很像LCA的tarjan解法，即在dfs过程中，离线把结果计算了。

前缀rank - 后缀rank

E. High contrast pattern

F. Jewel maximizing magic

写在最后