【比赛记录】周测 #14

· · 个人记录

记录

赛时 A 假 B 不会，C 调过了，D 也假，E 没看，比较寄。

题解

A. P7667 [JOI2018] Art Exhibition

发现由于要价值和减去尺寸极差最大，且价值均为正，所以若按尺寸排序，最优解一定是一段连续区间。

考虑预处理价值的前缀和 s，设取的区间左右端点为 x,y。拆式子，得到 S-(A_{max}-A{min})=s_y-s_{x-1}-(A_y-A_x)=(s_y-A_y)+(A_x-s_{x-1})，枚举其中一个括号，另一个维护前后缀最大值即可。

B. P7668 [JOI2018] Dango Maker

如果均不冲突，暴力求个数即可。需要考虑的是有冲突时如何计算，通过举例发现任意两个冲突的串一定是一横一竖，同时 G 在同一条左下-右上对角线上相邻或相同。

所以对于每一条对角线分别考虑，由于两条对角线之间没有相互影响，相互独立。这时设 f_{i,0/1/2} 表示前 i 个中第 i 个不选/竖选/横选的代最大个数，只要保证上一个不选或上一个与当前的串方向不同即可。

C. P6304 [eJOI2018] 山

考虑设 f_{i,j} 表示前 i 座山上选 j 个的最小代价，发现难以转移，所以加一维 k=0/1 表示第 i 个本身是否被选，同时若 i 被选保证 a_{i-1}<a_i 的最小代价，这样能防止重复计算代价。

所以 f_{i,0} 从 f_{i-1} 直接转过来，若选 i-1 还要保证把 a_i 减至小于 a_{i-1}。f_{i,1} 从 f_{i-2}，转过来，要把 a_{i-1} 减至小于 a_i，若同时也选 i-2 也要保证小于 a_{i-2}。

D. P5089 [eJOI2018] 元素周期表

考虑建模成一个二分图，左部点表示行，右部点表示列，每两个点之间的连接情况相当于原图中的一个格是否被填。发现最终要求转化为完全图，同时每个连通块内一定能转化成局部完全图。所以把原有的点作为边，答案等于连通块个数 -1。

E. P7669 [JOI2018] Commuter Pass

发现最终答案一定是一段非 0，一段 0 再一段非 0，军可能为空。因为如果有多段 0 却不连续，那么前一段的结尾 X 和后一段的开头 Y 一定都在 S 到 T 的最短路上，所以一定可以用中间的 0 补起来，一定较优。

但是暴力枚举 0 的两端 A,B 会产生 O(n^2) 的时间复杂度，寄。考虑优化，把 S 到 T 的最短路树建出来，一定是以 S 为源点的 DAG。在上面跑拓扑排序以求出 U 到每个点的最短距离，初始化为原来的最短距离，对于每个 v 更新 dis_v=\min(dis_v,dis_u)，也就是走了一条 0。最后用 dis_i+dis_{i,V} 更新即可。由于可能以最短路的反向经过最短路，还要建反图再跑一遍。