希胤

分类

dp模板(4) dp狂练(1) 图论模板(4) 小知识(3) 数论模板(1) 未归档(3) 杂模板(5) 题解(36)

/ 注册

TA的专栏 23篇文章 0人订阅

12篇文章 800人学习

线段树和数状数组经典例题

11篇文章 281人学习

全部文章（共60篇）

HH的项链

延迟操作（离线）分析：出现了新颜色，才能算贡献，如：{1，2，3，4，3，5}可以看作{1，1，0，1，1，1} ，同一种颜色，位置更后的更优（对L来讲），所以当相同的颜色出些后，计算后者的贡献，并把前者产生的贡献抹除；而树状数组tr[i]维护的是位置i之前所有的贡献和 #include<...

2021-10-15

0 260

网络流

相关概念网络流（似水流）（整张图流出的水流）网络流的本质是水流问题源点：水流出的点(只有一个) 汇点：水流进的点(只有一个) 弧(边)：水流容量(用小c表示) 可行流：一条路径(s ==> t)和(此路径能流过的最大水流)【可行流 = 路径边 + 能流过的最大水流】可改进路(增广路)：...

2021-08-29

0 395

图的连通性

有向图：割点：删掉不连通割边（桥）：删掉不连通连通分量：极大子图点双连通图：删任意一点仍连通，即没有割点边双连通图：删任意一边仍连通，即没有桥点双连通分量：极大点双连通子图边双连通分量：极大边双连通子图（单点也是边双连通分量）边双连通：删桥后，双方都是边双有向图：弱连通：单...

2021-08-20

0 321

分块（模板）

题目：数列分块入门 3 参考博客分块也是对区间操作虽然没有树状数组快但是什么都能维护未闻花名，但识花香 #include<bits/stdc++.h> using namespace std; namespace{ template<typename T> inli...

2021-05-29

0 273

扫描线模板

参考博客题目：P1502 窗口的星星线段树处理的是线段（一维几何计数）（张昆玮）线段树就是处理线段上的区间问题扫描线把矩形转化为线段（二维转一维）扫描线就是去除一维，使一堆矩形变成一堆线段，最后再使一堆线段合并成一条线段扫描线一般处理矩形有关的问题听懂了思想，代码随便看一份都可以已过...

2021-04-27

0 281

二分图

二分图：图中有两个点集，集合内的点互不连边，两个集合的点互相连边二分图最大匹配：在二分图找到最多的匹配数匈牙利算法：时间复杂度：邻接矩阵:O(n^3) 邻接表:O(n*m) int e[N][N]; //邻接矩阵 //可以用邻接表稍微优化一下 int vis[N],link[N]; ...

2021-04-25

0 308

带权并查集（模板）

网络分析参考博客带权并查集详解带权并查集（核心）： 1、路压要维护权值（考虑怎么维护） 2、合并时也要维护权值（考虑怎么维护） 3、并查集一般对根节点进行操作 dis与差分： 1、差分是当前元素与前一个元素的差值，dis是当前节点与父节点的差值 2、差分做前缀和为原数组，dis对祖先做前缀...

2021-04-17

0 221

lca之树上倍增（模板）

题目参考博客参考代码 #include<bits/stdc++.h> using namespace std; int const M=5e5+7; int const N=5e5+7; int n,m,s; struct node{ int a,next,len; }e[M<...

2021-04-01

0 311

双向bfs

参考博客 #include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e3+7; int n,m,sx1,sy1,sx2,sy2,f; char ch[N][N]; struct L{ ...

2021-03-27

0 511

小A的位运算

异或大值即可 #include<bits/stdc++.h> using namespace std; #define ll long long int const N=5e6+7; ll a[N]; int n; bool cmp(ll a,ll b){ return a>...

2021-03-25

2 700