2023-08-26 19:44 已编辑東京大学 golang 发布于上海

关注

牛客练习赛114 解题报告 | 珂学家 | 贪心场 + 期望 + 线性基

前言

alt

只要坚信自己的道路，就无所谓天气是晴是雨。

整体评价

这场还是蛮难的，对我而言。C题写的有点变扭，到是D和F相对容易些。CDF都是基于贪心的解法，不过赛后看到了其他解法。G题属于高阶知识点，会的人觉得简单，不会的人基本没啥思路。

A. 光速签到

贪心，把大的数放在前面。

因为需要是10的倍数，而且允许前置0，所以只要保证至少一个0，就存在解了。

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 n = sc.nextInt();
        int[] slot = new int[10];
        for (int i = 0; i < n; i++) {
            slot[sc.nextInt()]++;
        }
        if (slot[0] == 0) System.out.println("-1");
        else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < slot[i]; j++) {
                    sb.append((char)(i + '0'));
                }
            }
            System.out.println(sb.reverse().toString());
        }

    }
}

B. 相信我,这真的是一个暴力!

如果知道 几何分布，那这题就非常的容易了。

先按照模拟来求解

${E=\sum_{i=1}^{i=n} i * p^{i-1} * (1 - p)} \tag{}$

$p=\sum_{i=1}^{i=3} a_i * b_i / 100 \tag{}$

如果 $p=1$ , 则没有解，因为永远是平局

求一个极端概率 $p=82/100$ , 则第i次的期望

$f(i)=i*p^{(i-1)}*(1-p),f(100) \le 1e^{-7} \tag{}$

因此理论上迭代100次就收敛了

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 a1 = sc.nextInt(), b1 = sc.nextInt(), c1 = sc.nextInt();
            int a2 = sc.nextInt(), b2 = sc.nextInt(), c2 = sc.nextInt();

            // 平局的概率
            int draw = a1 * a2 + b1 * b2 + c1 * c2;
            if (draw == 100) {
                System.out.println("Sorry,NoBruteForce");
            } else {
                double f = 1.0, p = draw / 100.0;
                double res = 0;

                // 迭代100次
                for (int i = 1; i <= 100; i++) {
                    res += i * f * (1 - p);
                    f = f * p;
                }
                System.out.println(res);

            }
        }
    }

}

如果知道几何分布，则期望 $E=1/(1-p) \tag{}$

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 a1 = sc.nextInt(), b1 = sc.nextInt(), c1 = sc.nextInt();
            int a2 = sc.nextInt(), b2 = sc.nextInt(), c2 = sc.nextInt();

            // 平局的概率
            int draw = a1 * a2 + b1 * b2 + c1 * c2;
            if (draw == 100) {
                System.out.println("Sorry,NoBruteForce");
            } else {
                double p = draw / 100.0;
                System.out.println(1.0/(1.0 - p));
            }
        }
    }

}

C. Kevin的七彩旗

这题的核心目标就是

构建1~M的连续序列，求最小的切片数

可以先做预处理，就是把连续递增的子数组, 从原数组中切出来。

现在的问题就演变成, 对于一个区间集合 $[s_i, e_i] \in S$ , 挑选最小的子集，能够构建 $1~m$ 的序列。

所以本质上，它是一个区间合并的最优化问题，先排序预处理。

方法一: 贪心构造

按左端点对区间进行排序

引入一个栈，栈中的元素是区间，自底向上彼此不相交，这一点很重要。

