（补档）IOI2020国家集训队作业 Part 2

· · 算法·理论

来自 2023.3.3，不知道为啥当时没公开，今天突然翻到，现在放出来希望能对后人有用。

IOI2020国家集训队作业 Part 2

我会给每个题一个 1\sim16 的主观难度评分。

如果一个题的定数是 114514，那么说明这题是计算几何或者多项式，我跑路了。

51.CF627E Orchestra(12)

直接枚举两行然后中间双指针是 O(rc\min(r,c)) 的，但是考虑这里 n 和 r,c 同阶而且 k 非常小，可以枚举上边界，对下边界扫描线，同时动态维护每一列作为右端点的贡献。

这样加入一个点之后只会有相邻的 O(k) 个点的贡献发生变化，于是可以暴力修改。

时间复杂度 O(r^2+rkn)。

52.CF639E Bear and Paradox(9)

火药桶锐评：每一步都典的惊人/aiq

假设有两个元素 p_1,p_2，如果 p_1 在前贡献是 p_1(1-\frac{ct_1}T)+p_2(1-\frac{ct_1+ct_2}T)，如果 p_2 在前贡献是 p_2(1-\frac{ct_2}T)+p_1(1-\frac{ct_1+ct_2}T)，两者作差可以得到 \Delta=\frac{c(p_1t_2-p_2t_1)}{T}。

由于 c\geq 0 所以 \Delta 的正负性和 c 无关，也就是说如果 p_1t_2-p_2t_1\neq 0，那么二者的相对顺序是固定的。

反之，如果 p_1t_2=p_2t_1，那么二者的顺序可以随意交换。

这告诉我们最优解中分成若干个块，块间顺序一定，块内可以随意交换。

接下来考虑没有悖论的限制，预处理出来每个块的时间前缀和 sum，那么在第 i 个块中的题目 j 对应的函数自变量取值范围就是 [sum_{i-1}+t_j,sum_i]。由于斜率恒负，所以函数在 c=sum_i 取最小值，c=sum_{i-1}+t_j 取最大值。

我们要求在任意排列下均不存在悖论，先二分答案 c，然后按照 p 从小到大扫一遍所有的题目，对于 p 相同的题目一起处理，直接维护一下前面所有题目能取到的最大值，和当前题目的最小值比较一下即可。

时间复杂度 O(n\log \epsilon^{-1})。

53.CF639F Bear and Chemistry(12)

二合一。/tuu

点集内任意两点能互相到达，等价于所有点在一个点双里面。

先对原图缩点，然后有了一棵森林，对于每次询问直接把这些点拉出来建虚树（也许这里应该叫虚森林罢），跑一遍 tarjan 即可。

时间复杂度 O(n+\sum|V|\log\sum|V|)。

54.CF666D Chain Reaction(5)

问号。

暴力。暴力。暴力。先暴力枚举每个点的移动方向的横竖，再暴力分类讨论：

求出来一组坐标之后大力枚举全排列匹配每一个点算答案。

令 n=4，时间复杂度 O(2^nn!\log V)。

不是很懂为啥这题 t=50，也许还有其他更暴力的做法罢。/jy

55.CF666E Forensic Examination(8)

没啥营养的典题。

把 s 和所有 t_i 建一个广义 SAM，询问离线之后直接倍增一下找到对应点挂在树上，然后问题就变成了子树内区间颜色数最值，直接线段树合并。

时间复杂度 O((|s|+\sum|t|+q)\log m+q\log(|s|+\sum |t|))。

56.CF671D Roads in Yusland(13)

方法一

记 dp_{i,j} 表示 i 子树内全部覆盖，溢出的部分覆盖到的点最小深度是 j 的最小花费，f_i=\min\limits_{j=1}^{dep_i}dp_{i,j}，也就是覆盖子树内所有点的最小花费，转移的时候 dp_{i,j}=\sum\limits_{k\in son_i}f_k+\min(dp_{k,j}-f_k)，然后枚举起点是 i 的路径更新一下，直接做是 O(n^2) 的。

