• 2024-12-06P4899 [IOI2018] werewolf 狼人
    P4899[IOI2018]werewolf狼人又是欢乐的kruskal重构树捏。首先我们来仔细研读一下题目:当你是人形时,你必须避开城市\(0,1,\ldots,L_i-1\);而当你是狼形时,则必须避开城市\(R_i+1,R_i+2,\ldots,N-1\)。也就是说,从起点开始,你只能走\([L,n]\)从终点开始,你
  • 2024-11-23笔记 -- 第五章
    第五章语句简单语句表达式语句:一个表达式末尾加上分号,就变成了表达式语句。空语句:只有一个单独的分号。复合语句(块):用花括号{}包裹起来的语句和声明的序列。一个块就是一个作用域。条件语句悬垂else(danglingelse):用来描述在嵌套的ifelse语句中,如果if比else多时如何处
  • 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狼人一个想法是