JOISC 板刷计划

2023-09-03

题解/做题记录

10k 词

希望不会咕咕咕……

有些题 LOJ 上没有就不写了。

JOISC 2014

Day1T1 バス通学

答案显然只能是以 $1$ 为起点的边的起始时间。

考虑将每个点的出边按起始时间从大到小排序，则对于每个到达时间，可以走的边都是一个前缀。
我们考虑对于每个答案跑最短路，发现复杂度爆炸。
但是排序后前面的答案能走的边后面的答案一定能走，于是我们考虑在之前的基础上跑最短路。具体地，我们对于每个点记录一个指针表示当前枚举到了第几条出边，显然指针之前的边没必要重新走一遍。这样每条边至多被使用一次，时间复杂度为 $O(m \log m)$ 。

最后对于每组询问二分即可得到答案。

Day1T2 たのしい家庭菜園

显然最终序列一定是先一段单调不降再一段单调不升。

对于没有相同元素的情况，有一个显然的贪心：每次将最小的元素移到最左或最右（选择距离较短的），然后变成一个子问题。
考虑维护每个元素的实际位置，则移到最左对应前缀 $+ 1$ ，移到最前对应后缀 $- 1$ ，树状数组维护即可。
对于有相同元素的情况，每次移动距离最短的那个即可。

Day1T3 歴史の研究

回滚莫队板板，但是不想写。

考虑平衡复杂度，也就是找出一种 $O(1)$ 修改， $O(\sqrt{n})$ 查询的方法。
当然是值域分块了。考虑将所有可能的 $val \times \text{次数}$ 离散化，就可以实现 $O(1)$ 修改，然后查询就直接从后往前扫每个块即可。

Day1T4 ラーメンの食べ比べ

经典初赛题。

先两个一组两比较分出较大值和较小值，显然最大值只能在较大值中出现，最小值只能在较小值中出现，一个个比较过去即可。

Day2T1 水筒

做法有点怪。

考虑模拟一个类似于 Prim 的过程。

我们记 $from _ {i, j}$ 表示到 $(i, j)$ 最近的已经选择的特殊点， $dis _ {i, j}$ 表示这两个点的距离。每次取出未选择的 $dis$ 最小的点去松弛别的点。
如果取出来的点是特殊点，则连边，并清空 $dis$ 。
建出树之后直接倍增就好了。正确性显然。

但是每个点会被取出来多次，所以复杂度貌似并不能保证。
如果是一般图，可以通过一些方法将其卡到 $O(nm \sqrt{nm} \log (nm))$ ，但是不知道网格图是否存在一些特殊性质使得其复杂度正确。

update：这个东西不劣于 SPFA，且图为网格，边权为 $1$ ，大概可以认为是正确的。

正确的做法是，考虑每个到达点 $x$ 的点，显然只有最近的点和别的点之间的边是有用的。更近一步，对于能一步走到 $x$ 的 $O(1)$ 个点，到这些点距离最近的点之间的边才是有用的。
于是我们把所有特殊点放到队列中 bfs，每次访问到一个点时添加一条这个点的 $from$ 和访问他的点的 $from$ 之间的边，然后跑 Kruskal 即可。
时间复杂度为 $O(nm \log (nm) + (k + q) \log k)$ 。

Day2T2 友だちをつくろう

首先容易观察到一个性质：如果一个点 $u$ 有至少 $2$ 条出边，则 $u$ 的出边的传递闭包会成为完全图。
考虑一个非环的强连通分量（单点暂时视为环），显然其会成为完全图。
于是先缩点，然后形成一个 DAG。
继续挖掘性质，发现如果一个点不是环或是环（不包括单点）且有出边，则这个点和他的传递闭包会成为完全图。
如果一个点是单点且有至少 $2$ 条出边，则使用上面的结论。
于是可以发现每个连通块最终会变成一个以完全图或环为“根”的内向树。
我们对 DAG 拓扑排序，按照上面的结论模拟，删掉外面的外向树，只保留根，然后计算答案即可。

