- 2023-07-14P5044 [IOI2018] meetings 会议 思考--zhengjun
在NFLS模拟赛上遇到的,赛后订正过的。隔了蛮长时间的,总结一下。首先转化为笛卡尔树上后缀前缀的问题。然后考虑如何转移,发现转移形如\(f(x)=\min\{f(x)+C,kx+b\}\)的形式。可以直接线段树维护每个点的最优直线,在update的时候:如果\(f(x)+C\lekx+b\)恒成立(左右
- 2023-04-07【题解】P4898 [IOI2018] seats 排座位
思路线段树。题意可以转化成每次判定有多少个前缀满足所有结点构成矩形。首先排除确定矩阵坐标再数答案的做法,因为太难。所以考虑如何对前缀进行判定。一个简单的想法是维护前\(i\)个点中\(x,y\)坐标的最值,但这样只能暴力看矩阵中的所有元素,跑得很慢。不妨思考一下合法
- 2023-01-28【题解】[IOI2018] werewolf 狼人
题目分析这个题本身很简单,可能就是因为是IOI题所以看上去就难了些吧。其实题目就是让我们先走一段全部大于等于\(l\)的点然后再走一段全部小于等于\(r\)的点,那么能
- 2022-12-112022-12-11 #9 再异口同唱 那告别曲 逝去的一身葱茏
43AT_mujin_pc_2017_dOrientedTree头痛,想不了题。。。大概就是在直径重点断开,然后每棵子树都dp一下。先放一边吧。44P4899[IOI2018]werewolf狼人一个想法是