20231028 NOIP#26 总结

时间安排

7:40~8:20

看题，\(A,B,C\) 差不多会前一半，\(D\) 感觉很贪心但不知道对不对。

8:20~8:05

写 \(D\) 的贪心。

8:25~8:50

想了一会想出来 \(A\) 写了。

8:50~9:40

写 \(B,C\) 的暴力

9:40~10:50

想了半天发现性质会 \(B\) 了。

10:50~11:10

\(C\) 特殊性质拼包

11:10~11:50

罚坐。

总结反思

• long long要开够
• 留时间回顾代码

题解

A.新定义

\(1\) 操作暴力模拟，\(2\) 操作按序列单调性二分。

B.DP

发现 \(a,b\) 互不干涉，所以分开 \(DP\)。预处理长度为 \(i\) 的序列填 \(a/b\) 个奇（偶）数的合法方案数。
设 \(f[i][j]\) 表示长为 \(i\) 的序列填 \(a\) 个数，有 \(j\) 个出现偶数次（不满足）的方案数，显然答案为 \(f[i][0]\)。有转移方程:\(f[i+1][j+1]+=f[i][j]\times (a-j)\ \ \ \ f[i+1][j-1]+=f[i][j]\times j\)
另一个的 \(DP\) 同理。
答案是 \(\sum C_n^i\times f[i][0]\times g[n-i][0]\)

C.~

首先反向存边，从 \(1\) 出发走 \([x_i,y_i]\) 里的边到 \(p_i\)，看是否可行。考虑每条边依次“开放”，即先开放 \(1\) 号边，再开放 \(2\) 号边 \(\cdots\)
维护 \(g[y][p]\) 表示开放 \([1,y]\) 条边时，能从 \(1\) 走到 \(p\) 的最大左端点为 \(g[y][p]\)，即开放 \([g[y][p],y]\) 时 \(p\) 合法，开放 \([g[y][p]+1,y]\) 时 \(p\) 就不合法了。那么对于一个询问 \((p,x,y)\)，只需要看 \(x\) 是否 \(\leq g[y][p]\) 即可。
考虑如何递推 \(g\) 数组。
设第 \(y\) 条边为 \((u,v)\)，这时只有 \(v\) 的最大左端点可能发生变化。即 \(\forall i\in[1,n]\& i\not = v,g[y][i]=g[y+1][i]\)，而 \(g[y+1][v]=\max(g[y][v],g[y][u])\)。特别地，当 \(u=1\) 的时候，\(g[y+1][v]=y+1\)。
所以直接把 \(g\) 使用可持久化数组记录即可。

D.树形 DP

考虑树形 \(DP\) 的想法，最优方案可能多次走进某一个子树，每次走一个联通块。这些联通块满足：一定按拓扑序排列，收益一定大于 \(0\) 且以上升结束。则记录最低点和初值的差 \(p\)，终值和最低点的差值 \(g\)。可以理解为进入这个连通块，付出 \(p\) 的花费之后，才能获得 \(g\) 的收益。
维护子树内的联通块序列，满足：按拓扑序排列，\(g>p\)，\(p\) 单调不减。合并时，子树之间的直接互相插入，并把 \(x\) 作为一个单独连通块放在开头。
但可能会导致序列不满足 \(g>p\) 和 \(p\) 单调不减的条件，解决方法是将其与后面的联通块合并，更新 \(p,g\)，直到满足条件。若全部合并后还不满足，则 \(x\) 的子树不取更优。
这个可以用 \(set+DSU\) 维护联通块实现，复杂度 \(O(n\log^2 n)\)