JOI 2023

· · 个人记录

赛时A因为变量初始化调了1.5h，心态崩掉导致又卡B了1h，然后就彻底崩了。

好似。

A

对于点 i，若存在点对 (j,k) 满足 j < i < k 且 c_j=c_k,c_i\not=c_j，则 i 的颜色会改变。进一步发现决定 i 最终颜色的是 j 最小的点对。

所以考虑从小到大枚举 j，每次找到 c_j 最后一次出现的位置 k（即找到含 j 的最大点对），将 [j,k] 覆盖。由于 [j,k] 内的点不可能再被 j 更小点对覆盖，所以直接从 (k+1) 继续枚举。

时间复杂度 O(n)。

B

虽然舒畅的思路是枚举 X，但是行不通。

发现 i 能对 j 产生贡献的必要条件是 E_i \le E_j，所以考虑倒序枚举 E。

发现一个性质是若 i 能对 j 产生贡献，那么 j 能产生的贡献一定被 i 包含。

这个证明也很简单，若存在点 k 满足 |X_j-X_k| \le E_j-E_k，那么 |X_i-X_k| \le|X_i-X_j|+|X_j-X_k| \le E_i-E_j+E_j-E_k \le E_i-E_k。

所以倒序枚举 E 的过程中，若当前点被覆盖则跳过，否则选择该点。

这样硬做是 O(n^2) 的，考虑用线段树维护每个 X 上的 \max(X+E),\min(X-E)，判断是否被覆盖的时候查询前缀 \max(X+E) 和后缀 \min(X-E) 即可。

时间复杂度 O(n\log n)。

C

做的时候感觉很难，会了之后不知道哪里难/qd/qd

观察到从点 (x,y) 向其他地方走，若要进行操作，最优操作一定是以 (x,y+1),(x-1,y),(x+1,y),(x,y-1) 为正方形的一角，即 (x,y) 的四连通，接着从四连通出发，所有曼哈顿距离 \le N 的点都可以走到，代价是 0/1。

不难发现这是一个01bfs的形式，跑一遍即可。注意dp值相同的点要一起扩展曼哈顿 \le N 的点。

时间复杂度 O(RC)。

D

设 f_i 表示从第 i 个点开始走的最大步数，答案是 f_n。

那么有转移方程 f_i=\max\limits_{h_j<h_i,\{i \rightarrow j\}_{\max} < min(h_i,h_j)}\{f_j+dis(i,j)\}。其中 \{i \rightarrow j\}_{max} 表示路径 \{i \rightarrow j\} 内（不含 i,j）最大的 h。

与 B 类似，若 j 从 i 转移，那么能从 i 转移且的点 k(h_j<h_k)，从 j 转移一定不劣。

证明也不难。若存在点 k 从 i 转移而来，且 h_i<h_j<h_k，那么一种更优的走法是 k \rightarrow j \rightarrow i，即 dis(k,i) \le dis(k,j)+dis(j,i)。并且这条新路径一定是合法的，因为 \{k,i\},\{j,i\} 合法，且 \{k,j\} \subset (\{k,i\} \cap \{i,j\})。

考虑用并查集维护以上过程。每当 i 转移到 j，就将 i 合并到 j 。而枚举转移点时，枚举直接相连的点即可。因为对于非直接相连的点，要么和某个直接相连的点已经合并，要么路径上还存在高度更大的点。

时间复杂度 O(n\log n)，瓶颈在求树上两点距离。

E

蒋老师赛时都不会的题。弃了。

膜csy。

甚至没读题