JOI 2021/2022 二次予選 题解

题目链接

A

用栈直接模拟。

B

建图后 BFS。

C

发现确定左上角后,就可以确定所有划分的直线且方案唯一,暴力判断即可。

时间复杂度 \(\mathcal{O}(H^2W^2)\)。

代码链接:https://paste.ubuntu.com/p/5DzJhsPqmy/

D

首先想到一种显然是假的 DP:\(f_{i,j}\) 表示到 \(i\) 保留了 \(j\) 个的最大价值,发现转移是错的。考虑换一种 DP 方式。

注意到题目中连续 \(k\) 个中最多保留 \(2\) 个,于是设 \(f_{i,j}\) 表示当前是 \(j\),上一个在 \(i\) 以前的最大价值。

转移:\(f_{i,j}=\max(f_{i-1,j},f_{\min(j-k,i-1),i}+a_j)\)。

代码链接:https://paste.ubuntu.com/p/5VHF9J23KG/

E

考虑离线。

首先将两端点属于同一州的边缩起来,不属于同一州的就拿一个哈希表记录下来。

对于询问 \((u,v)\),把它们按照 \((s_u,s_v)\) 分类,同一类一起处理。

处理每一类询问时,把两端点所在的州是 \((s_u,s_v)\) 的边缩起来,并查集直接查询。需要注意的是并查集要用可撤销并查集,因此只能按秩合并,不能路径压缩。

分类的思想很值得借鉴。

时间复杂度 \(\mathcal{O}(Q+(N+M)\log(N+M))\)。

代码链接:https://paste.ubuntu.com/p/CGHHxPqDGV/

上一篇:JOIG2022 题解


下一篇:Ubuntu获取root桌面版权限