JOISC 2017 记录

Day1 T1 Cultivation

发现任何的两个操作之间时没有偏序关系的，也就是我们可以任意调整操作之间的顺序。那么本质不同的操作，可以用 \(l,r,u,d\) 四个数表示，分别表示向左/右/上/下移动的次数。

假设我们已经确定了 \(u,d\)，则会出现 \(O(n)\) 类本质不同的行，而对于每一行，都会给 \(l,r,l+r\) 一个下界的限制，也就意味着我们可以直接计算出最小的 \(l+r\)。

而对于 \(u+d\) 相同的 \(u,d\)，整个覆盖的条的形态时固定的，则 \(u\) 和 \(d\) 的变化可以看作框选的 \(R\times C\) 的范围的平移，可以用单调队列维护 \(l,r,l+r\) 的限制。

这样对于单个 \(u+d\) 的求值可以做到 \(O(n)\)。

发现最优解的 \(u+d\) 必然在 \(E_i-E_j-1\)，\(R-(E_i-E_j)-1\) 中出现，所以我们只需要检验这 \(O(n^2)\) 处的取值即可，时间复杂度 \(O(n^3)\)。

Day1 T2 Port Facility

考虑什么样的货物不能放在同一个栈里面处理，发现其当且仅当是 \(A_i<A_j<B_i<B_j\) 的结构。这启发我们对这样的点对之间连边，则最终有答案当且仅当图是一张二分图，答案为 \(2^{cnt}\) 其中 \(cnt\) 为连通块数。

依次扫描 \(1\sim 2n\)，如果是 \(A_i\) 就加入这个区间，如果是 \(B_i\) 就删除这个区间，并且将所有的还没有删除且在 \(i\) 之后加入的区间与 \(i\) 区间连边。

考虑 \(i\) 连边的点必然对应一段区间，而且这些点连边之后就本质相同的，所以可以将它们缩成同一个点。

根据势能分析可知，我们只会连出 \(O(n)\) 条边，所以复杂度正确。整个上述过程都可以使用并查集维护，时间复杂度 \(O(n\alpha(n))\)。

Day1 T3 Sparklers

答案具有单调性，可以先二分答案。现在需要考虑一个速度 \(v\) 能否满足条件。

可以通过画出 \(t-s\) 图像的方式知道，最优策略下必然只会同时有一支烟花棒燃烧。同时所有人向第 \(K\) 个人靠拢是优的。

这也就意味着，最优的操作是第 \(K\) 个人选择走到他左侧或者右侧最近的人，每一次会额外获得 \(T\) 的实现，也就对应 \(2vt\) 的行动距离（因为是相向而行）。

也就意味着如果我们合并的区间 \([L,R]\) 的人（\(L\le k\le R\)），我们需要保证 \(2vT(R-L)-(x_R-x_L)\ge 0\)。而每一次操作相当于让 \(R\) 增加 \(1\) 或者样 \(L\) 减少 \(1\)。

改写一下式子，也就是我们每次可以让 \(R\) 增加 \(1\)，或者让 \(L\) 减少 \(1\)，要实时保证 \(2vR-x_R\ge 2vL-x_L\)，发现这个和 NOIP T3 的问题是一致的，可以直接套用其 \(O(n)\) 解法。则最终时间复杂度为 \(O(n\log V)\)。

Day2 T1 Arranging Tickets

我们先钦定每个人都是顺时针从 \(\min(s,t)\) 走到 \(\max(s,t)\)。则我们可以翻转若干个人。

考虑先二分答案 \(ans\)，考虑如何检验是否能够满足条件。首先可以证明，如果我们翻转了两个对应区间不交的人，则一定是不优的，这也就意味着必然存在某一个位置 \(t\)，被所有的反转的人包含。我们先考虑枚举这个 \(t\)。

我们假设反转前，每一个位置需要 \(a_i\) 张票，翻转之后每一个位置需要 \(b_i\) 张票。

则对于第 \(x\) 个位置（\(x\le t\)），假设总共翻转了 \(p_t\) 个区间，其中有 \(p_x\) 个左端点 \(\le x\) 的区间，则有 \(b_i=a_i-p_x+(p_t-p_x)=a_i+p_t-2p_x\)。

因为我们有 \(b_i\le ans\)，则可以推出 \(p_x\ge \left\lceil\dfrac{a_i+p_t-ans}{2}\right\rceil\)，所以我们考虑枚举 \(p_t\)，就可以得到对于每一个前缀我们至少需要翻转多少个区间了。