Day2T3 スタンプラリー

先把铁路横过来，这样比较好理解。

我们发现上行进入下行出来和下行进入上行出来必须一一匹配，且下行进入上行出来必须在前面。
另外，下行进入下行出来必须在某个匹配的中间位置。这提示我们在确定上行进入下行出来和下行进入上行出来的位置以后应该匹配尽量远的距离。
然后我们发现这就变成了一个括号匹配的问题，于是考虑使用 DP 去解决。
一个经典套路是设 $dp _ {i, j}$ 表示后 $i$ 个位置匹配后剩余 $j$ 个右括号的答案。转移就是考虑当前位置的四种走的方式，注意下行进入下行出来必须满足 $j \ne 0$ 。
在贡献计算时，我们发现一对距离为 $l$ 的匹配会额外产生 $2lT$ 的行驶时间的贡献，于是考虑把贡献拆成前缀和的形式，在右括号加，左括号减即可。
剩下的一个问题就是，一个位置上其实可能会有多个括号。但是我们发现一个位置上同时有左括号和右括号一定不优，所以直接类似完全背包的转移就是对的。

最后答案即为 $dp _ {1, 0} + T(N + 1)$ 。

Day3T1 JOIOJI

设 $J_i, O_i, I_i$ 分别表示 $1 \sim i$ 的前缀中 $\text{J}, \text{O}, \text{I}$ 三种字母的数量，则等价于找到最大的 $r - l$ ，满足 $J _ r - J _ l = O _ r - O _ l = I _ r - I _ l$ 。
不妨设 $mn _ i = \min \{J _ i, O _ i, I _ i\}$ ，则条件等价于 $(J _ r - mn _ r, O _ r - mn _ r, I _ r - mn _ r) = (J _ l - mn _ l, O _ l - mn _ l, I _ l - mn _ l)$ 。用 map 维护一下即可。

Day3T2 かかし

将点按 $y$ 排序，则对于每个点 $i$ 作为右上角，所有满足条件的左下角都在它之前。
进一步地，如果 $j$ 可以成为左下角，则必须满足不存在 $k$ 使得 $x _ j < x _ k < x _ i, y _ j < y _ k$ 。也就是说如果我们把前面的点按 $x$ 从小到大排序，合法的 $j$ 为所有 $x < x _ i$ 的点的 $y$ 的后缀最大值。
也就是说我们要实现单点修改，前缀查询后缀最大值个数，这个就是经典的楼房重建。

Day3T3 電圧

题意相当于给你一张图，判断有多少条边满足没有和他相同的重边且将他连接的两个点缩起来后图是二分图。

我们发现当图中存在奇环时满足条件的边是所有在所有奇环的交上且不在偶环的并上的边，这样问题就转化成了 CF19E Fairy。
当图中没有奇环时，满足条件的边是所有不在偶环上，即不在环上的边，也就是割边。

Day4T1 2 人の星座

被计算几何爆杀了。

这个数据范围最多只能枚举两个点，考虑找到两个尽量特殊的点使得可以将两个三角形划分到不同的区域。
这里赵的是两个三角形的内公切线。枚举确定内公切线后，两个三角形分别在内公切线两侧，只要能数出两边每种颜色的点数就能求出答案。
考虑优化数点的过程。我们枚举确定其中一个点，然后旋转枚举的线，这样每次只会更改一个点的位置，就可以 $O(1)$ 维护了。

Day4T3 ストラップ

考虑确定选择的挂饰后，一定是优先挂挂钩多的挂饰。所以我们将挂饰按挂钩数量从大到小排序。设 $dp _ {i, j}$ 表示考虑前 $i$ 个挂饰，剩下 $j$ 个挂钩的喜悦值之和的最大值，枚举当前挂饰是否挂上转移即可。

JOISC 2015

Day1T1 コピー＆ペースト２

