分层图
[P4568 JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题意：
基于凸函数
基于凸函数Slope Trick - Gensokyo Algorithm Research Institute D - 红黑树 - SUA Wiki dp 凸优化学习笔记 - 寂静的海底 - 博客园 DP 的凸优化 - LarsWerner - 博客园 【学习笔记】Max 卷积 & 闵可夫斯基和 - APJifengc - 博客园 【学习笔记】DP 优化 3：闵可夫斯基和优化 DP - SoyTony - 博客园 从带权二分到闵可夫斯基和与凸生成函数 - JueFan - 博客园 浅谈斜率优化 - OI | Tiagimの小窝 = 重樱的长门 斜率优化 - OI Wiki 【学习笔记】动态规划—斜率优化DP（超详细） - 辰星凌 - 博客园
虚树
虚树 模板： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149struct edge { int v, w;};struct HLD { int n; vector<int> siz, top, parent, l, r, hson, dep; ...
断更说明
由于准备校赛，时间比较不够用，自己写的总结和题解，就没发，现在补一下。
质因数分解
acwing的最基础模板 https://www.acwing.com/blog/content/406/ 知乎大佬给的各种数据范围模板大全：https://zhuanlan.zhihu.com/p/591377294 对于其中的一部分进行提炼形成自己的模板 1.使用场景：假设有n个数需要分解，每个数最大可能是N,下面给出的这种代码的时间复杂度是O(nlogN)O(nlogN)O(nlogN) 思想：通过O(n)O(n)O(n)线性筛预处理过程中记录范围内每个数的最小质因数，分解时每个数的最多被计算O(logN)O(logN)O(logN)次。 1234567891011121314151617181920//预处理：for (int i = 2; i < N; i++)minp[i] = i;//通过这个初始化省下bool数组空间int cnt = 0;for (int i = 2; i < N; i++) { if (minp[i] == i) prime[cnt++] = i; for (int j = 0; j < cnt...
决策单调性优化dp
决策单调性优化dp学习笔记 决策单调性优化dp学习笔记 - birchtree - 博客园 (cnblogs.com)
普通对顶堆
动态维护第k大 1234567891011121314priority_queue<int> a; //大根堆priority_queue<int,vector<int>,greater<int> > b;for(int i=1; i<=n; i++){ int x; scanf("%d",&x); if(b.empty()||x>=b.top()) b.push(x); //插入 else a.push(x); int k=max(1,i*w/100); //第k大 while(b.size()>k) a.push(b.top()), b.pop(); //调整 while(b.size()<k) b.push(a.top()), a.pop(); printf("%d ", b.top()); //取值}
染色法判定二分图
20230723与y总代码模板不同，为自己独立实现，不够美观，但便于自己理解 debug过程： 需要注意到本题是无向图，所以add函数需要用两次，还有就是我们使用链式前向星结构去存图，所以ne和e数组需要开两倍的边数。 就是因为数组开小了，导致最后tle了，数组开小了什么报错都有可能出现 染色算法能够解决非连通图的二部图判定，所以从一个点dfs出发是不够的，要多源dfs 也就是说对每个连通块进行dfs,先对一个点dfs后，找此时没有被染色的点再dfs，直到全都被染色或者dfs过程中return false; 这个dfs过程不需要还原现场，因为我们需要保留所有点的颜色。 我的代码中dfs函数只有一个参数，yxc的代码是两个参数，都是可以的？！ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include...
Codeforces Round 918 (Div. 4)
#Codeforces Round 918 (Div. 4) D:本题从实现上来说正难则反，应该倒着做 在我正着做的时候，由于在访问后面元素的时候没有判边界，导致数组越界，出现奇怪字符在最后答案中。 1234567891011121314151617181920212223242526272829303132333435363738int n, m;int a[N];bool check(char c){ if(c=='a'||c=='e')return true; else return false;}void solve(){ cin>>n; string s;cin>>s; string ans; string tmp="."; for(int i=0;i<n;){ //cerr<<i<<"...
树链剖分——最近公共祖先（LCA）
N,M,S，分别表示树的结点个数、询问的个数和树根结点 理论时间复杂度上界就是O（2n+mlogn） 12345678910111213141516171819202122232425262728293031323334353637383940414243444546const int N=500010;int n,m,s,a,b;vector<int> e[N];int fa[N],son[N],dep[N],siz[N];int top[N];void dfs1(int u,int f){ //搞fa,dep,son fa[u]=f;siz[u]=1;dep[u]=dep[f]+1; for(int v:e[u]){ if(v==f) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[son[u]]<siz[v])son[u]=v; }}void dfs2(int u,int t){ //搞top top[u]=t; //记录链头...