最短路
title: 最短路 categories: ICPC tags: null abbrlink: f216fabe date: 2023-06-03 00:00:00 单源最短路： 求一个点到其他点的最短路 多源最短路： 求任意两个点的最短路 稠密图用邻接矩阵存，稀疏图用邻接表存储。 稠密图： m 和 n2 一个级别 稀疏图： m 和 n 一个级别 朴素dij： int 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++)//枚举点 ...
马拉车学习笔记
title: 马拉车学习笔记 categories: ICPC tags: null abbrlink: 2e68fff1 date: 2023-05-29 00:00:00 马拉车学习笔记 概念与定义： 回文串：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：对于回文串...
最基础树状数组
title: 最基础树状数组 categories: ICPC tags: null abbrlink: 7d5ff616 date: 2023-05-28 00:00:00 1.单点加 2.前缀和查询 int 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...
Trie三战含板子
title: Trie三战含板子 categories: ICPC tags: null abbrlink: 756ed5 date: 2023-05-25 00:00:00 Trie三战含板子 字典：一个字符串的集合称为字典。 字典串：在字典里的串称为字典串。 在处理字符串的时候，常会遇到这样的简单问题：给出一个字典，然后回答大量询问：输入一个字符串，判断它是否在字典中。 Trie 是一棵有根树，每个点至多有 |Σ| 个后继边，每条边上有一个字符。 每个点表示一个前缀：从跟到这个点的边上的字符顺次连接形成的字符串。 每个点还有一个终止标记：是否这个点代表的字符串是一个字典串。可以支持向 Trie 插入新字典串，删除字典串，查询某字符串是否是字典串，以及一些稍微复杂的查询。作为一个数据结构，它理所应当的还可以进行持久化。 这是一份处理小写字母字符串 int id(char c) {//给出现的字符集编码，记得改offset部分 if (c >= 'a' && c <= 'z') ...
关于浮点数误差以及四舍五入
title: 关于浮点数误差以及四舍五入 categories: ICPC tags: null abbrlink: 5b7b9db4 date: 2023-05-23 00:00:00 https://blog.csdn.net/Xavier_97/article/details/126931927 由于很玄学，我们考虑统一使用库函数round和自己手写round来实现最终输出整数的四舍五入和小数保留k位的四舍五入 #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) <<...
动态开点并查集+树上差分
title: 动态开点并查集+树上差分 categories: ICPC tags: null abbrlink: 64f2ca34 date: 2023-05-23 00:00:00 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...
需要整理的模板
title: 需要整理的模板 categories: ICPC tags: null abbrlink: ade3461 date: 2023-05-23 00:00:00 需要整理的模板 1.scc 2.edcc,vdcc 3.静态区间颜色数，区间mex。单点修改，区间修改 4.网络流？ 5.斜率优化，李超 ddp，括号序列（合法计数，k_th） 差分约束 多项式 .log_trick 平衡树板子->api Link-Cut Tree
acwing148周赛
title: acwing148周赛 categories: ICPC tags: null abbrlink: 47a0ff1d date: 2023-05-19 00:00:00 赛时困得睡着了 B题 https://www.acwing.com/problem/content/5562/ 第二题赛事一直在想模拟加贪心，却发现非常难实现，我们需要转变思维，这时候一般有3种可能 双指针？二分？dp？ 后来清醒了一点我们判断一个答案是不是合法很容易，我们再考虑答案求最大值，显然具有单调性，所以我们考虑二分答案，前缀和u优化判断 // Problem: 摆放棋子 // Contest: AcWing // URL: https://www.acwing.com/problem/content/5562/ // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include...
枚举子集+预处理优化dp+贪心视角转化成可做dp
title: 枚举子集+预处理优化dp+贪心视角转化成可做dp categories: ICPC tags: null abbrlink: bf104000 date: 2023-05-17 00:00:00 https://www.acwing.com/problem/content/531/ #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] =...
染色法判定二分图(1)
title: 染色法判定二分图(1) categories: ICPC tags: null abbrlink: 6e1acb24 date: 2023-05-17 00:00:00 什么叫二分图 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接！ 说人话的定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。 下图就是个二分图： 下图不是个二分图： 如果判断一个图是不是二分图？ 开始对任意一未染色的顶点染色。 判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。 bfs和dfs可以搞定！ 20230723与y总代码模板不同，为自己独立实现，不够美观，但便于自己理解 debug过程： 需要注意到本题是无向图，所以add函数需要用两次，还有就是我们使用链式前向星结构去存图，所以ne和e数组需要开两倍的边数。 ...