Baltic Olympiad in Informatics 2021
| books | servers | watchmen | prison | swaps | xanadu |
|---|---|---|---|---|---|
| $\color{green}{\texttt{+8}}$ | $\color{green}{\texttt{+2}}$ | $\color{green}{\texttt{-}}$ | $\color{green}{\texttt{+1}}$ | $\color{green}{\texttt{-}}$ | $\color{green}{\texttt{+1}}$ |
链接 题面链接
A. books
题意
交互题。给定 $n,k,A$。有一个长度为 $n$ 的递增序列 $a_i$，每次可以询问位置 $i$ 的权值，要求返回一个大小为 $m$ 的集合 $S$，满足 $\sum_{i\in S} a_i\in[A,2A]$。
$n\leq 25000,k\in[3,10]$。询问次数 $40$ 次。
题解
首先考虑如果所有元素都 $<A$ 的情况。可以发现 $[1,k]$ 一定是最小的和，$(n-k+1,n]$ 一定是最大的和。如果最小的和 $>2A$ 或者最大的和 $<A$ 那么直接无解。
否则可以发现相邻区间区间 $[i,i+k)$ 与 $(i,i+k]$ 之差 $<A$，所以连续区间中一定有解。
二分位置 $p$ 查询 $[p,p+k)$ 的和，即可做到 $k\log n$ 次查询。
考虑有元素 $\geq A$ 的情况。其实这个很好处理：二分找到最小的 $x$ 使得 $x\geq A$，那么贪心地选一定取 $[1,k)$ 最优。如果 $[1,k)\cup{x}$ 不合法，那么任何有元素 $\geq A$ 的集合都不合法。
考虑优化询问复杂度。注意到其实我们只要构造一个子序列，满足这个子序列最小子区间 $\leq 2A$，最大子区间 $\geq A$，相邻区间差 $<A$。
考虑先排除有元素 $\geq A$ 的情况，这样相邻区间差一定 $<A$。假设 $n$ 为剩下序列长度。事实上我们只需要保留 $[1,k]\cup(n-k,n]$ 对应的子序列即可，此时上述三个条件都满足。
因为子序列长度只有 $2k$，直接暴力全部查出即可。
分析交互次数，总共 $O(k+\log n)$。
代码
1 |
|
B. servers
题意
给定一个 $n$ 个点的树，每个点要维护一个集合 $S_u$，支持：
- 选定一条树边 $(u,v)$，令 $S_u\leftarrow S_u\cup S_v\ ,\ S_v\leftarrow S_u\cup S_v$。即同时赋值为并集。保证每条树边都会被恰好操作$1$次。
- 询问 $u,v$，回答是否有 $v\in S_u$。
- 询问 $v$，回答 $\sum_u[v\in S_u]$ 即有多少个集合包含 $v$。
题解
首先离线把树建出来，这样相当于每条边有一个权值。
考虑点分治。首先处理 $2$ 操作。可以发现 $S_u$ 中要有 $v$ 当且仅当 $v$ 到 $u$ 路径权值单调递增且询问时间大于路径最大权值。这些都可以直接 dfs 解决。
考虑处理 $3$ 操作。对于每个点分中心我们处理的是该点在其点分子树外的贡献，即对于其他子树询问有多少能够到达，要求同样是路径单调增且询问时间大于路径最大权值。
先处理出上升路径与下降路径，把所有子树按与分治中心连边的权值从大到小排序，显然只有连边权值小的子树才有可能存在路径到连边权值大的子树。
由于下降路径最大值一定大于上升路径，所以只需要将下降路径的权值作为键值。这样等价于一个单点插入，询问 $\geq$ 某个键值的点数，直接树状数组即可。
分治中心位置的询问要额外判断。
复杂度 $O(n\log^2 n)$。
代码
1 |
|
D. prison
首先显然有一个 $O(n\log^2 n)$ 的垃圾做法：
令 $l_i$ 表示如果 $i$ 要暴动，$[ l_i,i]$ 范围内不能有垫子。转化成平面上有若干线段，选 $k$ 个点使尽可能多的线段包含这些点。
显然这可以建出最小割模型故函数是凸的，用 wqs 二分 + 线段树即可做到 $O(n\log^2 n)$。
考虑一个结论：$\forall i< j\ ,\ l_j\geq i\ \vee\ l_j\leq l_i$。这个很好证明，因为如果一个点能经过 $i$ 传到 $j$ 那么 $i$ 一定也动了。 这样任意两个线段要么相离要么包含。
令每个点的父亲为包含它的，题意转化成：给定一个森林，将 $d$ 个叶子到根路径染黑，问最多能染黑几个。
考虑一个贪心做法：每次选择一个到根白点最多的叶子染黑。证明可以考虑每次取一个点向上第一个没有被染黑的节点 $u$，那么 $u$ 为根子树内最深的点是 $u$ 中最优的点。
如果删除染黑的点，那么一次操作会将一棵树分裂为若干森林。不妨用堆维护森林的根对应子树深度最大值，容易发现一个点只会被加入与删除一次，故复杂度 $O(n\log n)$，可以通过。
而上述过程中所有值都 $\leq n$，所以用桶代替堆同时用一个指针枚举当前最大值可以做到 $O(n)$。
代码
1 |
|
F. xanadu
全场真正的签到题。
直接 dp，用 $f_{i,0/1,0/1}$ 表示点 $i$，当前为 $0/1$，按过 $0/1$ 次按钮。
dp 时记录 $w_{0/1,0/1}$ 表示儿子全部为开/关，根是否被翻转。
复杂度 $O(n)$。
代码
1 |
|