itoshiki_Treap

分类

题解(3)

/ 注册

全部文章（共3篇）

题解 | #XJCPC2024 部分题解#

悲报：今年好像没有统一题解了。 H Magic Transport 首先一个显然的结论：给定若干带体积的物品，有限容积选择的物品数最大化，显然应当按照体积递增选择若干件，证明考虑交换法和反证法。我们维护的东西就变成了：给定一个可重集，支持查询上面那个东西和插入元素，上面那个东西转化成查询总和不超过...

2024-05-19

6 413

题解 | #G 魔法树#

计数类树形 DP 的常用思路之一为决策边，将点或点所在连通块状态放在主状态的附加维中。例如CF461B，NOIP2022 T3都可以用这个思路解决。回到本题，决策边的提示已经挂脸上了，考虑状态设计：注意每个点所在的连通块可以通过是否和儿子连边从而和儿子合并成一个大连通块来改变奇偶性，但是答案中整体...

C++ 计数

2023-10-21

0 312

题解 | #Genealogy in the trees#

D Genealogy in the trees 考虑把树拍平到 dfn 序列上，那么题目要求即为对于每个求有多少点对满足：其中为点子树大小，但本式中最后一部分不需要显式处理，只需在结点退栈时记录时间戳即可。放到二维平面上，将第一个式子的元素作为轴坐标，第二个式...

C++ 树状数组扫描线图

2023-10-18

0 445