【咕】2025 Beijing WC (CNUHS) B

· · 生活·游记

2025/02/05 (贪心 凸性 拟阵)

P2970 [USACO09DEC] Selfish Grazing S，*橙。

$n\le5\times10^4$。

按右端点从小到大排序，依次考虑每一个区间，能选则选。复杂度 \mathcal{O}(n\log n)。

Code.

UVA10020 Minimal coverage。

实现来自 AzusidNya，拜谢。

$n\le10^5$。

按左端点从小到大排序，每次选出最长前缀。具体实现相当于每次求 l\le x 的最大的 r，因此不妨把右端点挂到左端点上，维护前缀最大值即可。有较多细节。复杂度 \mathcal{O}(n\log n)。

Code.

* 区间选择模型 III。

$n,m\le10^6$。

去掉所有包含其他区间的区间。区间按左端点从小到大排序。从小到大依次考虑每一个点，能不选则不选。复杂度 \mathcal{O}(n\log n)。

* 前缀匹配模型。

$n\le10^6$。

以任意顺序考虑左侧第 i 个点，选择右侧 p_i 之前编号最大的未匹配点与之匹配。复杂度 \mathcal{O}(n\log n)。

* 区间匹配模型。

$n,m\le10^6$。

从小到大考虑右侧每一个点，选择左侧能与之匹配的点中 r_i 最小的点进行匹配。复杂度 \mathcal{O}(n\log n)。

* 二维前缀匹配模型。

$n\le10^6$。

按 x 坐标扫描线，扫到右侧点时加入按 y 排序的 multiset，扫到左侧点时选择能匹配的 y 最大的右侧点。复杂度 \mathcal{O}(n\log n)。

* 带点权前缀匹配模型。

$n\le10^6$。

按点权从大到小考虑右侧每一个点，选择左侧能与之匹配的 p_i 最小的点与之匹配。复杂度 \mathcal{O}(n\log n)。

邻项交换模型。

给定 n 个 01 序列 a_i，将他们以任意顺序拼接，最小化逆序对数。

考虑何时交换相邻两段更优。令 s_0(i) 表示 a_i 中 0 的个数，s_1(i) 同理。

发现交换只影响两段之间的逆序对，段内部的逆序对仍然存在。因此，当且仅当 s_1(i)\times s_0(i+1)>s_1(i+1)\times s_0(i) 交换更优。变形得 \frac{s_1(i)}{s_0(i)}>\frac{s_1(i+1)}{s_0(i+1)}。不妨按 \frac{s_1(i)}{s_0(i)} 从小到大排序即可。

AT_agc023_f [AGC023F] 01 on Tree，*3148。

$n\le2\times10^5$。

不妨扩展成点权为 01 序列。由上题结论，对于当前全局 \frac{s_1(i)}{s_0(i)} 最小的点 x，一定会在父亲被删除后立即被删除。因此，不妨将其与其父亲合并。如此不断合并，当只剩一个点时即可得到答案。用堆和并查集维护。复杂度 \mathcal{O}(n\log n)。

Code.

* 最小化字典序模型。

CF626G Raffles，*3100。

$t$ 张彩票，将彩票分配到这些奖池中，需要保证你在第 $i$ 个奖池中押入的彩票数 $t_i$ 不能超过 $l_i$。对于第 $i$ 个奖池，中奖概率为 $\frac{t_i}{t_i + l_i}$。若中奖，则获得这个奖池的全部奖金 $p_i$。 $q$ 次事件，每次事件会使某个 $l_i$ 加 $1$ 或减 $1$。询问在最佳分配方案下获得的奖金总数的最大期望值。 $n,t,q\le2\times10^5$，$p_i,l_i\le 10^3$，答案精度误差 $\le10^{-6}$。

对于每个奖池，注意到 f_i(x)=\frac x{x+l_i}\cdot p_i 是凸的，因此答案即为这 n 个凸函数 (\min,+) 卷积的第 t 项。

对于一组询问，只需用堆维护每一个奖池多放一张期望的增量，模拟贪心即可。复杂度 \mathcal{O(q\cdot n)}。

* 可以证明，每次修改后 t_i 至多只会变化 1。因此，用堆维护已经放置的彩票中期望增量的最小值和能够放置的最大值即可。复杂度 \mathcal{O}((q+n)\log n)。

Code.

P3826 [NOI2017] 蔬菜，*黑。

题意较复杂，不多赘述。

* 一组询问实际上就是最大权匹配模型，按顺序交错排列这些菜即可转化为后缀匹配，可贪心的从后向前考虑每一天，售出当前价格最高的蔬菜。

