做题记录 25.10.23

· · 个人记录

\textcolor{black}\odot P5294 [HNOI2019] 序列 \quad LOJ #3059. 「HNOI2019」序列

先考虑静态的情况

根据 IOI2018 集训队论文 高睿泉 《浅谈保序回归问题》 可得以下做法：

这样得到一个 O(qn) 的算法

然后考虑修改的情况

对于修改 (i,k)，设 [1,i-1] 得到的区间为 \{(l,r,s)\}_{i=1}^l，[i+1,n] 得到的区间为 \{(L,R,S)\}_{i=1}^R（逆序排列），两者使用主席树存储

令 avg_l(i)=\frac{s_i}{r_i-l_i+1}，avg_r(i)=\frac{S_i}{R_i-L_i+1}，令 avg_m(i,j)=\frac{\sum_{i=r_i+1}^{L_j-1}a_i}{L_j-r_i-1}

从大到小枚举 R_0=R\sim 0，对于每个 R_0，求出最小的 L_0 使得 avg_l(L_0)<avg_m(L_0,R_0)，若得到的 avg_m(L_0,R_0)<avg_r(R_0) 则答案的分组为 \{(l,r)\}_{i=1}^{L_0},(r_{L_0}+1,L_{R_0}-1),\{(L,R)\}_{i=1}^{R_0}

可证 R_0 一定时 L_0 单调，可证 R_0 单调

外层二分，内层主席树上二分，总时间复杂度 O(n\log n +q\log^2 n)

若离线则可以用扫描线等代替主席树

代码：luogu \quad LOJ

参考

QOJ #14549. 造桥与砍树

即边权为 (t_u+t_v)\bmod k 的 \text{MST}

考虑 \text{Boruvka} 算法，每次需要枚举 u，在当前连通块外找到 (t_u+t_v)\bmod k 最小的 v

令 S 为当前连通块外的 (t_v\bmod k,u) 的集合（初始加入所有，枚举到一个连通块时从中删除，处理完后撤销），对于当前的 u，找到第一个 v\ge k-(t_u\bmod k) 的 (v,u)，若不存在则找最小的

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

代码

\blue\odot P11483 [NordicOI 2021] The Elk

边双缩点，不在对应路径上的点合法

时间复杂度 O(n+m)

代码

\blue\odot P11604 [PA 2016] 卡牌 / Gra w karty

建立 2n 个点的二分图，若 x>y 则 L(x)\to R(y)，否则 L(x)\gets R(y)，则 可证 A 赢当且仅当存在入度为 n 的右部点，B 赢当且仅当不存在入度为 n 的右部点且存在入度为 n 的左部点，否则平局

代码

参考

\blue\odot P11505 [NordicOI 2018] Mysterious Array

处理出每个位置的下界 t_i，容易用 set 或 \text{ST} 表等做到 O(n\log n)

从小到大填数，设当前填 v，若存在 =v 的限制，取这些限制的区间交为 [L,R]，则 [L,R] 中必然有一个为 v，当前位有 \sum_{i=L}^R [t_i=v] 种填法，否则当前位有 \sum_{i=1}^n[t_i\le v]-(v-1) 种填法

容易做到 O(n\log n)

代码

参考

\blue\odot P11497 [ROIR 2019] 自动仓库 (Day 1)

显然操作次数为 O(n+m) 的，且容易构造，为了求出具体方案，转化为对于每个位置，求出它到下一个相同值位置之间，出现的种类数

询问左端点连续递增，因此树状数组维护所有位置值是否为最后一次出现，时间复杂度 O((n+m)\log(n+m))

代码

参考

\blue\odot P11645 【MX-X8-T4】「TAOI-3」Warmth of the Eternity

令 S_i 表示 i 的 d_i 个连通块大小的可重集

当 n-1\in S_i 时，显然 i 为叶子，令 c_i=\sum_{u\in S_i}[u=1]，则贡献为 \binom{\sum c_i}{c_1,c_2,\cdots,c_n}

然后考虑 n-2\in S_i 的情况，令 C_i=\sum_{u\in S_i}[u=2]，贡献为 \binom{\sum C_i}{C_1,C_2,\cdots,C_n}

依次类推，可得其它的贡献

发现 \sum c_i=\sum_{i=1}^n \sum_{u\in S_i}[u=i-1]，令 S=\bigcup S_i，则答案为 \prod_{2i>n} (\sum_{u\in S}[u=n-i])! \prod_{2i\le n} \prod_{j=1}^n \frac1{(\sum_{u\in S_j}[u=i])!}

容易 O(n) 求出答案

代码

参考

\blue\odot P11170 「CMOI R1」图上交互题 / Constructive Minimum Xor Path

可证 若存在解则 w(u,v) 取 f(u,v) 为一组解，此时要求所有环异或和都是 0，树上差分即可

时间复杂度 O(n+m)

代码

\green\odot AT_abc308_f [ABC308F] Vouchers

将 a 从小到大排序，将 (l,d) 按 l 从小到大排序

枚举 a，对于 l\le a_i 的 (l,d)，将 d 加入大根堆，将 a 计入答案，若堆非空则弹出堆顶并从答案中减去

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

代码

参考

\blue\odot P11268 【MX-S5-T2】买东西题

将 (a,b) 视为价格为 a 的物品和满 a 减 a-b 的优惠券，转化为 \green\odot AT_abc308_f [ABC308F] Vouchers

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

代码

\blue\odot P11277 世界沉睡童话

设 c_i 表示答案中 i 的数量，发现存在最优解使得只有 c_1 和 c_{n\sim 2n-1} 不为 0，此时要求 \sum_i \binom{c_i}2 +c_i(n-c_i)=k

贪心地，令 c_1 从 0 增加直到不满足 \binom{c_1}2+c_1(n-c_1)\le k，从 k 中减去这一部分，然后枚举 i\ge n，令 c_i 从 0 增加直到不满足 \binom{c_i}2\le k

容易做到 O(n)

代码

参考