Posts by hostmaster

概述 Fractional Cascading 算法，国内多译为“分散层叠算法”，用于解决在多个有序序列中的查找问题，单次复杂度为线性。Fractional Cascading 算法思想与跳表类似。 此算法思想可以用在一些图论题中 问题 给出 $k$ 个长度为 $n$ 的有序数组 $a_{i, j}$。 现在有 $q$ 个查询 : 给出数…

题意 给定无向带权连通图，每条边是黑色或白色，求恰好有 $need$ 条白边的生成树最小权。 $n = 5 \times 10^4, m = 10^5$ 题解 二分一个 $k$，把所有白边的权值都加上 $k$，以达到调整最小生成树的白边数量。 注意有个坑，因为有边权相等的情况，所以跑生成树是有可能取不到刚好 $need$ 的。 代码 vo…

题意 现在给出 $n, A, B, C$，求有多少个长度为 $n$ 的数组 $w$ 满足存在 $a < b < c < d$ 使得 $w_a + w_{a + 1} + \ldots + w_{b-1} = A$，$w_b + w_{b + 1} + \ldots + w_{c-1} = B$，$w_c + w_{c+1} + \ldots + w_d = C$…

题意 给定长度为 $n$ 的数组 $a$，计数： $1 \leq i < j < k < l < m$ 使得 $a_j < a_i < a_k, a_l < a_m < a_k$ $n = 5 \times 10^5$ 题解 首先注意到左右两边是对称的，于是只需要算黑色部分。 还是比较难求，可以考虑反着求。 为了方便描述，我们把图中 $i, j, k$…

题意 给定一个长度为 $n$ 的数组 $a$，要求选出若干区间，每段区间长度不超过 $k$，求被选出的数的和的最大值。 $n = 10^6, 0 \leq a_i \leq 10^9$ 题解 脑抽了，一下没想出来。 设 $f_i$ 表示 只看数组中 $1$ 到 $i$ 的答案，且要求 $a_i$ 必须选。 $f_i$ 可以由前面的一段转移…

题意 给定 $n, m$ 和长度都为 $m$ 的数组 $L$ 和 $R$。 要求选出 $m$ 个数，第 $i$ 个数在 $\left[L_i, R_i\right]$ 里，使得他们的和为 $n$。 求出方案数对 $998244353$ 取模的结果。两种方案不同，当且仅当某个数的值不同。 $1 \leq n \leq 10^9, 1 \leq m \leq 20, 0 \leq L_i \leq R_i \leq 10^9$…

题意 给定整数 $n, L, R$，长度都为 $n$ 的数组 $a$ 和 $b$。选择一段长度在 $\left[L, R\right]$ 的区间，使得 $\dfrac{\sum a}{\sum b}$ 最大，求最大值。 $1 \leq n \leq 10^5$ 题解 好像是个经典的 01 分数规划。首先二分 $x$，现在要检查是否有一段区…

题意 给定 $n, L, R$ 和一个长度为 $n$ 的数组 $a$，要求选出 $L$ 到 $R$ 个数，使得选出的数组成的可重集的方差最小。 $1 \leq n \leq 2 \times 10^5, a_i \leq 10^3$ 题解 可以先将 $a$ 排序。 众所周知，方差是用来衡量混乱程度的。我们选的数一定是排序后数组的一段区间。…

题意 给定长度为 $n$ 的 01 串 $a$，并以如下方式排序： 每次随机选定 $i$ 和 $j$，满足 $i < j$，如果 $a_i > a_j$，就交换 $a_i$ 和 $a_j$，否则什么也不干。 问期望操作次数，对 $998244353$ 取模。 $1 \leq n \leq 2 \times 10^5$ 题解 假设一共有 $k$…

前言 放寒假啦，为了庆祝买了一个 Mac (＾－＾)V 总体用起来还是比较流畅的，性能也还算可以，就是价格不太友好。 Minecraft 这个还算简单，直接去 这里 下载一个 ARM 原生的 JDK 然后装 HMCL 等客户端即可。实测画质全部拉到满的话可以跑到 100 多帧的样子。 关于 GPTK 好像需要一个开发者账号（需要氪金），只…