2023.4.17
CF1820C The Butcher
思路口胡:最后答案显然要么长跟最大的一样,或者宽跟最大的一样。先考虑长跟最大的一样。然后考虑贪心,每次删除长一样或宽一样的宽或长即可,只要能递归到中任意长货款为 。
trick :这是一道边界删除问题。跟前面有道题类似,就递归下去。
trick :有时候合并题可以反向变成删除题。
CF1820E The Fox and the Complete Tree Traversal
思路口胡:存在某种图,不能为该数的子图,若是,则不存在方案。然后构造就是以跳直径隔着一点一点地跳,旁岔可以带过。
trick :当在树上跳跃的时候,不妨可以从 dfn 序来思考。
2023.4.19
P6864 [RC-03] 记忆
思路口胡:每次加入一对括号的时候,在任何时刻,整个括号序都是匹配的。我们只用考虑每次加入时的状态。这个可以那线段树来维护状态矩阵。同时,是对操作线段树。
trick :有时候操作独立性强的时候,撤销操作只用将操作线段树取反即可。
2023.4.20
P6105 [Ynoi2010] y-fast trie
思路口胡:可以将问题拆成两个子问题来回答。对于 这个问题是好回答的。对于另一个问题,我们只要每次找到最优匹配,然后若两组最优匹配是包含关系,那么包含的关系是更有的,所以一个点只有一个最优匹配。
trick :对于
这种问题可以拆成
和
两个子问题来回答。
trick :每次修改时,若是单独影响,并且题目要求极值,那么可以在全局设个平衡树来维护。
P6617 查找 Search
思路口胡:每次计算只要找到和距离 最近的前驱。然后用线段树维护即可。然后每次修改只有
级别。
trick :对于记录前驱的点,我们每次单点修改都是变动
级别的。
CF840C On the Bench
思路口胡:不口胡。
trick :对于
是否为完全平方数的判断,可以转换成
去除所有平方因子以后是否相等就行。
2023.4.21
[AGC017D] Game on Tree
口胡思路:。
trick :同口胡思路。