CF1148F Foo Fighters，*3800。

思路来自 gcz，拜谢。

- 对于每个二元组，记 $f_i(s)$ 表示二进制下的 $s\text{ bitand }w_i$ 中 $1$ 的个数，则令 $v_i\gets(-1)^{f_i(s)}\cdot v_i$。 构造 $s$，使得操作前后 $\sum v_i$ 符号相反。 $n\le3\times10^5$。

不妨令 \sum v_i 初始为正。如果为负，将 v_i 全部取反是等价的。设 \text{ans}_s 表示选定 s 进行操作的答案，我们只需找到一个 \text{ans}_s>0 即可。

而根据题意，有：

\text{ans}_s=\sum_{i=1}^n(-1)^{f_i(s)}\cdot v_i

注意到：

\sum_{s=0}^{2^{62}-1}\text{ans}_s=\sum_{s=0}^{2^{62}-1}\sum_{i=1}^n(-1)^{f_i(s)}\cdot v_i=\sum_{i=1}^n\sum_{s=0}^{2^{62}-1}(-1)^{f_i(s)}\cdot v_i

又注意到，(-1)^{f_i(s)}+(-1)^{f_i(s\text{ bitxor }1)}=0。这是因为 s 和 s\text{ bitxor }1 仅在最低位有区别，因此二进制下 1 的个数一奇一偶。因此，有：

\sum_{s=0}^{2^{62}-1}\text{ans}_s=\sum_{i=1}^n\sum_{s=0}^{2^{62}-1}(-1)^{f_i(s)}\cdot v_i=\sum_{i=1}^n0=0

记 d(l,r)=\sum\limits_{i=l}^r\text{ans}_s。上面的观察告诉我们，d(0,2^{62}-1)=0。发现可以二分，d(0,2^{61}-1) 和 d(2^{61},2^{62}-1) 必定一正一负，并且负的区间中必定存在一个 \text{ans}_s<0。特别的，若两个区间和均为 0，由于 \text{ans}_0>0，因此左半区间一定存在 \text{ans}_s<0。于是，现在的问题变为如何快速计算 d(l,r)。

由于二分的特殊性，不难发现，我们所要计算的区间 [l,r] 都一定是二进制下一个前缀固定，剩下部分任取。与上面同理，我们不难得到：

d(l,r)=\sum_{i=1}^n\sum_{s=l}^r(-1)^{f_i(s)}\cdot v_i

因此，我们需要解决的问题是，对于每个 i，求所有二进制下前缀是某个定值、后面任取的 s 的 f(s,i) 之和。设固定的前缀长度为 t，若 w_i 在前 t 位外仍有 1，则显然贡献会两两抵消，答案为 0。否则直接计算即可。

复杂度 \mathcal{O}(n\log^2V)。

P10137 [USACO24JAN] Walking in Manhattan G，*蓝。

题意较复杂，不多赘述。

考虑奶牛走的路线必定如下图所示。

To be continue.

P4698 [CEOI 2011] Hotel，*紫。

To be continue.

To be continue.

P5290 [十二省联考 2019] 春节十二响，*紫。

Gym101221G Metal Processing Plant。

2025/02/06 (DP 及其优化)

CF1819D Misha and Apples，*2800。

设可重集 $T$，初始为 $\varnothing$。依次遍历每个集合，同时向 $T$ 中加入 $S_i$ 中的所有元素。若 $T$ 包含重复元素，则令 $T\gets\varnothing$。 钦定未确定的集合，求 $|T|$ 的最大值。 $n,m\le2\times10^5$。

令 f_i 表示能否使得 T 经过 S_i 后恰被清空。

显然，若 k_i=0，则 f_i=1。否则，考虑枚举上一次被清空的位置 j，若存在 j 满足：

则 f_i=1。

发现满足第二条的 j 是一段后缀，而满足第三条的 j 是一段前缀。* 具体求解可使用双指针和桶。我们只需要求这一段前缀和后缀的交中，是否存在 f_j=1。因此，我们只需维护 g_i 表示 i 之前最近的 f_j=1 的位置，判断是否有 g_r\ge l 即可。

求解答案时，我们找到最长的后缀 [l,n] 使得其中无重复元素。则

P8903 [USACO22DEC] Bribing Friends G，*绿。

$n,A,B\le2\times10^3$。

题目分为两步：选出一些人来贿赂，以及给这些人分配冰淇淋。