import java.io.BufferedInputStream;
import java.util.*;

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(), m = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            // 区间切割，保证 连续递增的子数组
            List<int[]> lists = new ArrayList<>();
            int j = 0;
            while (j < n) {
                if (arr[j] > m) {
                    j++;
                    continue;
                }
                int j2 = j + 1;
                while (j2 < n && arr[j2] == arr[j2 - 1] + 1 && arr[j2] <= m) {
                    j2++;
                }
                lists.add(new int[] {arr[j], arr[j2 - 1]});
                j = j2;
            }

            Collections.sort(lists, (a, b) -> {
                if (a[0] != b[0]) return a[0] < b[0] ? -1 : 1;
                if (a[1] != b[1]) return a[1] > b[1] ? -1 : 1;
                return 0;
            });

            Deque<int[]> deq = new ArrayDeque<>();
            for (int[] v: lists) {
                // 进行区间合并, 把之前小的进行覆盖
                boolean f = true;
                while (!deq.isEmpty()) {
                    int[] cur = deq.peekLast();
                    if (v[1] <= cur[1]) {
                        f = false;
                        break;
                    }
                    if (v[0] <= cur[0]) {
                        deq.pollLast();
                    } else {
                        break;
                    }
                }

                // 可以追加进去
                if (f) {
                    if (deq.isEmpty()) {
                        deq.offer(v);
                    } else {
                        deq.addLast(new int[] {Math.max(deq.peekLast()[1] + 1, v[0]), v[1]});
                    }
                }
            }

            // 进行最后的验证, 保证[1, m]完整
            int ans = deq.size();
            int next = 1;
            while (!deq.isEmpty()) {
                int[] cur = deq.pollFirst();
                if (cur[0] == next) {
                    next = cur[1] + 1;
                }
            }

            System.out.println(next > m ? ans : -1);
        }
    }

}

方法二：借助高级数据结构的DP

其实就是区间极值，像青蛙跳河系列的题

可以借助线段树，也可以借助非差分型的树状数组

import java.io.BufferedInputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Supplier;

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(), m = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            // 区间切割，保证 连续递增的子数组
            List<int[]> lists = new ArrayList<>();
            int j = 0;
            while (j < n) {
                if (arr[j] > m) {
                    j++;
                    continue;
                }
                int j2 = j + 1;
                while (j2 < n && arr[j2] == arr[j2 - 1] + 1 && arr[j2] <= m) {
                    j2++;
                }
                lists.add(new int[] {arr[j], arr[j2 - 1]});
                j = j2;
            }

            Collections.sort(lists, (a, b) -> {
                if (a[0] != b[0]) return a[0] < b[0] ? -1 : 1;
                if (a[1] != b[1]) return a[1] > b[1] ? -1 : 1;
                return 0;
            });

            RMQBIT<Integer> bit = new RMQBIT<>(m, () -> Integer.MAX_VALUE / 10, Math::min);
            for (int[] v: lists) {
                if (v[0] == 1) {
                    bit.set(v[1], 1);
                } else {
                    int r = bit.query(v[0] - 1, v[1] - 1);
                    bit.update(v[1], r + 1);
                }
            }

            // 进行最后的验证, 保证[1, m]完整
            int res = bit.query(m, m);
            System.out.println(res < Integer.MAX_VALUE / 10 ? res : -1);
        }
    }

    static
    public class RMQBIT<T> {
        int n;
        Object[] ori;
        Object[] arr;
        Supplier<T> e;
        BiFunction<T, T, T> op;

        public RMQBIT(int n, Supplier<T> e, BiFunction<T, T, T> op) {
            this.n = n;
            this.ori = new Object[n + 1];
            this.arr = new Object[n + 1];
            this.e = e;
            this.op = op;

            for (int i = 0; i <= n; i++) {
                this.ori[i] = e.get();
            }
            for (int i = 0; i <= n; i++) {
                this.arr[i] = e.get();
            }
        }

        public void setAll(T[] ori) {
            for (int i = 1; i <= n; i++) {
                this.ori[i] = this.arr[i] = ori[i];
                for (int j = 1; j < lowbit(i); j <<= 1) {
                    arr[j] = this.op.apply((T)arr[j], (T)arr[i - j]);
                }
            }
        }

        // O(log(n)), 前缀查询
        public T query(int p) {
            T res = (T)arr[p];
            while (p > 0) {
                res = this.op.apply(res, (T)arr[p]);
                p -= lowbit(p);
            }
            return res;
        }

        // 范围查询，操作时间复杂度, O(log(n)^2)
        public T query(int l, int r) {
            T ans = (T)ori[r];
            while (r >= l) {
                ans = this.op.apply(ans, (T)ori[r]);
                r--;
                while (r - l >= lowbit(r)) {
                    ans = this.op.apply(ans, (T)arr[r]);
                    r -= lowbit(r);
                }
            }
            return ans;
        }

        // O(log(n)), 符合单调性的更新
        public void update(int p, T v) {
            this.ori[p] = this.op.apply((T)this.ori[p], v);
            while (p <= n) {
                arr[p] = this.op.apply((T)arr[p], v);
                p += lowbit(p);
            }
        }

        // 操作时间复杂度, O(log(n)^2), 强制覆盖更新
        public void set(int p, T v) {
            this.ori[p] = v;
            for (; p <= n; p += lowbit(p)) {
                this.arr[p] = this.ori[p];
                for (int i = 1; i < lowbit(p); i <<= 1) {
                    this.arr[p] = this.op.apply((T)this.arr[p], (T)this.arr[p - i]);
                }
            }
        }

        int lowbit(int x) {
            return x & -x;
        }
    }

}

