NOIP 计划 R15
NOIP 计划 R15
\(\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\%\) 以下
Overview
\(\HD\)
\(340/400\text{pts}\) Very Good!
T1 railway
\(\EZ\)
考虑分三种情况讨论，题目条件等于一部分点可以花费 2 的代价传送：
-
第一种是不经过可变边
-
第二种是要花 2 的时间传送
性质：只可能传送一次 -
第三种是要经过菊花的中心点，
考虑是 1---固定端a 的最小+1+n---菊花中心（不经过菊花边，否则等价于情况 2）
或者是 n---固定端b 的最小+1+1---菊花中心
T2 recipe
\(\EZ\)
直接猜结论，先按 \(c\) 排序，然后依次插入线性基，如果能够成功插入就累加答案。
T3 cross
\(\IN^{-}\)
离正解最近的一次
考虑求每一条边的贡献系数，长下面这样：
对每一条边都是一样的，不同的只是关于他们在区间中的位置。
接下来有两种本质相同的状态设计方法，两种都可以互相推导，也都可以导出最后的结论：
一种是直接按照题目中的 dist 来设计，考虑容斥，有转移：
另一种是，设一条边左边有 \(i\) 个点，右边有 \(j\) 个点时的贡献为 \(f(i,j)\)，转移是相同的，或者设第 i 行第 j 个贡献系数是多少，也是可以一样转移。
无论是哪种设的方式，我们都能够看出在一定长度之后，dist 或者 f 里面就会累积一定数量的 2，结合大样例以及模数，我们发现当询问的路径长度大于 \(65\) 时，答案为 \(0\) 。
结合第二种设贡献的方案，进行暴力即可。
另外，本题有一个特殊的性质，以下称能够转移到状态 \(x\) 的状态为 \(x\) 的子状态，区间 dp 时，长度相等的区间的子状态所构成的结构是相同的，故可以从最顶上向下反着推，取最上面若干层的答案（若询问的路径长度为 len 则应该取最上面 len 层的最下面一层）作为最终贡献系数，这是可以的。 （way.exe 的做法）