考虑时光倒流，我们发现每次操作是把一段区间复制到另一个位置，我们根据追溯每个我们要求的字符来自哪里。
设 $p _ i$ 表示第 $i$ 个字符来自哪里。对于这次操作 $a, b, c$ ，如果 $p _ i$ 处于复制的字符串的区间之中，则将 $p _ i$ 更改为被复制的区间。如果 $p _ i$ 处于复制的字符串区间之后，则前移复制的字符串长度位置。如果 $p _ i$ 位于复制的字符串之前，则不变。这样一直回溯到最开始就可以根据 $s$ 确定每个字符了。

Day1T2 愉快なロゴデザイン

由于 JOI 列的特殊性质，我们只需要统计前缀 $\text{J}, \text{O}, \text{I}$ 的数量，即可在 $O(k)$ 的时间内判断一个串是否时 JOI 列。然后枚举起点 check 即可。

Day1T3 たのしいたのしい家庭菜園

发现产生贡献的 IOI 草的高度是先单调不降再单调不升的，这种题的经典套路就是拆成两半然后枚举峰值合并。然后把问题转化成单调不降。
有一个朴素的 dp。设 $dp _ i$ 表示前 $i$ 个 IOI 草，以第 $i$ 个 IOI 草为产生贡献的最后一个的最大贡献。可以得到转移为：

dp _ i = \max\left\{dp _ j - \sum\limits _ {j < k < i, h _ k > h _ j} c _ k\right\}\quad(j < i)

发现贡献几乎只和 $j$ 有关，于是考虑线段树优化。我们把 $h _ i$ 相同的 $i$ 放到一起，只保留 $dp _ i$ 最大的那个。那么转移相当于查询前缀最大值。然后更新就是前缀减一个数，再单点取 $\max$ ，直接线段树维护即可。

2024 年 2 月 9 日重新更新，并更名为《JOISC 板刷计划》，主要是补完了 JOISC 2015 和一部分 JOISC 2016，并更改了目录结构。
~~但是这些题我不是早就写过了怎么现在才来补。~~

Day1T4 IOIOI カード占い

相当于操作异或起来是 $a$ 个 $\texttt{O}$ ， $b$ 个 $\texttt{I}$ ， $c$ 个 $\texttt{O}$ ， $d$ 个 $\texttt{I}$ ， $e$ 个 $O$ 。

如果用一个区间表示一些操作异或起来是只有这个区间为 $I$ ，则相当于要得到 $[a + 1, a + b] \oplus [a + b + c + 1, a + b + c + d]$ 或 $[a + 1, a + b + c] \oplus [a + b + 1, a + b + c + d]$ 或 $[a + 1, a + b + c + d] \oplus [a + b + 1, a + b + c]$ 。

然后考虑取一些操作异或后是一个区间怎么做。
结论：对于操作 $[l, r]$ ，连一条 $l$ 到 $r + 1$ 的无向边，则操作异或后是区间 $[L, R]$ 等价于取出的操作是一条 $L$ 到 $R + 1$ 的路径。

证明还是比较简单的，然后跑一下最短路就好了。

Day2T1 Building 3

首先要满足第二个条件则必须要满足 $\forall i \ge 1, a _ i \le \max _ {j = 0} ^ {i - 1} a _ j + 1$ （特殊定义 $a _ 0 = 0$ ），然后容易证明这个条件是充分的。

然后对 $b$ 序列稍微分讨一下。

若存在 $i \ge 1, \max _ {j = 0} ^ {i - 1} b _ j < b _ i - 2$ ，则答案为 $0$ 。
否则若存在 $i \ge 1, \max _ {j = 0} ^ {i - 1} b _ j = b _ i - 2$ $i \geq 1, max_{j = 0}^{i - 1} b_{j} = b_{i} - 2$ ：
- 若存在 $k > i, \max _ {j = 0} ^ {k - 1} b _ j < b _ k - 1$ ，则答案为 $0$ 。
- 否则设 $id$ 为 $i$ 之前最后一个前缀最大值的位置，答案为 $i - id$ 。（ $id$ 到 $i$ 中间任意一个位置插入 $b _ i - 1$ ）
否则，答案为 $(\sum _ {i = 1} ^ {n - 1} \max _ {j = 1} ^ i b _ j) + 1$ 。

