爱飞鱼的blog

单源最短路： 求一个点到其他点的最短路 多源最短路： 求任意两个点的最短路 稠密图用邻接矩阵存，稀疏图用邻接表存储。 稠密图： m 和 n2 一个级别 稀疏图： m 和 n 一个级别 朴素dij： 123456789101112131415161718192021222324252627282930313233int n,m,s,a,b,c;const int N=100010;struct edge{int v,w;};vector<edge> e[N];int d[N], vis[N];void dijkstra(int s){ for(int i=0;i<=n;i++)d[i]=inf; d[s]=0; for(int i=1;i<n;i++){//枚举次数 int u=0; for(int j=1;j<=n;j++)//枚举点 if(!vis[j]&&d[j]<d[u]) u=j; vis[u]=1; //标记u已出圈 ...

马拉车学习笔记 概念与定义： 回文串：S=R(S) 回文中心： 奇长度：回文中心为S[n+12]S[\frac{n+1}{2}]S[2n+1​],如abcbaabcbaabcba 偶长度：回文中心在S[n2]与S[n2+1]S[\frac{n}{2}]与S[\frac{n}{2}+1]S[2n​]与S[2n​+1]之间,如$ abc|cba$。 回文半径L：回文中心到回文串左右端点的距离，常用二元组<回文中心，回文半径>< 回文中心，回文半径><回文中心，回文半径>来表示一个回文子串. 回文长度和回文半径的关系： 奇长度回文串：∣S∣=2L−1|S|=2L-1∣S∣=2L−1 偶长度回文串：∣S∣=2L|S|=2L∣S∣=2L 回文半径的二分性：回文半径-1 等价于同时删掉回文串的首尾字母，依然是回文串。 回文串和 Border：对于回文串 S，回文前（后）缀等价于Border。因此得到结论：回文串的回文前后缀都是border（!!!) 算法预处理：为了将偶回文串的处理方式与奇回文串统一起来，将 S...

1.单点加 2.前缀和查询 1234567891011121314151617181920212223242526272829303132int n, m;int a[N];int tr[N];int lowbit(int x){ return x&(-x);}void add(int pos,int k){ for(int i=pos;i<=n;i+=lowbit(i))tr[i]+=k;}int query(int x){ int res=0; for(int i=x;i;i-=lowbit(i))res+=tr[i]; return res;}void solve(){ cin>>n;cin>>m; for(int i=1;i<=n;i++){ int x;cin>>x; add(i,x); } while(m--){ int op;cin>>op; if(op==1){ int...

Trie三战含板子 字典：一个字符串的集合称为字典。 字典串：在字典里的串称为字典串。 在处理字符串的时候，常会遇到这样的简单问题：给出一个字典，然后回答大量询问：输入一个字符串，判断它是否在字典中。 Trie 是一棵有根树，每个点至多有 |Σ| 个后继边，每条边上有一个字符。 每个点表示一个前缀：从跟到这个点的边上的字符顺次连接形成的字符串。 每个点还有一个终止标记：是否这个点代表的字符串是一个字典串。可以支持向 Trie 插入新字典串，删除字典串，查询某字符串是否是字典串，以及一些稍微复杂的查询。作为一个数据结构，它理所应当的还可以进行持久化。 这是一份处理小写字母字符串 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051int id(char c) {//给出现的字符集编码，记得改offset部分 if (c >= 'a' && c <=...

https://blog.csdn.net/Xavier_97/article/details/126931927 由于很玄学，我们考虑统一使用库函数round和自己手写round来实现最终输出整数的四舍五入和小数保留k位的四舍五入 1234567891011121314151617#include <iostream>#include <cmath> using namespace std; int main(){ double a = 1.4999999; double b = 1.5000001; double n_a = -1.4999999; double n_b = -1.5000001; cout << round(a) << endl; // 1 cout << round(b) << endl; // 2 cout << round(n_a) << endl; // -1 cout <<...

https://www.acwing.com/problem/content/description/2071/ 每次合并的时候需要开一个新点去实现信息的无后效性，也就是合并之前的两个连通块信息是无法共享的，发现这样开点连边最后 形成一棵树，每次我们将信息传递到新点，也是两个合并点的lca，这使得最后求答案的直接求一边树上前缀和，不同子树不受影响 debug：最后合并n-1次，初始化和空间都要开两倍 // Problem: 网络分析 // Contest: AcWing // URL: https://www.acwing.com/problem/content/2071/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define ll long long //# define int long long #define...

需要整理的模板 1.scc 2.edcc,vdcc 3.静态区间颜色数，区间mex。单点修改，区间修改 4.网络流？ 5.斜率优化，李超 ddp，括号序列（合法计数，k_th） 差分约束 多项式 .log_trick 平衡树板子->api Link-Cut Tree

赛时困得睡着了 B题 https://www.acwing.com/problem/content/5562/ 第二题赛事一直在想模拟加贪心，却发现非常难实现，我们需要转变思维，这时候一般有3种可能 双指针？二分？dp？ 后来清醒了一点我们判断一个答案是不是合法很容易，我们再考虑答案求最大值，显然具有单调性，所以我们考虑二分答案，前缀和u优化判断 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374// Problem: 摆放棋子// Contest: AcWing// URL: https://www.acwing.com/problem/content/5562/// Memory Limit: 256 MB// Time Limit: 1000 ms// // Powered by CP Editor...

https://www.acwing.com/problem/content/531/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 12, M = 1 << N, INF = 0x3f3f3f3f;int n, m;int d[N][N], g[N][M];int f[M][N];int main(){ scanf("%d%d", &n, &m); memset(d, 0x3f, sizeof d); for (int i = 0; i < n; i ++ ) d[i][i] = 0; while (m...

什么叫二分图 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接！ 说人话的定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。 下图就是个二分图： 下图不是个二分图： 如果判断一个图是不是二分图？ 开始对任意一未染色的顶点染色。 判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。 bfs和dfs可以搞定！ 20230723与y总代码模板不同，为自己独立实现，不够美观，但便于自己理解 debug过程： 需要注意到本题是无向图，所以add函数需要用两次，还有就是我们使用链式前向星结构去存图，所以ne和e数组需要开两倍的边数。 ...