D. 长途的春天

可以先按值域统计，然后顺序遍历。

那核心的逻辑如何处理呢？

引入状态 $opt[i][j]$ 表示i值结尾，长度为j的个数

状态转移为

// 优先去填充长度为1~4的状态
for (int j = 1; j <= 4; j++) {
    opt[i][j+1] = opt[i - 1][j] + min(opt[i - 1][j], nums[i]);
    nums[i] -= min(opt[i - 1][j], nums[i]);
}

// 5是缩点，代表>=5的状态
opt[i][5] = min(opt[i - 1][5], nums[i]);
nums[i] -= min(opt[i - 1][5], nums[i]);

// 最后有剩下的，才新建长度为1的顺子
opt[i][1] = nums[i];

核心逻辑是这个。

那为啥不叫这个是DP，而是贪心呢，因为这边局部最优和全局最优一致。

所以时间复杂度为 $O(6n)$ , 空间复杂度为 $O(6n)$ ，不过这里空间上可以借助滚动数组优化。

如果值域很大怎么办？没事，离散化处理一样成立。

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

public class Main {

    static boolean solve(int n, int[] hash) {
        // 滚动数组优化
        int prev = 0, next = 1;
        int[][] opt = new int[2][6];

        for (int i = 1; i <= n; i++) {
            Arrays.fill(opt[next], 0);

            // 先填充长度为1~4的
            int v = hash[i];
            for (int j = 1; j <= 4; j++) {
                if (opt[prev][j] > 0) {
                    // 快速判定
                    if (opt[prev][j] > v) return false;
                    opt[next][j + 1] += opt[prev][j];
                    v -= opt[prev][j];
                }
            }
            // 填充5这个缩点
            if (v > 0 && opt[prev][5] > 0) {
                int d = Math.min(opt[prev][5], v);
                opt[next][5] += d;
                v -= d;
            }
            // 如果还有多余, 新建长度为1的顺子
            if (v > 0) {
                opt[next][1] = v;
            }
            prev = 1 - prev;
            next = 1 - next;
        }

        // 最后在判断一下尾巴
        for (int i = 1; i <= 4; i++) {
            if (opt[prev][i] > 0) return false;
        }
        return true;
    }

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

            int[] hash = new int[n + 1];
            for (int i = 0; i < n; i++) {
                int v = sc.nextInt();
                hash[v]++;
            }
            boolean res = solve(n, hash);
            System.out.println(res ? "YES" : "NO");
        }

    }

}

E. Kevin的抽奖黑幕

先占个位子

F. Kevin去砍树

这题很有意思，一开始往惯性上去思考，看看是否可以利用并查集，可无单调栈。

但是好想又不是，总差点意思。

观察后发现

最优值一定是从山峰点出发

这个其实是可以反证的，如果该点不是山峰点，那起左侧或者右侧一定有它大的点.

不失一般性，假定是左侧

$height[i - 1] > height[i]\ and\ g(i - 1) < g(i) \tag{1}$

