在 Splay 学习笔记(一)中,我们学会了用 Splay 维护二叉排序树,来实现了有序集合的查询 / 修改操作,接下来,我们来研究 Splay 在维护数列中的用途。
「HNOI2004」宠物收养所 - set
发表于
|
分类于
OI
有 N
(<= 80000)个宠物或领养者,每个宠物或者领养者有一个特点值 a
,每次当宠物或领养者到来时,从已有的当中匹配一个与其特点值相差最小(且特点值较小)的并删除,计算所有的领养特点值差的总和。
「CodeVS 3269」混合背包 - 背包 DP
发表于
|
分类于
OI
背包体积为 V
(<= 200,000),给出 N
(<= 200)个物品,每个物品占用体积为 Vi
,价值为 Wi
,每个物品要么至多取 1
件,要么至多取 Mi
(> 1)件,要么数量无限,求装入背包内物品总价值的最大值。
「NOI2002」银河英雄传说 - 并查集
发表于
|
分类于
OI
有 30000 个元素,初始时每个元素以单独的队列形式存在,支持一下两种操作:
1.动态合并两条队列,将 x
元素所在队列首合并在 y
元素所在队列尾;
2.查询 x
与 y
是否在同一条队列中,若是,查询 x
与 y
间隔元素数量。
共 500,000 次操作。