爱飞鱼的blog

title: 分层图categories: - ICPCtags: - nullabbrlink: c08b9b99date: 2024-07-12 00:00:00[P4568 JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题意：

title: 基于凸函数categories: - ICPCtags: - nullabbrlink: 3225bee5date: 2024-07-11 00:00:00基于凸函数Slope Trick - Gensokyo Algorithm Research Institute D - 红黑树 - SUA Wiki dp 凸优化学习笔记 - 寂静的海底 - 博客园 DP 的凸优化 - LarsWerner - 博客园 【学习笔记】Max 卷积 & 闵可夫斯基和 - APJifengc - 博客园 【学习笔记】DP 优化 3：闵可夫斯基和优化 DP - SoyTony - 博客园 从带权二分到闵可夫斯基和与凸生成函数 - JueFan - 博客园 浅谈斜率优化 - OI | Tiagimの小窝 = 重樱的长门 斜率优化 - OI Wiki 【学习笔记】动态规划—斜率优化DP（超详细） - 辰星凌 - 博客园

title: 虚树categories: - ICPCtags: - nullabbrlink: c15ecfc4date: 2024-07-11 00:00:00虚树模板： struct edge { int v, w; }; struct HLD { int n; vector<int> siz, top, parent, l, r, hson, dep; vector<vector<edge>> adj; int idx; vector<int> mn;//1-u的最小边权 HLD() {} HLD(int n) { init(n); } void init(int n) { this->n = n; siz.resize(n + 1), hson.resize(n + 1), top.resize(n +...

title: 断更说明categories: - ICPCtags: - nullabbrlink: da02ab26date: 2024-07-10 00:00:00由于准备校赛，时间比较不够用，自己写的总结和题解，就没发，现在补一下。

title: 质因数分解categories: - ICPCtags: - nullabbrlink: e7d92776date: 2024-07-09 00:00:00acwing的最基础模板 https://www.acwing.com/blog/content/406/知乎大佬给的各种数据范围模板大全：https://zhuanlan.zhihu.com/p/591377294对于其中的一部分进行提炼形成自己的模板1.使用场景：假设有n个数需要分解，每个数最大可能是N,下面给出的这种代码的时间复杂度是$O(nlogN)$思想：通过$O(n)$线性筛预处理过程中记录范围内每个数的最小质因数，分解时每个数的最多被计算$O(logN)$次。 //预处理： 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...

title: 决策单调性优化dpcategories: - ICPCtags: - nullabbrlink: 67361f08date: 2024-07-07 00:00:00决策单调性优化dp学习笔记决策单调性优化dp学习笔记 - birchtree - 博客园 (cnblogs.com)

title: 普通对顶堆categories: - ICPCtags: - nullabbrlink: d860667ddate: 2024-06-27 00:00:00动态维护第k大 priority_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(); ...

title: 染色法判定二分图categories: - ICPCtags: - nullabbrlink: c6091b98date: 2024-06-25 00:00:0020230723与y总代码模板不同，为自己独立实现，不够美观，但便于自己理解debug过程： 需要注意到本题是无向图，所以add函数需要用两次，还有就是我们使用链式前向星结构去存图，所以ne和e数组需要开两倍的边数。 就是因为数组开小了，导致最后tle了，数组开小了什么报错都有可能出现 染色算法能够解决非连通图的二部图判定，所以从一个点dfs出发是不够的，要多源dfs也就是说对每个连通块进行dfs,先对一个点dfs后，找此时没有被染色的点再dfs，直到全都被染色或者dfs过程中return false; 这个dfs过程不需要还原现场，因为我们需要保留所有点的颜色。 我的代码中dfs函数只有一个参数，yxc的代码是两个参数，都是可以的？！ #include <bits/stdc++.h> using namespace std; //# define int long...

title: Codeforces Round 918 (Div. 4)categories: - ICPCtags: - nullabbrlink: c3916e9bdate: 2024-06-22 00:00:00#Codeforces Round 918 (Div. 4) D:本题从实现上来说正难则反，应该倒着做在我正着做的时候，由于在访问后面元素的时候没有判边界，导致数组越界，出现奇怪字符在最后答案中。 int 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<<"...

title: 树链剖分——最近公共祖先（LCA）categories: - ICPCtags: - nullabbrlink: 3a719bdate: 2024-06-12 00:00:00 N,M,S，分别表示树的结点个数、询问的个数和树根结点 理论时间复杂度上界就是O（2n+mlogn）const 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...