CSP-JS 2022 VP 记录

· · 个人记录

本来想着去年我是 SD 省第一，但是没有 AK，今年能不能有点长进。

然后 SD CSP-J/S 都取消了 /ll/ll/ll。

CSP-J

我的评价：

今年这难度不得一车 AK 的？

建议 swap(T3, T4)。

先开 T1，显然 a>1 时暴力即可，a=1 时输出 1 即可。

再开 T2，不知道有没有选手认出来，这是 RSA 加密。

推一推式子可以发现是一个萌萌的二次方程，直接套求根公式即可，记得开 __int128。

再开 T3，不是很可做，看 T4，发现是个萌萌 DP。

先把 k 换成 m，然后按照 x 坐标排序，x 坐标相同就按照 y 坐标排序，这样从第 i 个点走到第 j 个点一定有 i<j。

设 f_{i,k} 表示仅考虑第 1\sim i 个点，已经加上了 k 个点，最长的路径，转移显然。

发现要预处理 g_{i,j} 表示从第 i 个点到第 j 个点最小要放几个点，随便 DP 一下就行。

再回来做 T3，发现转后缀表达式然后扫一遍不就是萌萌题了吗，于是 AK 了。

CSP-S

先开 T1，慌了，为什么不会。

然后果断放弃，开 T2。

T2 好像是个萌萌 DS，用形式化的语言书写出来：

给你一个长度为 n 的数组 a，和一个长度为 m 的数组 b，q 次询问，每次询问给你 l_1,r_1,l_2,r_3，保证 1\le l_1\le r_1\le n,1\le l_2\le r_2\le m，求：

\max_{l_1\le i\le r_1}\left\{\min_{l_2\le j\le r_2}a_ib_j\right\}

那不就是个萌萌 DS 吗！

我们只需要对每个数组开一个线段树，维护区间最大正数、最小正数、最小负数、最大负数、有没有 0，然后询问搞一搞就行了，O(q(\log n+\log m)) 应该能过。

回来思考 T1，O(n^2) 的算法显然是想让我们枚举两个点，枚举 B,C 会非常好做，然后就会了。

被不连通的图坑了，然后 AC 了。

T2 也写完了，一交，95。

看 T3 和 T4，T3 题面太长了，不想看，T4 看上去比较简单。

首先按照国际惯例拆成 s 到 LCA 和 LCA 到 t，LCA 搞一搞就行。