杂题总结 Vol.3

\(\def\EZ{\textcolor{#51af44}{\text{EZ}}}\EZ\) 表示简单，10分钟内就能想到。
\(\def\HD{\textcolor{#3173b3}{\text{HD}}}\HD\) 表示中等，能独立想出
\(\def\IN{\textcolor{#be2d23}{\text{IN}}}\IN\) 表示困难，独立思考能想到 \(50\%\) 以上
\(\def\AT{\textcolor{#383838}{\text{AT}}}\AT\) 表示非常困难，独立思考只能想出 \(50\%\) 以下

JOI 2024 Final [2024-09-18]

P10208 [JOI 2024 Final] 礼物交换

\(\IN\)

本题再次提示我们，忘记了一个定理不要慌。。。也许不要定理结论也能出来。

由于本题连边关系非常特殊，排序之后就会变成前缀后缀。如果把 AB 排序放到一个序列里面，那么此时就可以发现，我们要的匹配就是要求 B 与右边的 A 匹配，而且不能匹自己。

我们发现每个 B 都是往后匹配的，且每个 B 往后都至少有其自己的 A，但是不能只有其自己的 A，都必须至少要有一个别人的 A，对于所有的，包括最后一组 BA 都是这样，换句话说，如果从 B 到 A 是一个区间，每个区间都必须至少有一个相交（包含或被包含也算相交）的才可以。

再次理解一下，一个区间 BA 右边如果有 K 个 BA，那么 B 右边至少也是有 K+1 个 A 的，但是自己那个 A 不能用，如果要用别人的一个 A，就必须把自己的 A 拿出去交换，换句话说，当前这组 BA 至少有一个 B 能够吃到这个 A，否则别人的就不够了。

每次都排序是不行的。但是这里有一个 Trick，如果多次询问在一个区间内是否存在满足条件的元素、元素对，可以对于每一个位置、元素求出上、下一个满足条件的元素在哪里，从而转化为只关于判断前驱后继位置的询问，可以考虑离线询问后扫描线做。

典例：P1972 [SDOI2009] HH的项链

P10207 [JOI 2024 Final] 马拉松比赛 2

\(\IN^{-}\)

要对自己有自信，不要摆，仔细考虑每一个想法。

本来想出了 81pts 的 DP，但是我好像不太相信自己能写出 DP，然后没继续想。

有一种天真的想法是从 \(S\) 出发之后先走到一个端点把球全拿了，然后折回终点。

但是这个是不对的，因为有可能有一边球特别多，全拿了会导致代价飙高。

以上要对必须满足两个性质：1. 折返的时候经过的球必须拿 2. 靠远的必须比靠近的先拿

2 是肯定正确的。但是 1 不一定是对的，实际上不一定要一次性拿走。

但是这个告诉我们，保留的球一定是一段。故可设 \(f_{l,r,0/1}\) 表示若从左边第一个开始，当前还剩下 \([l,r]\) 中没有拿，且当前在左边/右边端点。计算答案的时候把它与 \(S,G\) 拼上即可。当然，也不一定从左边第一个开始，再设一个 \(g\) 表示从右边第一个开始的那种，转移一样。