关于最后一条：对于一个连续段，我们只允许在末尾插入与该段相同的数。

Day2T2 合鍵

考虑相邻两个事件：

前进后进：中间这个时间段能关门当且仅当后面的人有钥匙。
前进后出：无论如何都能关门。
前出后进：两个人都要有钥匙。
前出后出：前面的人有钥匙。

我们对于第一种情况将中间时间段的时间加到后面的人的点权上，第四种情况加到前面的人的点权上，第三种情况在两个人之间连一条边，将时间加到边权上，问题转化成选 $k$ 个点使得选的点的导出子图的点权和边权之和最大。

容易发现建出来的图是若干条链，用一个虚根连起来然后树形 DP 即可。

Day2T3 道路整備

时光倒流然后树剖维护即可。

Day3T1 AAQQZ

感觉是比较厉害的一个题，但是不大会描述，不如直接看官方题解罢（

大致思路是分类讨论，然后枚举回文中心向右扩展维护排序后的样子并与左侧匹配。

Day3T2 とてもたのしい

容易发现任意时刻从第三张牌开始后面都是原本连续的牌，所以设 $dp _ {i, j, k}$ 表示上一张取走的是原本的第 $i$ 张牌，第一张和第二张是原本的第 $j$ 张和第 $k$ 张时的答案，则第三张即为 $\max\{i, k\} + 1$ 。

Day4T1 遺産相続

暴力就是直接 Kruskal，然后可以发现任意时刻前面的人的连通性严格强于后面的人，即对于任意两个点 $u, v$ ，后面的人连通则前面的人一定联通，前面的人不连通则后面的人一定不连通，因此对于每条边二分其属于哪个人即可。

Day4T2 記憶縛り

暴力想法是模拟栈，但是空间不够。

正解是每次只 check 某一特定大小的情况，即对于第 $T$ 轮 check，当且仅当当前栈大小为 $T$ 时才判断是否为同一类型的括号，这样需要记录轮数、当前所在的序列的位置、栈的大小和栈内从底向上第轮数个符号，其中轮数和栈的大小最多只有 $n / 2$ ，因此只需要 $6 + 7 + 6 + 1 = 20$ 个比特。
另外栈的大小的奇偶性和当前所在序列的位置是相同的，因此还可以再省一个比特。

Day4T3 防壁

首先考虑激光的位置，容易发现如果存在 $P _ i < P _ {i + 1} < P _ {i + 2}$ ，则可以直接删掉 $P _ {i + 1}$ ，不会对答案产生影响，反过来同理，因此以下假设 $P _ 1 > P _ 2 < P _ 3 > \ldots$ 或 $P _ 1 < P _ 2 > P _ 3 < \ldots$ 。

然后考虑按长度从小到大枚举防壁，则如果相邻两个激光的距离小于等于防壁长度一定不会产生贡献，因此激光会一点点被删除，然后可以发现第一次移动以后的移动是可以直接确定的（来回横跳），因此用一个 set 维护激光和相邻激光之间移动的贡献，然后用链表来维护删除即可。

JOISC 2016

Day1T1 マトリョーシカ人形

按 $R$ 从大到小排序，相当于询问一个左下角矩形的最长上升子序列，扫描 $R$ 维护最长上升子序列，答案即为最长的 $l$ 使得长度为 $l$ 的上升子序列的最大值最小时小于等于询问的 $H$ 。

Day1T2 神経衰弱

每日被交互薄纱……

先两两一组询问，然后如果任意两组的结果不同则恰好每一组是相同的数，否则找到结果相同的两组，可以使用三次询问得到值为结果的两个数。询问次数为 $5n$ 。

Day1T3 ソリティア

待补。

Day2T1 雇用計画

