何事秋。

分类

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章（共461篇）

线段树合并：

某一天马学长给我看了一个lca的题目，然而确实是lca+树上差分，但是仅仅有lca和树上差分解决不了，然后我就去面向题解编程了。可是这个线段树合并是个什么东东。。。然而今天看书，突然看到了这个线段树合并。就写一下了。 %mmh。 P4556 [Vani有约会]雨天的尾巴：题目背景深绘里一...

2020-09-04

0 447

离线分治算法：

一、基于时间的分治算法 --------CDQ分治例题：AcWing 254. 天使玩偶 Ayu在七年前曾经收到过一个天使玩偶，当时她把它当做时间囊埋在了地下。而七年后的今天，Ayu却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。我们把Ayu生活的小镇看做一个二维平面直...

2020-09-04

0 473

基环树：

把树再加一条边，形成一个环。处理基环树的方法，一般就是找出环，并且把环当成广义上的树根，处理树，然后处理环。一、AcWing 358. 岛屿：你准备有限一个公园，该公园由 N 个岛屿组成，当地管理部门从每个岛屿出发向另外一个岛屿建了一座桥，不过桥是可以双向行走的。同时，每对岛屿之间都有一...

2020-09-04

0 350

可持久化Trie（可持久化字典树）：

构建可持久化Trie所需的空间和时间复杂度都是字符串的总长度的线性函数。比例系数为字符集大小。例题：AcWing 256. 最大异或和：给定一个非负整数序列 a，初始长度为 N。有 M 个操作，有以下两种操作类型： 1、”A x”：添加操作，表示在序列末尾添加一个数 x，序列的长度 N...

2020-09-04

0 514

二叉查找树与平衡树初步（Treap）：

例题：洛谷 P3369 【模板】普通平衡树题目描述您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1。插入x数 2。删除x数(若有多个相同的数，因只删除一个) 3。查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名) 4。查询...

2020-09-04

0 395

主席树——可持久化线段树：

终于开始学这个了，水平不够，时间来凑。先%一发马学长。例①：没错又是这个题目，区间第k小。 K-th Number POJ - 2104： You are working for Macrohard company in data structures department. After ...

2020-09-04

0 332

欧拉降幂：

今天欧拉降幂，怎么操作姿势都不对。。。。。例题： The Preliminary Contest for ICPC Asia Nanjing 2019： B super_log：求 b 个 a ^ a ^ a ^ a ^ a ^ a ^ a : 很明显就是欧拉降幂：然而就这破题。。卡了我2...

2020-09-04

0 402

The Preliminary Contest for ICPC Asia Nanjing 2019：D. Robots（期望dp）：

题目链接： D. Robots 题目这一题应该是比较常规的期望dp，但是比赛的时候被b题卡到飞起，当然这题就没有出。。。。拓扑序和dfs都能解决，于是写了个dfs，记得及时回溯就好啦。 #include<iostream> #include<cstdio> #i...

2020-09-04

0 404

自适应辛普森积分：

例①：Ellipse HDU - 1724： Math is important!! Many students failed in 2+2’s mathematical test, so let’s AC this problem to mourn for our lost youth… Loo...

2020-09-04

0 391

The Preliminary Contest for ICPC Asia Xuzhou 2019： J. Random Access Iterator（概率dp）：

其实这题也是比较简单的，只不过我们队开这题的时候已经快结束了，导致满脑子混沌。。。以至于我样例手动模拟都算错了概率。。。。。题目连接：点击这里 dp[u] 表示 u这个点向下能到达最深深度的概率，因为对于每个点要找k次，只要其中有一次能到达最深即可。但是对于不能到达要所有次都不能到达，比较好求...

2020-09-04

0 373