考虑优化，这个东西其实有点类似 NOI2020 命运 那个题，可以线段树合并维护，具体来说需要支持线段树合并，区间加，区间取 \min，维护两个标记是可以维护的，但是空间可能会被卡，写点内存回收说不定就过了。

草，怎么洛谷题解区有老哥说没写内存回收的线段树合并冲过去了啊。/kx

方法二

线性规划对偶，有趣。

大概意思是说 \max\{c^T\cdot x|Ax\leq b\}=\min\{b^T\cdot y|A^Ty\geq c\}

~~我知道你很急但是你先别急让我先急，~~我知道这个看起来很抽象，我们来一点说人话的例子。 > 某工厂有两种原料A、B，而且能用其生产两种产品： > 1、生产第一种产品需要2个A和4个B，能够获利6； > 2、生产第二种产品需要3个A和2个B，能够获利4； > 此时共有100个A和120个B，问该工厂最多获利多少？ > > 用数学表达式描述如下： > 已知： > $2\times x_1+3\times x_2\leq 100
4\times x_1+2\times x_2\leq 120

求：

手算一下可得答案是 $200$。

工厂除了拿原料生产成产品卖掉这条出路外，还有一种方法是直接将原料卖掉。但是要求把原料卖掉赚的钱比生产成产品赚的钱多。那么最低可以接受多少的价格呢？

用数学表达式描述如下： 已知：

2\times y_1+4\times y_2\geq 6 3\times y_1+2\times y_2\geq 4

求：

手算一下可得答案也是 $200$。

这样线性规划对偶就有了一个比较直观的感觉了。

回到这题，原题是个最小化问题，直接大力套到右边的式子上：

然后带到左边，显然 x 是个 n-1 行行向量。考虑这个 x 向量的实际意义，相当于给每条边一个权值。

那么问题变成要给每条边一个边权，要求每条链上的边权和不超过链的权值的前提下最大化所有边的边权和。

这个问题是可以贪心解决的，显然在更深的边加边权是不劣的，于是直接维护每条链剩余的权值即可，需要一个可以维护全局减的可并堆。

时间复杂度 O(n\log m)。

57.CF671E Organizing a Race(15)

这位更是重量级。

记 pre_i=\sum\limits_{j=1}^iw_{j-1}-g_{j-1},suf_i=\sum\limits_{j=1}^iw_{j-1}-g_j。

先考虑正向，当 pre_i<pre_k 的时候我们就开不过去 k 了，这个可以单调栈求出来每个 i 对应的 k。

然后每次直接贪心在每段的左端点加上对应的差值就可以，这样求出正着走过去要加上的值 g(l,r)。

但这样不一定能反着回来，考虑我们操作完之后会对 suf 产生影响得到新的数组 suf'，这个时候因为正着已经能过去了，反着不够的我们全加到 r 上就行。

