爱飞鱼的blog

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

title: 基于凸函数 categories: ICPC tags: null abbrlink: 3225bee5 date: 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: ICPC tags: null abbrlink: c15ecfc4 date: 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),...

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

title: 质因数分解 categories: ICPC tags: null abbrlink: e7d92776 date: 2024-07-09 00:00:00 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)次。 //预处理： for (int i = 2; i < N; i++)minp[i] = i;//通过这个初始化省下bool数组空间 int cnt = 0; for (int i = 2; i < N; i++) { if...

title: 决策单调性优化dp categories: ICPC tags: null abbrlink: 67361f08 date: 2024-07-07 00:00:00 决策单调性优化dp学习笔记 决策单调性优化dp学习笔记 - birchtree - 博客园 (cnblogs.com)

title: 普通对顶堆 categories: ICPC tags: null abbrlink: d860667d date: 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()),...

title: 染色法判定二分图 categories: ICPC tags: null abbrlink: c6091b98 date: 2024-06-25 00:00:00 20230723与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: ICPC tags: null abbrlink: c3916e9b date: 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: ICPC tags: null abbrlink: 3a719b date: 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...