首先离散化，然后考虑把问题转化成在 $A _ i$ 时刻加入点 $i$ ，那么每次加入一个点或删除一个点对每个时刻连续段数量的影响是可以直接计算的，拿树状数组维护一下就好了。

Day2T2 サンドイッチ

首先考虑一个三明治，假设先取上面再取下面，然后我们发现其需要走的路径是固定的，可以直接 dfs。
进一步发现如果先上后下，则取一个三明治要走的路径其下方的三明治也一定要走，所以按列考虑，每一列不清空，时间复杂度就可以优化到 $O(RC)$ 。
然后先下后上一样的做一遍即可。

Day2T3 トイレ

结论：将 F 视为 $+1$ ，M 视为 $-1$ ，则序列合法当且仅当任意后缀和 $\ge -1$ 。

考虑每个 M 都要找一个 F 匹配，然后原本应该是从前往后考虑，但是不难发现从后往前考虑，贪心和尽量靠后的 F 匹配一样正确，于是不难得出结论。
于是答案直接就是 $-1$ 减去后缀最小值。

Day3T1 ダンジョン 2

待补。

Day3T2 回転寿司

一次操作相当于把序列的前缀最大值整体右移然后把 $A$ 插进去。

关键性质：操作顺序不影响最终序列形态。

证明略。于是考虑分块，对于整块，每次都是插入一个 $A$ 取出最大值，用大根堆维护即可。对于散块重构，我们不妨令操作从小到大来，用一个小根堆维护所有操作的 $A$ ，然后扫一遍即可。

Day3T3 電報

特判掉原本就是环的情况，剩下的相当于取出一些链使得点不交且边权和最大，建一个虚根向每个点连边权为 $0$ 的边就等同于最小树形图，容易发现朱刘只会跑至多 $2$ 次。

Day4T1 危険なスケート

首先可以证明不存在制造一个冰块后绕一圈再回来用的情况，因此只需要考虑同一方向来回走，然后就可以有一个 $O(R ^ 2 C ^ 2)$ 条边的最短路的做法，然后优化就是考虑同一方向来回走可以切成先跳到某一端点，然后一个来回走到下一个位置，这样边数就是 $O(R C)$ 的了。

Day4T3 最悪の記者 2

相当于二分图匹配，左部点与右部值比他大的点连边，国籍相同时代价为 $0$ ，否则代价为 $1$ ，求完美匹配的最小代价。

考虑将所有点放一起按值排序，则每个右部点往前找一个左部点。从前往后扫，用右部点去匹配左部点，每次如果存在国籍相同的左部点，找到最靠后的一个判断匹配后是否仍然存在解，如果存在则直接匹配，否则保留这个右部点。

正确性随便证证就好了。

然后考虑怎么维护，那就把左部点当左括号，右部点当右括号，则找到一组匹配就把这两个位置都设成空，用线段树维护括号序列即可。

JOISC 2017

Day1T1 開拓

咕。

Day1T2 港湾設備

朴素想法是直接连边，然后对于每个连通块如果是二分图则答案 $\times 2$ ，否则无解。

然后考虑优化连边，我们不妨先默认是有解的，则一段区间被连边后说明这段区间必然是同色的，则只需要保留第一个，用并查集维护即可。

Day1T3 手持ち花火

参考：https://www.luogu.com.cn/article/0ua1720q。

最优肯定是其他人一起往中间跑，所以在点燃之前人的相对位置是不变的。

并且显然相遇后不直接点燃，直到耗尽的时候再点不劣。

二分答案，然后问题转化成有左右两个队列，每次把某个队列的头取出来，使得过程中时间不会耗尽。取出一个人相当于失去走到他的时间，然后剩余时间加上 $T$ 。

对于每个队列都分成若干块，每块是一个级短的连续段表示取完这段净剩余时间会增加。显然每次都是取一段，并且能取就取。

然后两个队列还会剩下一段后缀是不会增加剩余时间的，对于这部分由于最后剩余时间是可以确定的，因此 reverse 过来再求一遍看能不能取完即可。