同理当 suf'_k<suf_i 的时候我们没法从 i 走过这个点，定义 f(l,r)=\min\limits_{i=l}^{r-1}suf'_i，那么我们要在 r 加上的值就是 \max(0,suf'_r-f(l,r))。

于是我们要求 h(l,r)=g(l,r)+\max(0,suf'_r-f(l,r))\leq k，显然这等价于 h'(l,r)=g(l,r)+suf'_r-f(l,r)\leq k。

给每个 i 向单调栈求出来的 k 连边后形成一棵森林，建个虚根后 dfs，考虑加入一个点的贡献。

首先 g(l,r) 会有一段后缀加，然后 suf'_r 会有后缀减，但根据定义你发现 g(l,r)+suf'_r=pre_r+suf_r，所以实际上二者的贡献抵消了。

剩下的是 f(l,r) 会对 suf' 有一个后缀减的贡献。

所以我们要维护的东西就是 suf_r-f(l,r)，要求的是满足 \max(pre_r,suf_r-f(l,r))\leq k 的最大的 r。

先二分出来 pre_r\leq k 的区间，记右端点是 r'，给 [1,l) 偏移正无穷，[r',n] 偏移负无穷，这样就变成全局查询了，然后维护一棵类似楼房重建的单侧递归线段树，具体参见粉兔的博客。

时间复杂度 O(n\log^2 n)。

58.CF643D Bearish Fanpages(9)

这题为啥看了提示才想出来啊，怄火。

类似树剖那个维护所有轻儿子的套路，我们维护所有儿子的贡献，和儿子数量，并在每个点用 multiset 维护所有儿子除去自己的贡献后的最值，再用一个 multiset 维护全局最值（把每个点的最大最小值加上自己的贡献放进去）。

这样修改的时候只会影响 f_{f_{f_x}},f_{f_x},f_x,x,f_{f_y},f_y,y 七个点，直接把暴力修改即可。

时间复杂度 O((n+q)\log n)。

59.CF643F Bears and Juice(12)

大概是个经典题，因为他被两次抬到山东省集的模拟赛。/jy

虽然有一次被魔改成了交互题。

信息论入门题。

枚举天数 k，考虑最后的局面（也就是我们得到的信息）。我们可以把所有熊的状态抽象成一个长度是 n 的序列 a，a_i 的值域是 [0,k]，其中 0 表示这只熊最后是醒着的，否则表示这只熊在第 a_i 天睡着了。额外的限制是这个序列最多有 \min(p,n-1) 个不是 0 的值。

那么枚举有多少个不是 0 的数，本质不同的序列就有 \sum\limits_{i=0}^{\min(p,n-1)}k^i\dbinom ni 种，显然答案不会超过这个值，但答案是否就是这个值呢？考虑构造一种方案使得一种酒的位置和一个序列一一对应。

发现确实是可以构造的。考虑先给每种酒的位置 k 钦定一个对应的序列 a_k，在第 j 天，如果第 i 只熊还醒着，那么他会喝下所有 a_{k,i}=j 的位置的桶里的液体。

这样构造的正确性是显然的，如果这只熊今天睡着了说明对应序列 a_{k,i}=j，否则 a_{k,i}\neq j，这样对于每个位置我们都能根据熊最终的状态得出序列对应位置的值，由于序列和酒的位置之间是双射，所以可以唯一确定一个答案，因此答案的上界就是答案的精确值。

接下来考虑怎么算，发现这题要求的是自然溢出，算组合数的时候不一定有逆元。但自然溢出等价于对 2^{32} 取模，所以直接套上对 p^k(p\in\mathrm{prime}) 取模的方法，质因子 2 拿出来单独处理即可，剩下的部分扩欧计算逆元。

预处理组合数之后就可以直接暴力 O(pq) 扫一遍算答案了，时间复杂度 O(p^2\log p+pq)，比大部分题解的暴力约分复杂度优秀一点。虽然不是复杂度瓶颈。

60.CF643G Choosing Ads(10)

发怒。

类似区间找绝对众数的那个方法，线段树维护每个区间可以成为答案的数，合并的时候遇到相同的合并，否则互相抵消然后扔掉变成 0 个的即可。

时间复杂度 O(\lfloor\frac p{100}\rfloor^2n\log n)。

61.CF679E Bear and Bad Powers of 42(12)

调了一年，怄火。

粗略估计一个最差的上界，就是所有操作都在全局加，估算值域 V 在 10^{14} 级别。

没有区间赋值的话可以直接使用 segment tree beats 维护每个位置的值到 $42^{\lceil\log_{42}a_i\rceil}$ 的距离，如果区间内操作后有 $\lceil\log_{42}a_i\rceil$ 的值发生变化就暴力递归进去修改。如果一次操作结束以后全局 $\min$ 是 $0$ 说明有数字恰好是 $42$ 的幂次，就再操作一遍。 考虑区间赋值，显然直接 segment tree beats 是不行的，但是考虑每次区间赋值连续段数量的变化量是 $O(1)$ 的，而线段树是可以直接打标记维护连续段的，于是直接给赋值的区间打标记，表示这段区间值全部一样，递归到有标记的区间直接当做叶子修改之后返回即可。 这里有一些细节，存在区间覆盖标记的时候不应该有区间加标记，因此要注意标记的下放顺序。 时间复杂度 $O(n\log n\log_{42}V)$。 ## 62.CF685C Optimal Point(7) 众所周知 $k$ 维曼哈顿距离可以转化成 $2^{k-1}$ 维切比雪夫距离，先转一下然后二分答案，剩下的工作是求一个不等式组有没有解，分类讨论即可。 时间复杂度 $O(n\log V)$。 ## 63.CF696F ...Dary!(114514) 糗大了，计算几何。 ## 64.CF698D Limak and Shooting Points(8) WA on test 107/kx 这个 $k$ 实在是太小了，感觉不枚举一下全排列都对不起这个数据范围。 枚举一手全排列 $p$，然后判断这个序列能不能~~射爆~~击中第 $i$ 个怪物。 钦定 $p_1$ 是击中 $i$ 的，但是前面可能会有障碍，于是前面的障碍直接暴力递归就行了，分别钦定用 $p_2,p_3\cdots,p_k$ 击中。 时间复杂度 $O(k!kn)$。 ## 65.CF700E Cool Slogans(11) 感觉自己又不会后缀数据结构了，非常的安格瑞啊！ 题意等价于求所有子串的 border 数量最大值，因为显然如果匹配两次后面有多出来的部分去掉是不劣的。 建个 SAM，如果 $A$ 是 $B$ 的 border 等价于 $A$ 在自动机和 parent 树上都能走到 $B$，晚上和军师讨论的时候他告诉我大力图剖一下应该是能做的，我感到非常谔谔。 还是看看远方的线段树合并吧家人们。我们扔掉自动机，他是个 DAG，太谔谔了。parent 树就很好，来看看树上怎么维护。如果 parent 树上 $A$ 是 $B$ 的祖先，显然 $A$ 的 $\mathrm{endpos}$ 集合是 $B$ 的超集，也就是说二者至少有一个公共 $\mathrm{endpos}$，就是右端点（记为 $pos$），这个在建 SAM 的时候就可以很简单的维护出来，所以我们只要找有没有出现第二次就好了。显然可能出现答案的区间是 $[pos_B-|B|+|A|,pos_B-1]$。 那么我们可以主席树合并预处理出来每个点的 $\mathrm{endpos}$，直接查就完了。 这样暴力枚举祖先后代的话还是个暴力，考虑压缩一下状态，记 $dp_k$ 表示 $k$ 及其祖先的最大匹配长度，$g_k$ 表示 $dp_i=dp_k$ 的深度最浅的 $i$，这样点 $k$ 贪心匹配 $g_{fa_k}$ 肯定是不劣的，直接 dfs 一遍就得到答案了。 时间复杂度 $O(n\log n)$。 ## 66.CF704B Ant Man(5) 集训队作业居然有 *2500 的题/jy/jy/jy 把贡献拆一下，$f(i,j)$ 中 $i,j$ 的贡献是独立的，很方便我们分别考虑计算。 具体来说贡献有四类： - 左边比 $i$ 大：$-x_i+b_i$； - 左边比 $i$ 小：$x_i+c_i$； - 右边比 $i$ 大：$-x_i+d_i$； - 右边比 $i$ 小： $x_i+a_i$。 然后按照 [JOI 摩天大楼](https://loj.ac/p/2743) 那个题的套路来做，$dp_{i,j}$ 表示填了前 $i$ 个数，当前有 $j$ 个连续段的最小值。 从小到大加入数字，转移分三类讨论： - 当前点是 $s$，分成新开一段（右边比他大）和接在一段边上（右边比他小）两种； - 当前点是 $e$，分成新开一段（左边比他大）和接在一段边上（左边比他小）两种； - 当前点是普通点，分成新开一段（左右都比他大），合并两段（左右都比他小），接在一段左边（左边比他大，右边比他小），接在一段右边（左边比他小，右边比他大）四种。 这里有一个坑点是有些状态是不合法的，具体来说有下面五种，要特判掉： - 数组越界了的； - 合并成 $0$ 段的； - $s,e$ 都已经填了，当前点不是 $n$ 却已经缩成了一段的； - 只填了 $s$，只有一段却接在了这段左边的； - 只填了 $e$，只有一段却接在了这段右边的。 时间复杂度 $O(n^2)$。 ## 67.CF704C Black Widow(11) 特判掉单独一个字母或者两个字母相同的表达式，把表达式中两个变量连边，由于每个变量最多出现两次，所以每个联通块不是链就是环，链直接顺着 dp 一遍，环随便枚举一个点的取值转化成链，然后总的再 dp 一下。 时间复杂度 $O(n)$。 ## 68.CF704D Captain America(12) 假设 $r\leq b$，如果没有限制我们肯定都涂红。 考虑限制，把每个点从行向列连边，涂红看做流，每行每列的限制相当于流量在 $[\lceil\frac{cnt-d}2\rceil,\lfloor\frac{cnt+d}2\rfloor]$ 之间，于是直接跑上下界最大流就做完了。 时间复杂度 $O(n\sqrt n)$。 ## 69.CF704E Iron Man(14) 考虑序列上怎么做，对时间扫描线，那么我们只需要支持加点，删点，查询相邻两点相交时间，这个可以用 set 维护，具体方法是把时间开成全局变量，因为我们维护的过程中一旦相交就推出了所以不会 UB。 树上就硬套个树剖。 时间复杂度 $O(n\log n\log m)$。 ## 70.CF708D Incorrect Flow(12) 每条边先强制流 $f$ 的流量，然后考虑上下界费用流： - $c<f$，这时先令 $c=f$，答案加上 $f-c$： - 前 $f-c$ 次退流代价和扩大 $c$ 产生的代价抵消了，边权是 $0$； - 后 $c$ 次退流和普通退流一样，边权是 $1$； - 增广时 $c$ 和 $f$ 都要增加，边权是 $2$。 - $c\geq f$： - $f$ 次退流边权是 $1$； - 前 $c-f$ 次增广只扩大 $f$，边权是 $1$； - 后续增广 $c,f$ 都要扩大，边权是 $2$。 其中退流边反向建即可，然后直接跑上下界费用流。 时间复杂度 $O(n^2m)$。 ## 71.CF708E Student's Camp(12) $g_i$ 表示边上消失了 $i$ 个格子的方案数，显然有 $g_i=\dbinom mip^i(1-p)^{k-i}$。 先考虑暴力 dp，$f_{i,l,r}$ 表示前 $i$ 行上一行的格子区间是 $[l,r]$ 的概率，转移显然，复杂度 $O(nm^4)$。 光是状态就已经有 $O(nm^2)$ 了，先优化状态。 左右端点其实是同等地位的，所以我们其实可以只记一边。 记 $f_{i,j}$ 表示前 $i$ 行上一行右端点在 $j$ 的概率，考虑与容斥掉不交的区间，那么有： $f_{i,r}=\sum\limits_{l=1}^rg_{l-1}g_{m-j}(\sum\limits_{j=1}^mf_{i-1,j}-\sum\limits_{j=1}^{l-1}f_{i-1,j}-\sum\limits_{j=1}^{m-r}f_{i-1,j})

最后一项是因为左右端点同等地位，可以直接对称过去。

接下来套路地前缀和优化，令 sum_j=\sum\limits_{k=1}^jf_{i-1,k}：

f_{i,r}=g_{m-j}\sum\limits_{l=1}^rg_{l-1}(sum_m-sum_{l-1}-sum_{m-r})

里面还能再前缀和优化一次，然后就可以直接转移了，时间复杂度 O(nm+k)。