Menci's OI Blog

幻梦终醒,不悔华年


  • 首页

  • 关于

  • 归档

  • 标签

  • 友链

  • 搜索

Splay 学习笔记(二)

发表于 2015-12-23 | 分类于 OI

在 Splay 学习笔记(一)中,我们学会了用 Splay 维护二叉排序树,来实现了有序集合的查询 / 修改操作,接下来,我们来研究 Splay 在维护数列中的用途。

阅读全文 »

Splay 学习笔记(一)

发表于 2015-12-20 | 分类于 OI

上周周四开始学 Splay,一边看《高级数据结构》,一边看 FireStorm 的《Splay学习笔记》,现在终于弄明白最基础的一部分了。

模板请见《Splay 模板 + 详细注释》。

阅读全文 »

「HNOI2004」宠物收养所 - set

发表于 2015-12-16 | 分类于 OI

有 N(<= 80000)个宠物或领养者,每个宠物或者领养者有一个特点值 a,每次当宠物或领养者到来时,从已有的当中匹配一个与其特点值相差最小(且特点值较小)的并删除,计算所有的领养特点值差的总和。

阅读全文 »

「CodeVS 3269」混合背包 - 背包 DP

发表于 2015-11-23 | 分类于 OI

背包体积为 V(<= 200,000),给出 N(<= 200)个物品,每个物品占用体积为 Vi,价值为 Wi,每个物品要么至多取 1 件,要么至多取 Mi(> 1)件,要么数量无限,求装入背包内物品总价值的最大值。

阅读全文 »

「NOI2002」银河英雄传说 - 并查集

发表于 2015-11-23 | 分类于 OI

有 30000 个元素,初始时每个元素以单独的队列形式存在,支持一下两种操作:

1.动态合并两条队列,将 x 元素所在队列首合并在 y 元素所在队列尾; 2.查询 x 与 y 是否在同一条队列中,若是,查询 x 与 y 间隔元素数量。

共 500,000 次操作。

阅读全文 »
1…3536
Menci

Menci

355 日志
3 分类
225 标签
GitHub QQ RSS E-Mail
© 2015 — 2022 Menci
自豪地运行于 Azure 云平台 | 由 Upyun 提供 CDN 服务
由 Hexo 强力驱动
|
主题 — NexT.Pisces v5.1.2