JOI Final 2018

· · 个人记录

http://qoj.ac/contest/404

（好久没有做题时写代码了.jpg，还有为什么 Final 会是所有赛事中最简单的一场啊）

A

贪心。每次往尽量大的间距去放火柴。

http://qoj.ac/submission/54621

B

按照 A 从小到大排序，选择的一定是一段区间，求出 B 的前缀和 S，枚举右端点的同时维护 A_l-S_{l-1} 的最大值即可。

http://qoj.ac/submission/54623

C

考虑把一个 RGB 的位置定为这个 G 的位置。对于一个横着的和竖着的串，发现他们冲突当且仅当两个是有公共点的左下右上关系。也就是说，它们冲突当且仅当它们是从左下到右上的对角线上相邻的点。对于每个对角线，我们做一个小 DP 即可。在两条不同对角线的合法串显然是不可能相交的。

https://qoj.ac/submission/54783

D

首先从 U,V 出发做最短路求出 d_{u,x} 与 d_{v,x}。然后我们也要理所当然地求出这个图的最短路图 G'。我们相当于要选出两个点 x,y 使得 x,y 在 G' 的一条路径上，且 d_{u,x}+d_{v,y} 最小。G' 是一个 DAG，我们按照拓扑序从后往前 DP：f(u,1/2/3) 表示 u\to T 的所有路径上，已经选择 x / 已经选择 y / 都选择了的最小的代价。

https://qoj.ac/submission/54829

E

设问号的个数为 x，则容易想到一个 2^x 的暴力。然后我们看看这个能不能容斥，然后得到了一个非常肯定的答案：我们可以预处理出 f_{0,s} 表示钦定集合 s 的位置为 0 的蛇的总和，f_{1,s} 表示钦定集合 s 的位置为 1 的蛇的总和，然后考虑问询中，如果 1 的位置少，就把 1 容斥成 0；如果 0 的位置少，就把 0 容斥成 1；如果 x 少，就暴力做。也就是说，我们根据问号，0 的数量，1 的数量，分类讨论选择一个算法去做，就可以做到 O(L2^{L}+Q2^{\frac{L}{3}})，直接通过。（好像我的实现问询枚举集合时还多了个集合大小，但是无所谓反正很快）（很快，指1.8s）。

https://qoj.ac/submission/54885