按照流程约定，i点出发相当于失去了左侧的发展机会，而i-1点还包含了i在右侧的全部隐含收益。则 $g(i - 1) \gt g(i) \tag{2}$

1, 2互相矛盾，则反证出，山峰点一定是最优解的出发点。

而山峰点的覆盖范围，只包含它邻近的非山峰点。

左侧是递增的，右侧是递减的。

唯一的约束是左侧和右侧不能有相同高度的点。

所以这里，唯一的难点就在，那如何处理呢？

分别枚举左侧点和右侧点就行了，看看是否在另一侧存在。

其实每个点，都被枚举到了一次，山峰点代表区间，其他点枚举是相同点检测.

最后借助前缀和预处理，这题就呼之欲出了。

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

import java.io.BufferedInputStream;
import java.util.HashMap;
import java.util.Map;
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 n = sc.nextInt();

            int[] hs = new int[n];
            long[] ws = new long[n];

            // 前缀和预处理
            long[] prev = new long[n + 1];
            for (int i = 0; i < n; i++) {
                hs[i] = sc.nextInt();
            }
            for (int i = 0; i < n; i++) {
                ws[i] = sc.nextLong();
                prev[i + 1] = prev[i] + ws[i];
            }

            long ans = 0;
            for (int i = 0; i < n; i++) {

                // 山峰点判定
                if ((i == 0 && i + 1 < n && hs[i] >= hs[i + 1])
                        || (i > 0 && i + 1 < n && hs[i] >= hs[i - 1] && hs[i] >= hs[i + 1])
                        || (i > 0 && i + 1 == n && hs[i] >= hs[i - 1])
                ) {

                    // 寻找左侧的范围 (均摊为O(1))
                    int s = i, e = i;
                    Map<Integer, Integer> left = new HashMap<>();
                    Map<Integer, Integer> right = new HashMap<>();
                    while (s - 1 >= 0 && hs[s - 1] < hs[s]) {
                        s--;
                        left.put(hs[s], e);
                    }
                    while (e + 1 < n && hs[e + 1] < hs[e]) {
                        e++;
                        right.put(hs[e], e);
                    }

                    // 枚举左右侧，看是否在另一侧存在
                    long tmp = prev[i + 1] - prev[s];
                    ans = Math.max(ans, tmp);
                    for (int j = i + 1; j <= e; j++) {
                        if (left.containsKey(hs[j])) {
                            break;
                        }
                        tmp += ws[j];
                        ans = Math.max(ans, tmp);
                    }

                    tmp = prev[e + 1] - prev[i];
                    ans = Math.max(ans, tmp);
                    for (int j = i - 1; j >= s; j--) {
                        if (right.containsKey(hs[j])) {
                            break;
                        }
                        tmp += ws[j];
                        ans = Math.max(ans, tmp);
                    }
                } else {
                    ans = Math.max(ans, ws[i]);
                }
            }
            System.out.println(ans);
        }
    }

}

G. 图上异或难题

参考了大神的题解，先把边权转为点权

那问题就变成了数的集合，求子集的最大异或和。

借助线性基模板来求解

IO-WIKI上的线性基

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

public class Main {

    public static void insert(long[] vec, long v) {
        for (int i = 31; i >= 0; i--) {
            if ((v & (1 << i)) == 0) continue;
            if (vec[i]== 0) {
                vec[i] = v;
                return;
            }
            v ^= vec[i];
        }
    }

    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(), m = sc.nextInt();
            long[] ws = new long[n + 1];
            for (int i = 0; i < m; i++) {
                int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
                ws[u] ^= w;
                ws[v] ^= w;
            }

            // 构建向量基
            long[] vec = new long[32];
            for (int i = 1; i <= n; i++) {
                insert(vec, ws[i]);
            }

            // 获取子集异或和最大
            long ans = 0;
            for (int i = 31; i >= 0; i--) {
                ans = Math.max(ans, ans ^ vec[i]);
            }
            System.out.println(ans);
        }
    }

}