另外能取到的条件：设当前是 $[l, r]$ ，要取 $r + 1$ ，则需要满足 $\frac{X_{r + 1} - X_l}{2v} \le (r - l + 1)T$ ，其中 $v$ 表示速度，取 $l - 1$ 也是类似的，于是可以得到设 $x_i = X_i - 2Tvi$ ，能扩展当且仅当 $x_l \ge x_{r + 1}$ 或 $x_r \ge x_{l + 1}$ ，这样就可以变成大小比较了。

同时也证明了不会出现取完后缀需要继续 reverse 回来递归的情况。

Day2T1 切符の手配

为什么不看我们楼阁的题解呢：https://www.luogu.com.cn/article/lqa8q1lu。

Day2T3 鉄道旅行

显然是起点终点一直往高的地方跳然后在某个地方汇合。

先处理出 $l_{u, i}, r_{u, i}$ 表示从 $u$ 跳 $2^i$ 步能跳到的最左和最右的点。

考虑汇合点，显然只有三种： $s, t$ 之间的最大值（可能有多个，但只需要最左和最右的，记为 $M_1, M_2$ ，如果只有一个则 $M_1 = M_2$ ）， $s$ 左边第一个大于 $M_1$ 的（记作 $X$ ）和 $t$ 右边第一个大于 $M_2$ 的（记作 $Y$ ）。

显然从 $s$ 出发起码要跳到 $M_1$ ，也就是跳这么多步后再跳一次会越过 $t$ ， $t$ 类似。这样跳完后 $s$ 要么能到 $X$ 要么能到 $M_1$ ， $t$ 要么能到 $M_2$ 要么能到 $Y$ ，此时要么再走一步就汇合了，要么要把 $M_1$ 和 $M_2$ 之间的高度最大的那些都走掉。

这样好像有点麻烦，我们不妨让 $s$ 先跳到 $X$ 或 $M_2$ ，然后 $t$ 跳的时候只要不越过 $s$ 能到的最右点即可。

Day3T1 長距離バス

咕。

Day3T2 細長い屋敷

先求出每个房间左右最近的有对应钥匙的位置，表示如果从对应方向走到这个房间必须要走到那个位置。

然后考虑暴力，就是每次能走就走。

考虑优化，去掉不必要的枚举。记 $l_i, r_i$ 表示从 $i$ 出发能走到的最左和最右的点。假设已经求出 $1 \sim i - 1$ 的答案，考虑 $i$ 。

考虑 $i - 1$ 和 $i$ 的关系，若 $r_{i - 1} \ge i, l_i \le i - 1$ ，则有 $l_{i - 1} = l_i, r_{i - 1} = r_i$ 。因此先从 $i$ 一直往右走，然后看能不能走到 $i - 1$ ，若不能走到就结束了，否则若能走到，继续分讨：若 $r_{i - 1} \ge i$ ，则直接继承 $i - 1$ 的答案，否则 $l_i \gets l_{i - 1}$ ，然后继续往右走，再往左走。

考虑这个东西的复杂度，先忽略第一次往右走，则对于右边界，每次往右走都会使已有右边界的 $\max$ 变大，均摊 $O(n)$ 。然后每次往左走时，跳过一个点之后这个点以后就不会被访问了，因此也是均摊 $O(n)$ 的。

然后对于第一次往右走直接单调栈预处理一下就也是 $O(n)$ 的了。

Day3T3 自然公園

考虑增量法。每次加一个点 $v$ ，如果与已有的点不联通，可以对剩下的点二分找到一个点 $u$ 使得其在 $v$ 与已有点的某条路径上，先处理 $u$ 再处理 $v$ 。

如果与已有点直接连通，可以在已有点中二分找到一个与 $v$ 直接连接的点，删去这个点后已有点会分裂成若干个连通块，对每个连通块分治处理即可。

Day4T1 誘拐 2

咕。

Day4T3 ドラゴン 2

咕。

留言