2021/11/3模拟赛

$7:50-8:30$
看题&＃xff0c;觉得 $T3$ 比较像之前做过的题&＃xff0c;$T4$ 的样例都给的比较难受。
$8:30-9:40$
尝试用各种方法搞 $T3$ &＃xff0c;一开始觉得放到树上做各种东西的传递还是不太好调试&＃xff0c;跑树的时候重新连边&＃xff0c;当成一个有向无环图来搞&＃xff0c;然后传递的时候每个节点再用 vector 记录下当前单调上升序列的最大值和长度&＃xff0c;然后有需要判断的时候做类似背包的状态转移&＃xff0c;但是状态转移比较困难且 STL 用着还是比较吃力了些。
然后就还在树上做&＃xff0c;自下而上传递些大小和最大值之类的&＃xff0c;我觉得如果选了 $i$ 号节点&＃xff0c;那么它的子节点怎么选择都是固定的&＃xff0c;很有 动态规划 的味道了&＃xff0c;但是卡在了一个节点如果有多个儿子的情况上。在纸上写写画画也没有完全解决&＃xff0c;感觉这还得看有多个子节点的节点能不能选择&＃xff0c;且上方的改变可能会影响下边的好多都发生改变。
然后就想把每条链拆开来做&＃xff0c;但是不会写。
然后考虑能不能设定某个点必选&＃xff0c;但是这样每次设定一个必选的点的话&＃xff0c;对于其他链又没有影响&＃xff0c;还是会陷进刚刚的怪圈里。
$9:40-10:50$
$T1$ 中每个区间选择的先后顺序对结果无影响&＃xff0c;所以 dfs 得到每个点选或不选的结果&＃xff0c;然后计算。时间复杂度 O(2N)O(2^N)O(2N) 左右&＃xff0c;能过第一档分。然后考虑第二档分&＃xff0c;数据范围应该够一个 O(N2)O(N^2)O(N2) 的算法&＃xff0c;所以就考虑 动态规划 &＃xff0c;先后无影响&＃xff0c;且读入就是每个区间的左右端点&＃xff0c;所以就开始想区间DP。把读入的每个区间里包含了多少个区间算出来&＃xff0c;然后看任意一个区间&＃xff08;左右端点恰好是之前读入的某个区间的左端点和某个区间的右端点&＃xff09;中有多少个端点&＃xff0c;提前用递推处理出来组合数&＃xff0c;然后对于每个刚刚处理出来的区间搞个&＃xff0c;然后整个区间里对这样的区间搞乘法原理。但是最后没太推出来。
相当于开考了 $3h$ 才拿了 $20$ 分&＃xff0c;已经开始很慌了&＃xff0c;所以那 $20$ 分也没打表也没对拍也没扣数据验证一下。
$10:50-11:20$
基于刚刚就用 O(2N)O(2^N)O(2N) 看每个选不选然后再处理&＃xff0c;这时候我又想到 $T3$ 的第一档分也可以看每个选不选&＃xff0c;然后检验是否成立&＃xff0c;并同时求出最优的答案。但是没调试出来。
$11:20-剩下的时间$
搞 $T2$ 感觉也是组合数学 &＃43;动态规划&＃xff0c;最后没有搞出来。

$T3$ 搞上头了&＃xff0c;而且节奏错了&＃xff0c;还是从低档分写推高档分比较稳一点&＃xff0c;正解的话是经典的求树上最长上升子序列。题解中的启发式合并根本没想到。平时题做太少了。

$T1$ 没有任何措施去保证必得分&＃xff0c;搞 $T2$ 的时间匀出来些打个表&＃xff0c;扣数据验证验证啥的&＃xff0c;也该稳拿些分。而且把题想太难了&＃xff0c;正解其实主要就一个有点像组合的小递推式
fi&＃61;2∗fi−1&＃43;2xf_i&＃61;2*f_{i−1}&＃43;2^xfi​&＃61;2∗fi−1​&＃43;2x
而 $x$ 就是右端点小于 rir_iri​ 的区间的数量&＃xff0c;读入的时候顺便求个前缀就行。
或者线段树维护DP也可以。