何事秋。
何事秋。
全部文章
数据结构基本算法
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)
数据结构瞎乱写(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)
归档
标签
去牛客网
登录
/
注册
何事秋。的博客
全部文章
/ 数据结构基本算法
(共69篇)
笛卡尔树
例①、POJ 2201: 题目: 笛卡尔树:笛卡尔树中的每个节点有两个数据域key,val,对于数据域key,满足二叉搜索树性质,对于数据域val,满足最小堆性质。给出N个节点,1<=N<=50000,每个节点由一对key,val构成,判断能否根据这些节点构建一颗笛卡尔树,如果可以构建则...
2020-09-04
0
493
P4929 【模板】舞蹈链(DLX)
题目背景 本题是舞蹈链模板——精确覆盖问题 题目描述 给定一个N行M列的矩阵,矩阵中每个元素要么是1,要么是0 你需要在矩阵中挑选出若干行,使得对于矩阵的每一列j,在你挑选的这些行中,有且仅有一行的第j个元素为1 输入格式 第一行两个数N,M 接下来N行,每行M个数字0或1,表示这个矩阵 ...
2020-09-04
0
686
P5903 【模板】树上 k 级祖先
给定一棵 n 个点的有根树。 有 q 次询问,第 i 次询问给定 xi, ki,要求点 xi 的 ki 级祖先。 保证ki合法。 一、树链剖分——重链剖分 O(n+qlogn): 7.46s #include<iostream> #include<cstdio> #i...
2020-09-04
0
490
P3919 【模板】可持久化数组(可持久化线段树/平衡树)
其实就是用主席树来实现的可持久化数组: #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include...
2020-09-04
0
348
P3402 【模板】可持久化并查集
①用可持久化线段树加按秩合并实现: #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<...
2020-09-04
0
403
P3380 【模板】二逼平衡树(树套树)
您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: ①查询k在区间内的排名 ②查询区间内排名为k的值 ③修改某一位值上的数值 ④查询k在区间内的前驱(前驱定义为严格小于x,且最大的数,若不存在输出-2147483647) ⑤查询k在区间内的后继(后继定义为严...
2020-09-04
0
448
P6086 【模板】Prufer 序列
你相信缘分吗,反正我是很相信,前几天刚看了prufer序列这个东西今天就看到了洛谷上的模板题。 可是这个题O(n),还卡读入就很难受了。 #include<iostream> #include<cstdio> #include<algorithm> #inclu...
2020-09-04
0
378
不可视境界线(inv) KD-Tree 模板
这个题可以转化一下。 dp [ i ] = min ( dp [ i ] , sqrt ( dp [ j ] * dp [ j ] + dis ( i , j ) ) ) i点 ( 0 , ai1 , ai2 ) j点 ( dpj , aj1 , aj2) 就是求 i 点之前距离 i 最近的点。...
2020-09-04
0
315
P6135 【模板】虚树
一个纯虚树的模板吧,不涉及啥要处理的东西。 题目描述 给定一棵 n 个点的有根树,树上有 k 个关键点,请你构建这些点的虚树。 输入格式 第一行两个整数 n,k。 第二行 n 个整数 f 1…n,其中 fi 表示 i 的父亲。特别地,若 i 为根,则 fi =0。 第三行 k 个整数,表示关...
2020-09-04
0
357
P6136 【模板】普通平衡树(数据加强版)
题目如同洛谷普通平衡树。 数据加强, 题解rank1是 WBLT 写的,本来想学一下,但是我这个 SBT 跑的还是蛮快的,就不学了。 目前洛谷rank3,可是rank1,rank2都是SBT 写的。。为啥比我的要快。。 #include<iostream> #include<cs...
2020-09-04
0
515
首页
上一页
1
2
3
4
5
6
7
下一页
末页