キサラギの世界

概况#

今年的网络赛也算告一段落了，我们队拿到了上海站的区域赛名额，比赛在 12 月初，还有不少时间可以准备。
接下来的这段时间里，有空可能会看看上海站往年的题目，熟悉一下题目的风格，不过在此之前先复盘一下刚刚参加的两轮网络赛。
ICPC 第二场网络赛题目相当难，不过 CCPC 网络赛的题相对简单一些，就先从这次的 CCPC 网络赛开始复盘。
ICPC 第一次网络赛的复盘可见我的另一篇博客。

这次我们做了 8 道题出来，发挥还算不错，保持这个状态拿区域赛银牌应该问题不大。
根据外部榜单，题目的通过情况如下：
A：$\textcolor{red}{33/304}$
B：$\textcolor{green}{1881/5810}$
C：$\textcolor{green}{485/5042}$
D：$\textcolor{red}{1/52}$
E：$\textcolor{green}{1595/4050}$
F：$\textcolor{red}{20/156}$
G：$\textcolor{red}{0/42}$
H：$\textcolor{green}{1845/2369}$
I：$\textcolor{green}{1796/2846}$
J：$\textcolor{orange}{266/1939}$
K：$\textcolor{green}{1015/3311}$
L：$\textcolor{red}{79/1341}$
M：$\textcolor{green}{424/1410}$
N：$\textcolor{green}{2109/2320}$

以上标绿色的题目是我们做出来的，标橙色的是相对可做但没做出来的，标红色的是相对不可做的，基本都是省选以上难度的题目，可见这次把可做的题目都做得差不多了。
详细题面见 QOJ，此处不再赘述，接下来记录一下可做的 9 道题目解法，根据通过人数，按简单到困难的顺序记录。

Problem N#

签到题，按题意模拟。

Problem B#

暴力搜索 $7^6$ 个所有可能的组合，并检查每个组合的 $36$ 种点数对，如果最小可能点数和比给定的要求要小，差值可任意分配。

Problem H#

通信题，做法很多，可以第一轮输出原排列及每个 $p_i$ 分别和 $p_1$ 交换的排列。第二轮恢复的时候 $p_2,...,p_n$ 只需要找对应列的众数，$p_1$ 是剩下没有被使用的数字。

Problem I#

注意到满足条件的 $n$ 一定是偶数，对于偶数可直接构造 $a=1, b=-1, c=n/2$。

Problem E#

通过观察可以发现，位置 $k$ 后有效边界存在的充要条件是，三个排序中有两个具有相同的前 $k$ 个问题集合。
标答的做法是取一对排名 $A,B$，记录每个元素在 $B$ 中的位置，然后从左往右扫描 $A$，维护它的前 $k$ 个元素在 $B$ 中的最大位置，当最大值等于当前扫描到的位置 $k$ 时，说明 $k$ 后面存在有效边界。
对三个排名两两之间做以上操作，最后统计所有满足条件的 $k$ 即可，时间复杂度为 $O(n)$。
我们的做法是从左到右同时扫描三个排名，分别维护三个排名前缀集合两两之间的对称差大小，实现也很简单，时间复杂度为 $O(n)$。

Problem K#

从出度为 $0$ 的 $t$ 点开始按照拓扑排序，依次维护每个点到 $t$ 的最短距离和最短路径条数，再计算期望，根据节点是否有信号决定转移的系数，无信号时均分，有信号则从所有最短路中按照条数加权分配，时间复杂度为 $O(n+m)$。
虽然这道题的思路很简单，不过我不太熟练图论相关的程序实现，代码是交给队友写的。

Problem C#

从这题开始就需要一些思考了，考场上我在做 $M$ 题，这题是完全交给队友做的。
首先到达 $y=y_c$ 后，一定沿着垂直方向抵达终点，而抵达 $y=y_c$ 的路径也一定是沿着一条直线，如果是曲线变成直线肯定更优。
接下来需要思考穿过 $y=y_c$ 前，是否需要等待障碍物离开，实际上等待不可能发生，如果发生等待，那一开始不应该往你等待的位置走，至少往这一时刻的端点位置走会是更优的选择。
因此最终跑法很简单，要么直接垂直跑向终点，要么先直线走到 $y=y_c$，且此时在障碍物的端点处，然后再垂直跑向终点，
对于第二种情况列出方程 $v^2t^2-y_c^2=(x_1+ut)^2$ 和 $v^2t^2-y_c^2=(x_2+ut)^2$，取最小非负实根即可，时间复杂度 $O(1)$，代码实现不算难。

