JOISC 2019 记录

Day1 T1 Examination

三维数点板子题，直接 cdq分治+树状数组，时间复杂度 \(O(n\log^2n)\)。

Day1 T2 Meetings

对于一个大小为 \(n\) 的树，我们可以在 \(n-2\) 的询问中得到某一条我们选定的链 \((x,y)\) 上的所有节点的集合 \(S_0\)，以及在断掉这条链之后，得到的若干连通块集合 \(S_1,S_2,\dots,S_{S_0}\)，这样我们就可以通过 \(O(n)\) 次询问将查询整个树分成查询 \(|S_0|+1\) 个树，由于每一个点的度数很小，所以考虑直接每一次随机选取 \((x,y)\)，可以通过。

Day1 T3 Naan

考虑先得到每一个人单独均分这块馕的 \(N-1\) 个位置，然后按照 \(i\) 从小到大，贪心地让第 \(i\) 个分界点最小且还没有拿到过馕的人分到按照他的分界点分到馕，由于这个人不是第 \(i-1\) 个分界点最小的人，所以它分到的这一块一定完全包含了他单独分的时候的一块，也就是有了至少独吞时的 \(\frac{1}{N}\)。

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

Day2 T1 Two Antennas

考虑扫描线 \(R\)，所有可能做出贡献的 \(|H_x-H_y|(x<y)\) 都记录在 \(x\) 上。
由于我们要计算 \(\max|H_x-H_y|\)，等价于求 \(\max(H_x-H_y,H_y-H_x)\)，所以可以做两次直接去掉绝对值。

我们只考虑 \(H_x-H_y\) 的情况。
考虑到 \(x\) 向后做出贡献的是一段区间，而 \(y\) 向前做出贡献的也是一段区间。所以可以使用线段树维护 \(\max val_x\)，其中 \(val_x=\begin{cases}H_x,&y\in[x+A_i,x+B_i]\\-\infty,&y\notin[x+A_i,x+B_i]\end{cases}\)，每一次增大 \(y\) 的时候修改变化的 \(x\) 即可，总共只需修改 \(O(n)\) 次，而每一次让 \(y\) 对 \([y-B_y,y-A_y]\) 这段区间为 \(-H_y\) 打上懒标记，表示其对这一段区间可以做贡献，实时维护出现过的最大的 \(val_x-H_y\) 即可，时间复杂度 \(O(n\log n)\)。

Day2 T2 Two Dishes

由于不能停下来休息，所以每一个步骤的限制都可以抽象成：如果在完成某道菜第 \(i\) 个步骤之前另一道菜的进度 \(\le a\) 就会对答案做出 \(b\) 的贡献。

整个做菜的过程是一条折线，会做出贡献的就是经过了某一条平行于坐标轴的线段，通过讨论全部转成平行于纵轴的线段，扫描线掉横轴，维护另一维，发现由于修改可能出现的不同的转移只能是 \([0,p]\to [p+1,+\infty)\)，可以直接使用线段树维护。

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

Day2 T3 Two Transportations

这是一个双人 Dijkstra 的过程，两个人都按照自己知道的边来维护最短路，比较两个人的下一个转移点，选择其中较小的进行转移。考虑到一个合法的转移必然与上一个转移的权值之差 \(\le max(C,D)\le 500\)，所以每人只需要 \(\left\lceil\log_2500\right\rceil=9\) 传输信息即可。

但是对于需要用对方的转移点转移的一方，他不知道这个点具体在哪里，所以还需要 \(\left\lceil\log_2N\right\rceil=11\) 位来传输这个点的信息，单次总共需要 \(9+9+11=29\) 位来传输信息，总用有 \(N\) 次转移，总共需要 \(29N\) 次传输，刚好满足条件。

Day3 T1 Designated Cities

