最短路
title: 最短路categories: - ICPCtags: - nullabbrlink: f216fabedate: 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++)//枚举点 if(!vis[j]&&d[j]<d[u])...
马拉车学习笔记
title: 马拉车学习笔记categories: - ICPCtags: - nullabbrlink: 2e68fff1date: 2023-05-29 00:00:00马拉车学习笔记概念与定义：回文串：S=R(S) 回文中心： 奇长度：回文中心为$S[\frac{n+1}{2}]$,如$abcba$ 偶长度：回文中心在$S[\frac{n}{2}]与S[\frac{n}{2}+1]$之间,如$ abc|cba$。 回文半径L：回文中心到回文串左右端点的距离，常用二元组$< 回文中心，回文半径>$来表示一个回文子串. 回文长度和回文半径的关系： 奇长度回文串：$|S|=2L-1$ 偶长度回文串：$|S|=2L$ 回文半径的二分性：回文半径-1 等价于同时删掉回文串的首尾字母，依然是回文串。回文串和 Border：对于回文串 S，回文前（后）缀等价于Border。因此得到结论：回文串的回文前后缀都是border（!!!)算法预处理：为了将偶回文串的处理方式与奇回文串统一起来，将 S 的每两个字母中间，以及开头结尾插入...
最基础树状数组
title: 最基础树状数组categories: - ICPCtags: - nullabbrlink: 7d5ff616date: 2023-05-28 00:00:001.单点加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: - ICPCtags: - nullabbrlink: 756ed5date: 2023-05-25 00:00:00Trie三战含板子字典：一个字符串的集合称为字典。 字典串：在字典里的串称为字典串。 在处理字符串的时候，常会遇到这样的简单问题：给出一个字典，然后回答大量询问：输入一个字符串，判断它是否在字典中。 Trie 是一棵有根树，每个点至多有 |Σ| 个后继边，每条边上有一个字符。 每个点表示一个前缀：从跟到这个点的边上的字符顺次连接形成的字符串。 每个点还有一个终止标记：是否这个点代表的字符串是一个字典串。可以支持向 Trie 插入新字典串，删除字典串，查询某字符串是否是字典串，以及一些稍微复杂的查询。作为一个数据结构，它理所应当的还可以进行持久化。 这是一份处理小写字母字符串 int id(char c) {//给出现的字符集编码，记得改offset部分 if (c >= 'a' && c <= 'z') ...
关于浮点数误差以及四舍五入
title: 关于浮点数误差以及四舍五入categories: - ICPCtags: - nullabbrlink: 5b7b9db4date: 2023-05-23 00:00:00https://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: - ICPCtags: - nullabbrlink: 64f2ca34date: 2023-05-23 00:00:00https://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: - ICPCtags: - nullabbrlink: ade3461date: 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: - ICPCtags: - nullabbrlink: 47a0ff1ddate: 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 <bits/stdc++.h> using...
枚举子集+预处理优化dp+贪心视角转化成可做dp
title: 枚举子集+预处理优化dp+贪心视角转化成可做dpcategories: - ICPCtags: - nullabbrlink: bf104000date: 2023-05-17 00:00:00https://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: - ICPCtags: - nullabbrlink: 6e1acb24date: 2023-05-17...