Problem M#

组合计数题，首先对数组排序，然后进行枚举。
第一种情况，若子序列长度为奇数，且 $a_i=x$ 作为唯一的中位数，则需要在左右两边各选 $k$ 个元素，方案数如下：

对于组合数的计算，可以先预处理 $1$ 到 $n$ 的阶乘，然后每个组合数只需要 $O(1)$ 的时间复杂度。
但是直接算出这个求和式的每一项并相加，需要 $O(n)$ 的时间复杂度，一共有 $O(n)$ 个求和式，总复杂度为 $O(n^2)$，需要进一步的优化，注意到：

因此每个求和式的计算被优化到了 $O(1)$，总时间复杂度 $O(n)$。

第二种情况，若子序列长度为偶数，且 $a_i+a_j=2x$ 作为两个中间元素，同理方案数如下：

首先固定左边的 $i$，然后对于所有的 $a_j=2x-a_i$，需要一次全部处理，假设这个值在排序后出现的位置区间为 $j\in[L,R]$，注意到：

查询位置区间可用函数 lower_bound 和 upper_bound，二分查询的时间复杂度为 $O(\log n)$，因此对于固定的 $i$，只需要 $O(\log n)$ 的时间就能完成所有方案的计算，总时间复杂度 $O(n\log n)$。

而最开始对数组排序的时间复杂度为 $O(n\log n)$，综上，这道题的时间复杂度是 $O(n\log n)$。
考场上这两个注意到比较难想，第一个是打印了很多求和式结果后发现的，第二个的灵感源自于高中时期做的数学题，代码实现不算难。

Problem J#

这应该是考场上剩下的唯一一个有机会做出来的题目，可惜做到这题的时候时间已经所剩无几了。
首先可以发现流水线部分其实只和最大 batch 工作量有关，第一条流水线必须依次处理所有 batch，执行完毕的时刻为 $\sum_{i=1}^n a_i$。
现在考虑第一条流水线和第二条流水线之间的完成时间差 $T$，只有当 $T=\max\limits_{i} b_i$ 时，第二条流水线才不会被最大的 batch 卡住，以此类推，所有 $m$ 条流水线执行完毕的时刻为 $\sum_{i=1}^n a_i+(m-1)\max\limits_{i} b_i$。
因此最终优化的目标只有 $\min\max\limits_{i} b_i$，等价于把一个环分成不超过 $k$ 段，最小化每段内数字之和的最大值，我们在考场上也只想到这里。

接下来考虑二分答案，答案的下界为 $\max\limits_{i} a_i$，上界为 $S$，给定 $mid$，先将环复制一遍变为 $a_1,a_2,\dots,a_n,a_1,a_2,\dots,a_n$，若起点已经确定从位置 $i$ 开始，根据贪心应该尽可能顺时针扩展到最远位置，则找最大的 $j$ 使得 $a_i+a_{i+1}+\cdots+a_{j-1}\le mid$。
记 $nxt[i]=j$，如果到了最右边则记 $nxt[i]=2n$，这个 nxt 数组可以通过双指针一次 $O(n)$ 全部求出来，因为左指针和右指针都只会往一个方向移动，最多移动 $2n$ 次。

接下来只需要检查 $i$ 的 $k$ 级后继是否覆盖了一圈即可，即 $\exists i\in[0,n-1],nxt^k(i)\ge i+n$，但难点在于需要在线性时间内完成所有点的 $k$ 级后继查询。
如果用倍增法，单次 check 需要 $O(n\log k)$，套上最外层二分后的总复杂度为 $O(n\log k\log S)$，很可能超时。
标答用到了一些技巧，对于每一个 $i<2n$，连一条边 $nxt[i]\to i$，一定有 $nxt[i]>i$，而每个点最终一定会走到最右边 $2n$ 处，因此连成的边形成了一棵父亲编号始终更大的树，根节点为 $2n$。
接下来就只需要从根节点 DFS 遍历，同时维护当前 DFS 路径的数组，如果当前节点深度是 $d$，它的 $k$ 级后继就是 $path[d-k]$，因为每个节点只访问一次，一次检查只需要 $O(n)$，总复杂度 $O(n\log S)$。

总结#

这次网络赛简单题目比较多，我们的发挥还算可以，不过还是在代码调试上花了过多时间，导致来不及做 J 题。
我个人认为代码的简洁性还是很重要的，简短的代码往往更易于调试，毕竟人的注意力窗口也有限，可以善用函数封装和 STL。