\(E=1\) 时，可以之间换根得到每一个点的答案 \(w_i\)。
\(E=2\) 时，如果选择两个点 \(x,y\)，答案为 \(\dfrac{w_x+w_y+dis(x,y)}{2}\)，其中 \(dis(x,y)\) 为路径上每条边的两个权值的和的和。
\(E>2\) 时，可以证明存在最优解是在 \(E-1\) 的起初上再选择一个点，也就是再覆盖一条某个方向的链，这是一个比较经典的贪心，具体的，将 \(E=2\) 是选择的链缩成一个点，然后将树按照权值和进行长链剖分，每一次选择最长的长链即可。

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

Day3 T2 Lamps

由于 on/off 操作会直接区间覆盖，所以可以通过调整将最优解变成先执行所有的 on/off 操作，在执行 tog 操作。
tog 是反转，所以存在最优解使得 tog 操作的区间不交。

如果出现相交的 on/off 操作，它们必然是包含关系，同样可以转成一个 on/off 和若干个 tog 操作，这样没有增加操作次数。由此所有的 on/off 操作也不交了，由此我们可以直接 DP \(f_{i,0/1,0/1}\) 表示处理了前 \(i\) 位，当前第 \(i\) 位是否有 on/off 操作，是否有 tog 操作的最小次数，时间复杂度 \(O(n)\)。

Day3 T3 Bitaro, who Leaps through Time

通过调整可知，存在最优解只有在不得不时间回溯的时候才时间回溯。同时我们将坐标系偏移一位，使得所有向左右移动一格不改变时间。

此时，可以通过分类讨论得到经过一个区间的方案可能为：有一个空区间 \([L,R]\) 可以之间经过；或从 \(L\) 进入，从 \(R\) 离开，中间消耗 \(k\) 次回溯。

这个信息的合并是可以分类讨论 \(O(1)\) 得到的，使用线段树维护，时间复杂度 \(O(n\log n)\)。

Day4 T1 Cake 3

发现对于一个选择的蛋糕集合 \(S\) 来说，答案为 \(\sum\limits_{i\in S}V_i-2(\max\limits_{i\in S}C_i-\min\limits_{i\in S}C_i)\)。

不妨按照 \(C\) 将所有的蛋糕排序，我们钦定后面的极差 \(C_r-C_l\) 之后，相当于要在 \([l,r]\) 中选择前 \(m\) 大的蛋糕，对于单独的 \(l,r\)，求出答案 \(f_{l,r}\) 可以使用主席树做到 \(O(\log n)\)。

记 \(g_r=\operatorname{argmax}\limits_{l\le r}f_{l,r}\)，发现 \(g_r\) 不减，有决策单调性，所以可以直接通过分治得到所有的 \(g_r\)，时间复杂度 \(O(n\log^2n)\)。

Day4 T2 Mergers

如果存在可分裂的 X 组和 Y 组，其必然对应一条边分割成的两个连通块，我们称使得其可分裂的边为可分裂边

每一种颜色构成的虚树对应原树上的所有边都不是可分裂边，我们可以将其两端的点缩在一起，这样我们最终会得到一棵只有可分裂边的树。

如果这个树有至少两个节点，及其叶子节点数量（无根树）为 \(lf\)，则最终答案为 \(\left\lfloor\dfrac{lf+1}{2}\right\rfloor\)。

每个虚树可以被剥离称 \(siz\) 条链，使用并查集维护点集，时间复杂度 \(O(n\log n)\)。

Day4 T3 Minerals

我们扫一遍将所有的点分成两组，其中每种矿物每一组各一个，具体方式为依次插入，如果总矿物量变化就放到第一组，否则放到第二组。

然后，我们对于第一组，将前 \(Bn\) 和后 \((1-B)n\) 个矿物的状态设置成不一样的，然后依次修改第二组中的矿物存在状态，如果其对应的第一组不在集合内，则答案会变化，这样我们可以通过 \((1+B)n\) 此操作将所有的矿物分成 \(Bn\) 和 \((1-B)n\) 两组，在 \(B=0.5\) 的时候，操作次数为 \(1.5n\log_2n+2n\approx 1078787\) 次，无法通过，发现单层的操作是 \((1+B)n\) 的，所以可以考虑些微的减小 \(B\)，发现操作次数更优，同时可以加入一些剪枝，就可以卡过去了。