月度归档: 2021年5月

14 篇文章

C++ 代码压行工具
启发 个人特别喜欢压行。 受 Mivik 和 AC 牛 的 C++ 代码压行机启发,改写增强了 Mivik 的 js 脚本,增加了按行字符数压行的功能,并在 Github 上进行了开源。 使用 链接 宽度设为 $-1$ 的时候即压成一行,否则值必须大于等于 $2$。 如果你设为其他的数值,它会默认给你压成宽度为 $2$ 的效果。 可以用来压板子,也…
AT4537 题解
AT4537:Independent Set Description 给定一棵含有 $n~(1 \leq n \leq 10^5)$ 个节点树,每一个节点可以染成黑色或白色,其中任意两个相邻的节点不能同时为黑色,求染色的方案数,结果对 $10^9+7$ 取模。 Solution 首先我们可以想到这是树形 DP,考虑如何转移。 统计总方案数需要用到一…
可持久化线段树
可持久化线段树 又称“主席树”,据说是其发明人黄嘉泰(HJT)拼音首字母同某位国家主席而得名。 但个人感觉“可持久化线段树”的英文名 "Persistent Segment Tree" 中的 "Persistent" 和“主席”的英文 "President" 也比较相似? 可持久化线段树在每次修改后都会保存一份历史版本
做干净的奥赛
全国青少年信息学奥林匹克竞赛(NOI)自 1984年创建以来, 25年间从来没有放过一次水,主办者拍胸脯起誓: 做干净的奥赛 中国青年报记者 谢湘 实习生 董博(风韦) 2009年8月28日 原文: 中国青年报 NOI 官网 绝不放水 “你敢说,你们信息学奥赛一次都没放过水?一点猫儿腻的事都没干过?” 自从中国科协书记处书记程东红7月26日在全国青…
平衡树
FHQ-Treap 例题 洛谷 P3369:【模板】普通平衡树 / 洛谷 P6136:【模板】普通平衡树(数据加强版) Description 你需要写一个数据结构来支持以下六种操作: 插入一个数 $x$。 删除一个数 $x$(若有多个相同的数,只删除一个)。 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$)。 查询排名为 $x$…
OI 的一些配置
Fread FastIO.cpp namespace FastIO { static const int BUFSIZE = (1 << 20) + 1; static char Ibuf[BUFSIZE], *I1 = Ibuf, *I2 = Ibuf, Obuf[BUFSIZE], *O1 = Obuf, *O2 = O1 + BU…
《算法竞赛中的 SSH》
原帖地址: https://www.luogu.com.cn/blog/my-vegetable-died/how-to-shengxuan-over-300(已被删除) 以及其备份:https://www.luogu.com.cn/blog/my-vegetable-died/ssH-iN-OI 警告:请勿在正式比赛中模仿!您将会被禁赛三年的风险…
扫描线
例题 洛谷 P5490:【模板】扫描线 Description Solution Code USACO 5.5:矩形周长 Picture Description Solution Code
专题——线段树
由于线段树的内容实在是太多了,因此本板块仅作一个索引。 本人线下用 Typora 编辑的时候写到后期越来越卡,写到文件大小 30KB 的时候还是选择把他们都分开。 线段树 关于线段树的内容比较多。 基础线段树 本篇为线段树的基础操作(模板,Tag 的运用)。 当然也存在一些码量极大的毒瘤题 *树状数组 都是一家的东西,拿出来总结一下。 拆位线段树 …
线段树合并
字面意思,就是合并几棵线段树。可以有两种合并方式: DFS 将每个点依次合并起来。 先将叶子节点并起来,然后依次 pushup。 存放新树也有两种方式: 新开一个树。 覆盖在原有的树上。 总之最后要把整棵树都遍历一遍,所以时间复杂度为 $O(n \log n)$。 例题 洛谷 P4556:雨天的尾巴 /【模板】线段树合并 Description 村…