JOI Final 2020 题解

JOI 2020 Just Long Neckties

首先一定是贪心将两个从小到大排。然后考虑维护 \(a_i-b_i\) 的前缀 max 与 \(a_{i+1}-b_i\) 的后缀 max 即可。

https://qoj.ac/submission/113106

JOI 2020 JJOOII 2

考虑维护出每个点往前跳 \(k\) 个 J/O/I 跳到哪里。于是枚举右端点，然后往前跳找到最大的左端点即可。

https://qoj.ac/submission/113117

JOI 2020 Collecting Stamps 3

考虑破环后设计 DP：\(f(l,r,x)\) 表示目前走遍了 \([l,r]\) 并停在了 \(l\) 并拿了 \(x\) 个邮票的最小用时，\(g(l,r,x)\) 表示停在 \(r\) 的最小用时。于是 \(f(l+1,r,x)\) 就可以转移到 \(f(l,r,x')\) 满足 \(x'=x+[f(l+1,r,x)+d_{l+1}-d_l\le t_l]\)。同时还有 \(f(l,r,x)\) 和 \(g(l,r,x)\) 的互相松弛（用 \(d_r-d_l\) 松弛）。

https://qoj.ac/submission/113146

JOI 2020 Olympic Bus

考虑对于边 \(u\to v\)，翻转后对于 \(1\to n\) 和 \(n\to 1\) 的影响。以 \(1\to n\) 为例。如果 \(u\to v\) 是最短路必经边，那么就求一下删掉之后的最短路；如果不是，那么就有两种情况，取原最短路，和取反边后 \(1\to v\to u\to n\)，显然两者都不会用到 \(u\to v\)。删掉之后的最短路考虑最短路图后支配树。由于这题有零边所以不能直接 DAG 支配树！暴力复杂度 \(O(nm)\) 即可。

https://qoj.ac/submission/113239

JOI 2020 Fire

首先考虑 \(L=1,R=N\) 怎么做。我们发现每个 \(s_i\) 覆盖的区间会不断右移。\(a_i\) 表示 \(s_i\) 覆盖的区间左端点开始动的时间，即最大的 \(j\) 满足 \(s[i-j,i)\le s_i\)；同理 \(b_i\) 表示区间右端点停止的时间，即最大的 \(j\) 满足 \(s(i,i+j]<s_i\)。考虑 \(f_t\) 表示 \(t\) 时间的和，那么 \(s_i\) 对 \(f_t\) 的贡献是一个类似梯形的一个关于 \(t\) 的函数，我们可以轻易通过 \(a_i,b_i\) 找到 \(i\) 对 \(f\) 的二阶差分的贡献的位置。然后考虑分块，同理我们也可以对于每个块，处理出它的 \(f\)，遍历每个 \(i\) 看 \(s_i\) 对这个块的 \(f\) 的二阶差分的贡献的位置。具体而言，对于块 \([L,R]\)，块左边的贡献为 \(L-i\) 处 \(+s_i\)，\(L-i+a_i+1\) 处 \(-s_i\)，\(\min(R-i,b_i)+1\) 处 \(-s_i\)，\(\min(R-i,b_i)+a_i+2\) 处 \(+s_i\)。块内部点的贡献后面两个是相同的，前面的是 \(0\) 处 \(+s_i\) 以及 \(a_i+1\) 处 \(+s_i\)。

https://qoj.ac/submission/113415