我们顺次扫描 \(1\sim t\)，每一次将可以翻转的区间加入，如果目前反转的区间数量还没有到达 \(\left\lceil\dfrac{a_i+p_t-ans}{2}\right\rceil\)，我们就选择右端点最右的那个区间翻转，如果能够翻转的区间数量不够，则必然不合法。

最后我们检验一遍后缀是否合法即可，我们每一次检验 \(ans\) 的时候需要枚举 \(t\) 和 \(p_t\)，所以时间复杂度是 \(O(n^3\log n\log V)\) 的。

我们想要尝试减少枚举的 \(t\) 和 \(p_t\) 的数量。

可以证明 \(b_t\) 必然等于 \(\max\limits_{i=1}^nb_i\) 或者 \(\max\limits_{i=1}^nb_i-1\)，如果不是，我们可以取消某一个反转的区间，使得 \(b_t\) 增加 \(1\)，全局最大的 \(b_i\) 减少 \(1\)，答案变优。这也就意味着 \(b_t=ans\) 或者 \(ans-1\)，也就意味着 \(p_t\) 确定了。

同时可以证明，最优方案中，必然可以找到一个 \(t\) 满足 \(a_t=\max\limits_{i=1}^na_i\)；同时对于每一个这样的 \(t\)，必然存在一组最优方案。

这样，我们 \(t\) 和 \(p_t\) 的枚举量都变成 \(O(1)\)，所以最终复杂度优化到了 \(O(n\log n\log V)\)。

Day2 T2 Broken Device

我们考虑用一位来维护一位的信息肯定是不现实的，所以考虑用将若位分成一组来维护信息。

如果我们两位一分，我们就可以用那些两位均没有损坏的位置维护 \(3\) 种信息，对于损坏的位置不维护信息，这样最劣可以维护 \(\dfrac{150}{2}-40=35\) 位的信息，但是 \(3^{35}\le 10^{18}\)，其实是并不够的。当然可以通过一些随机化的技巧来优化。

所以考虑三位一分，对于没有损坏的维护，我们维护两位二进制位的信息；对于有一位损坏的，我们维护一位二进制位的信息；有两位或者三位损坏的，我们不维护信息。

通过计算发现，这样最劣情况下我们可以维护 \(60\) 位二进制位，刚好是可以通过的。由于有一位损坏的我们不知道具体是那一位，所以我们至少要设计两个三位的二进制码来对应 \(0/1\)，而对于没有损坏的，只需要设计一种就可以了。这是我们就需要总计 \(2\times 2+4\) 种三位二进制数，但是我们只有 \(7\) 种可以用的三位二进制数（\(0\) 不可用）。也就意味着我们需要压缩有一位损坏的时候的状态。

例如 \(100,011\to 1\)，\(010\to 0\)，\(001\to 00\)，\(101\to 01\)，\(110\to 10\)，\(111\to 11\)。

这样，如果要表示 \(0\) 但是中间的那一位损坏了，我们发现 \(00\) 和 \(01\) 都不需要中间那一位，所以其实时可以用这一位维护两位的信息。

Day2 T3 Railway Trip

考虑在可以直接通过某一条铁道通行而不需要中途停靠的点对之间连边，发现这样的限制类似于在笛卡尔树上向左侧和右侧最近的祖先连边。可以证明这样链出来的是一个平面图的三角剖分，所以可以直接使用三角剖分求点对间最短路的技巧做到 \(O((n+Q)\log n)\)。

Day3 T1 Long Distance Coach

将所有人按照 \(D_i\) 排序之后重标号，则每一次下车的人必然是编号的连续区间，而且这个区间内的最后一个人 \(i\) 必须要满足存在一个服务站 \(S\) 使得 \(D_i<(S\bmod T)<D_{i+1}\)。

同时由于司机不能下车，所以对应的区间必然是 \([l,r]\)，而不会出现 \([1,r]\cup[l,m]\) 的结构。

由此，我们可以设计 DP \(f_i\) 表示处理了前 \(i\) 个人的最小代价。

我们考虑每一个人是被赶下车还是留在车上。

如果留在车上就有 \(f_i\gets f_{i-1}+W(\left\lfloor\dfrac{X}{T}\right\rfloor+[X\bmod T>D_i])\)。

