JOI 2022 final
_YangZJ_
·
·
个人记录
还有机会做剩下的场吗？？？
「JOI 2022 Final」星际蛋糕推销
简单题。
「JOI 2022 Final」自学
简单题。
首先 a 对 b 取 \max ，然后二分答案，先贪心上课，看能否补够即可。
「JOI 2022 Final」选举
*贪心，性质优化 \text{dp}
首先很容易观察出如下性质：
- 所有人一定在同一个地方演讲最优（尽快得到下一张选票或者下一个协作者）。
- 一定是先拿到所有的协作者，再去拿剩下的选票。
- 拿协作者的顺序一定是按照 b 从小到大。
然后按照 b 从小到大排序后很容易设计出一个 \text{dp} ，首先枚举最终协作者个数：m 。
然后设 f_{i,j,k} 表示考虑了前 i 个， 选好了 j 个协作者，另选择了 k 个只拿选票的最优解。转移是容易的。
这样总复杂度是 O(n^4) 的，无法通过。
观察这个 \text{dp} ，打表发现答案关于枚举的 m 是一个 单峰函数，并且似乎有凸性 ，在暴力 \text{dp} 上套一个二分就行了。
复杂度是 O(n^3\log n) 的，常数很小，可以通过。
考虑继续优化，这里需要观察到一个性质：
- 按照 b 从小到大排序后，一定存在一段前缀，满足这段前缀要么选 a 要么选 b ，后面的部分选择 a 最小的几个。
正确性是很显然的，因为如果一个很小的 b 让他作废的话，那后面还要选 b 的话一定不优了。
这样预处理对于每个后缀 i ，预处理出 g_{i,j} 表示后缀 i 中最小的 j 个 a 之和。
设 f_{i,j} 表示考虑了前 i 个，有 j 个选 b ，剩下 i-j 个选 a 的最优解，转移同样容易。
统计答案的话枚举那个前缀 i ，贡献就是 f_{i,m}+g_{i+1,k-i} ，做一次 \text{dp} 是 O(n^2) 的。
总复杂度 O(n^3) ，是这道题目的正解。
将优化后的算法套三分。
可以做到更优的复杂度 O(n^2\log n) 。
「JOI 2022 Final」铁路旅行 2
*倍增，\text{RMQ}
跟前不久的模拟赛题做法一样，考虑倍增，分别预处理出 g_{i,k},f_{i,k} 表示从 i 出发乘坐最多 2^k 次列车 最左 / 最右 分别能到哪里。
枚举答案的时候转移与上面更新类似。
复杂度 [$O(n\log^2 n)$](https://loj.ac/s/1931432) 。
### [「JOI 2022 Final」沙堡 2](https://loj.ac/p/3666)
***哈希，暴力，扫描线**
首先发现这样一个性质：
- 每个点下一步一定是走到周围比其权值小的最大的一个点。
一个矩形合法的充要条件是：除了矩形中最大值以外，其他点的入度均为 $1$ 。
根据边界情况，维护若干哈希数组，用二维前缀和容易 $O(1)$ 判断一个矩形是否合法。
复杂度 $O((nm)^2)$ ，可以通过 $80pts$ 。
之前想得那个哈希判定需要求个矩形最大值，不方便用扫描线。
考虑这样一种特别的哈希方式：
记 $l$ 为周围权值小于其的最大的权值，不存在则 $l=0$ ；$r$ 为周围权值大于其的最小的权值，不存在则 $r=inf$ 。
那么一个点的权值 ```val[i][j] = r < inf ? a[i][j] : inf``` 。那么一个矩形合法的话，中间部分都被消去了，链头权值为 $inf$ ，链尾为 $0$ 。
因此矩形的权值为 $inf$ 则说明这个矩形合法。
如果 $n>m$ 则行列交换。
枚举行的区间，对列做扫描线，对于每个右边界，用 ```map``` 计数合法的左边界。
复杂度 $O(n^2m)$ 乘上一个 ```map``` 的复杂度，是 $O((nm)^{\frac{3}{2}})$ 级别的。[submission](https://loj.ac/s/1932561) 。