Noip 2023

A

事实上只需要比较最大一个和最小一个就可以了。

注意排序后的字符串是递增或递减的，是用递增字符串与其他的递减字符串比较。

B

考场不会。

综述：

对 DFS 的详细描述：

Noip 2022

悲惨的一年，对这一年真题有问题别问学长。

A

签到。当时我写了个三方还艹过去了。

对于三方的优化做个前缀和即可，可以看出今年写代码的速度比去年高了很多。

B

瞄准颜色种类 k=2n-2 做，每个栈分配两个颜色，剩下一个缓冲栈。如果新插入的数和栈顶颜色一样就消掉，如果和栈底颜色一样就丢进最后一个栈里消栈底。

还有一个爆搜，感觉不好打。

C

15pts

爆搜枚举每一个点和每一条边，再判断是否能够连通。

35pts

爆搜每个点，枚举每条边被割的情况，判断是否能连通。割不断的边就可选可不选，答案累加 \(2^{E}\)。

性质 A

链的情况。

若只选一个点，所有边都可选可不选，答案为 \(2^{n-1}\)。

若选择多个点，设最左边的点为 \(l\)，最右边的为 \(r\)（\(l\)、\(r\) 都是选了的），\(l \ne r\)，可以枚举左右端点 \(l,r\)。

这样 \(l,r\) 之间的边全要选，其他的边可选可不选，\(l,r\) 之间的点可选可不选。

边的贡献是 \(2^{n-1-(r-l)}\)，点的贡献是 \(2^{r-l-1}\)，乘起来发现贡献就是 \(2^{n-2}\)，与 \(l,r\) 无关。

\(l \neq r\) 的选取方案有 \(C^{2}_{n}\) 个，只选一个的选取方案有 \(n\) 个。

D

数据结构题，正解是个古怪的线段树，我们来考虑如何骗到 20pts。

离线询问，将每个询问按右端点排序。

枚举 \(r\)，设当前状态下 \(x_i=\max\limits^{r}_{j=i} a_j\)， \(y_i=\max\limits^{r}_{j=i} b_j\)，\(f_i\) 是区间 \([i,r]\) 的总贡献，即 \(f_i=\sum x_i \times y_i\)。（对每个 \(r\) 累加，即左端点固定为 \(l\)，右端点可选范围为 \([i,r]\) 的总贡献，最终 \(f_i\) 的区间会变成 \([i,n]\)）

对询问 \([l,r]\)，答案就是 \(\sum \limits^{r}_{i=l} f_i\)，时间复杂度 \(O(n^2+nq)\)。

幻想时间

这样可以拿到 100+15+45+20=180pts，比 czh 高。

再要提高至少要写出 T3，不在水平范围内qwq。

Noip 2021

A

埃筛预处理即可，注意多处理几个。

B

正解是 DP，但可以爆搜，搜完发现还可以记忆化，拿到 50pts。

C

模拟退火可做，甚至有满分的优秀退火。

SA 的关键在于设置初始状态，一定要是一组较优解。

D

是个神仙题，跑了。

幻想时间

100+50+80+0=230，比 yed 高一拿得多。

但是 WTR 会 T2 正解，失败。