否则，我们枚举这一次下车的区间 \([j+1,i]\)，\(f_i\gets \min\limits_{j<i}(f_{j}+(sum_i-sum_j)+W(i-j)sd_i)\)。其中 \(sum_i\) 为前 \(i\) 个人的 \(C_i\) 的和，\(sd_i\) 为 \(\min\limits_{D_i<S_j\bmod T<D_{i+1}}\left\lfloor\dfrac{S}{T}\right\rfloor\)，表示将 \(i\) 赶下车之前需要喝水的次数。

对于前者，可以直接暴力转移，对于后者，其等于 \(\min\limits_{j<i}(f_{j}-sum_j-Wjsd_i)+sum_i+Wisd_i\)，可以使用斜率优化，具体的就是二分栈。

Day3 T2 Long Mansion

我们想要对于每一个 \(i\) 维护出 \([l_i,r_i]\) 表示从第 \(i\) 个位置出发能够走到的范围。

考虑直接记忆化搜索，每一次 \(i\) 需要往左或者往右拓展的时候，我们并上 \(L-1\) 或者 \(R+1\) 对应的 \([l,r]\)。

似乎可以证明这样拓展的总次数是 \(O(n)\) 次的，所以复杂度就对了。

Day3 T3 Natural Park

我们想要维护一个包含 \(0\) 的连通块 \(S\)，如果我们每次可以降入和一个和 \(S\) 有直接连边的点，我们就可以通过类似二分+分治的方式找到和这个连通块的所有连边。

现在的问题是如何找到这样的点。我们考虑随便找一个 \(x\)，如果这个点和 \(S\) 直接相连，就可以加入；否则可以二分出来一个在 \(S\) 到 \(x\) 的路径上不在 \(S\) 内的点 \(y\)，然后递归处理这个点 \(y\)，然后再处理点 \(x\)。

每次向 \(S\) 加入一个点需要二分，每一次连一条边也需要二分，最终的询问次数复杂度约为 \(n\log n+m\log n+7m\)。

Day4 T1 Abduction 2

除了第一次开始之外，任何依次拐弯的位置 \((x,y)\)，都可以唯一确定两个下一次拐弯或者结束的位置，具体的，这两个位置可以用线段树上二分直接得到。

可以证明，记忆化搜索直接维护上述 \((x,y)\) 能够走到最远的位置，询问到的点数是 \(O(n\sqrt{q})\) 的，所以最终的时间复杂度为 \(O(n\sqrt{q}\log n)\)。

Day4 T2 City

考虑如果我们维护出来的每一个点对应的 dfn 序区间 \([L,R)\)，我们就能够直接通过这两个数得到祖先后代关系。但是这样需要 \(35\) 位。

考虑阈值分治，对于子树大小 \(siz< B\) 的，我们有 \(R-L\le B\)，所以我们可以只维护 \(L\) 和 \(R-L\)，而对于 \(siz\ge B\) 的，这样的点最多只有 \(\dfrac{\sum siz}{B}=\dfrac{\sum dep}{B}=18\dfrac{n}{B}\) 个，对于每一个，我们钦定 \(L,R\) 均为 \(B\) 的倍数，我们就只需要维护 \(\dfrac{L}{B}\) 和 \(\dfrac{R}{B}\) 了。

发现 \(B=2^7\) 时比较合适，可以通过。

Day4 T3 Dragon 2

我们考虑如何维护一个点 \(P\) 到一堆点会有多少条经过道路的射线。首先按照这一堆点是否和 \(P\) 在道路的同侧区分，在同一侧的所有点，发现满足条件的会是这个半平面的某一个部分，具体的，会有和道路两个端点之间的两个夹角的大小有所限制，这也就对应成了一个二维数点问题，可以使用主席树维护。

考虑对于依次询问，我们暴力枚举数量少的那边的点，可以证明复杂度时正确的。

如果较少的那边有 \(x\) 条龙，则对于 \(x<B\)，单次询问的次数是 \(O(B)\)；而对于 \(x>B\)，本质不同的龙的种族最多只有 \(\dfrac{n}{B}\) 种，则询问的复杂度最多位 \(\dfrac{n}{B}\times n=\dfrac{n^2}{B}\)，考虑 \(B\) 取 \(\dfrac{n}{\sqrt{Q}}\)，则最终时间复杂度为 \(O(n\sqrt{Q}\log n)\)。