7.29模拟赛总结

我挂分 我偏挂分（痛哭流涕

今天没那么困！ 感觉很有精神！

时间安排

7.30-8.30

看T1 感觉没啥想法 感觉是不是个什么最优策略题 但我不知道最优策略是什么 嘎

8.30-10.00

写T2 想了半天也只会拓扑

10.00-11.30

想T2 以为能过第二个点 猛冲（但其实空间时间开销同阶 泪目了 mle

11.30-12.30

又想了一会T1 还是不会

题目分析

啊？ T1怎么过了998244353个人啊

T1

？

upd

$ceil（log(m))$ 可以取得100分的好成绩捏喵！

正解是dp 也就是我没想出来的最优策略 $f[x,y]=f[x-1,y-1]+f[x,y-1]+1$

$f[x,y]$ 是用$x$ 个牛油果 扔 $y$ 次可以确定的最大范围

问题可能是 我认为这个有一个贪心的策略 但其实dp）

T2

$n^2$ 建出来dag之后跑

upd

不太好的一点是没想到可以归并排序做链

T3

考虑可以把询问放在边上 然后按照追击/相遇分别计算

可以剪枝剪进2s内（nm)

就是空间开销有问题）

upd

考虑转换成以时间为横坐标 深度为纵坐标的线段

那么答案就是线段的交点

树剖后 用set维护这些线段

有一点点像 sdoi 游戏