第二步是容易的，贪心的给 x_i 较小的人即可。按 x_i 从小到大排序。故必定存在一个分界点，前面只用冰淇淋，后面只用牟尼，而这个处于分界点的人可能需要混合使用冰淇淋和牟尼。

因此，不妨设 f_{i,j} 表示前 i 个人只用 j 个冰淇淋能得到的最大受欢迎度，而 g_{i,j} 表示后 i 个人只用 j 个牟尼能得到的最大受欢迎度。

统计答案时，枚举分界点处的第 i 个人用 a 个牟尼，计算出其还需要 b 个冰淇淋，则用 f_{i-1,B-b}+g_{i+1,A-a}+p_i 更新答案即可。

复杂度 \mathcal{O}(n^2)。

Code.

UVA10559 方块消除 Blocks，*紫。

长为 n 的序列 a_i，消除长为 x 的连续同色段的分数为 x^2。求最大分数。

考虑一个朴素区间 dp，设 f_{l,r} 表示区间 [l,r] 的最大答案。转移时考虑枚举最后一次消除的编号，则有：

f_{l,r}=\max_{l\le i_1<i_2<\cdots<i_k\le r}\{f_{l,i_1-1}+f_{i_1+1,i_2-1}+\cdots+f_{i_k+1,r}+k^2\}

P3592 [POI 2015] MYJ，*紫。

$n\le50$，$m\le4\times10^3$。

设 f_{l,r,k} 表示只考虑 [a_i,b_i]\subseteq[l,r] 的约束，且 [l,r] 中的最小值至少为 k 时的最大收益。

转移时枚举值为 k 的位置 p，即：

f_{l,r,k}=\max_{l\le p\le r}\{f_{l,p-1,k}+f_{p+1,r,k}+\text{cnt}(l,r,p,k)\cdot k\}

其中 \text{cnt}(l,r,p,k) 表示满足以下条件的三元组数量：

不妨离散化，仅需考虑 k 为 c_i 之一。

如何计算 \text{cnt} 函数？考虑容斥，不妨预处理 s_{l,r,k} 表示满足以下条件的三元组数量：

则有：

\text{cnt}(l,r,p,k)=s_{l,r,k}-s_{l,p-1,k}-s_{p+1,r,k}

如何处理 s 数组？显然可以差分，将 c_i\ge k 转化为 c_i=k。此时即为一个二维数点问题，无需数据结构优化，直接暴力即可。复杂度 \mathcal{O}(n^2m)。

总复杂度 \mathcal{O}(n^3m)。

CF1093F Vasya and Array，*2400。

同 AT_arc169_c [ARC169C] Not So Consecutive。

有长为 n 的值域为 [1,k] 的序列 \{a_n\}，其中有些位置未填。填入这些数使得不存在长为 l 的连续同色段，求方案数。对 998244353 取模。

设 f_{i,j} 表示考虑了前 i 个数并且 a_i=j 的合法方案数。令 s_i=\sum\limits_{1\le j\le k}f_{i,j}。

根据定义，若 a_i\ne-1，则 f_{i,a_i}=1。

对于其他的 a_i，若 $$

P5664 [CSP-S2019] Emiya 家今天的饭，*蓝。

P3195 [HNOI2008] 玩具装箱，*紫。

To be continue.

斜率优化

P1912 [NOI2009] 诗人小G，*紫。

决策单调性

CF868F Yet Another Minimization Problem，*2500。

P10197 [USACO24FEB] Minimum Sum of Maximums P，*黑。

P3620 [APIO/CTSC2007] 数据备份，*蓝。

凸优化。

2025/02/07 (模拟赛 树)

CF1632E2 Distance Tree (hard version)。

2025/02/08 (链剖 树上启发式合并 Prufer 点分治 边分治)

CF685B Kay and Snowflake。

P3345 [ZJOI2015] 幻想乡战略游戏。

P4211 [LNOI2014] LCA。

CF1009F Dominant Indices。

BZOJ3252 攻略。

P4292 [WC2010] 重建计划。

CF600E Lomsat gelral。

P1600 [NOIP 2016 提高组] 天天爱跑步。

P6596 How Many of Them。

P3806 【模板】点分治 1。

P2495 [SDOI2011] 消耗战。

P6329 【模板】点分树 | 震波。

P4886 快递员。

U402226 [HNJX2021D5T1] 下落的数字。

P7518 [省选联考 2021 A/B 卷] 宝石。

LOJ6669 Nauuo and Binary Tree。

P9340 [JOISC 2023 Day3] Tourism。

2025/02/09 (模拟赛 线段树)