树的重心
title: 树的重心categories: - ICPCtags: - nullabbrlink: a5c898adate: 2023-03-13 00:00:00const int N=100010; int n, a, b; vector<int> e[N];//用vector作邻接表 int siz[N], pos, ans=1e9; void dfs(int x, int fa){ siz[x]=1; int mx=0; for(auto y : e[x]){ if(y == fa) continue; dfs(y, x);//先搜完，再统计答案 siz[x] += siz[y]; mx=max(mx, siz[y]); } mx=max(mx, n-siz[x]); //维护了重心是pos if(mx<ans) ans=mx,pos=x; } int main(){ scanf("%d", &n); ...
维护除了自己外的最大值
title: 维护除了自己外的最大值categories: - ICPCtags: - nullabbrlink: 60cbacb1date: 2023-03-13 00:00:00AcWing 5132. 奶牛照相对于求除了当前点外其他点的最大值， 1.笨拙的方法是维护最大值和次大值以及他们所对应的坐标，用pair可以实现。 2.巧妙的办法是用前缀数组和后缀数组预处理 1的实现 #include <bits/stdc++.h> using namespace std; # define int long long typedef long long ll; typedef unsigned long long ull; typedef pair<int,int>pii; const int N = 2e5 + 10; const int M = 2e5 + 10; const int inf = 0x3f3f3f3f; const int mod = 998244353; int n, m; int ans[N]; int...
为什么树的dfs不需要vis数组，只需要维护父节点就可以？
title: 为什么树的dfs不需要vis数组，只需要维护父节点就可以？categories: - ICPCtags: - nullabbrlink: 572bc114date: 2023-03-12 00:00:00无向图无环的，无环的图总是可以展成树的形式。然后考虑无向图，顶多有回边指向父节点。不可能有回边指向祖先。更不可能有横向边，因为无环啊。所以只需要考虑指向父节点的回边就可以无需使用Vis。
AC自动机
title: AC自动机categories: - ICPCtags: - nullabbrlink: 5c28c80edate: 2023-03-10 00:00:00AC自动机 AC 自动机= Trie + KMP AC 自动机基于Trie，将KMP 的Border 概念推广到多模式串上。 AC 自动机是一种离线型数据结构，即不支持增量添加新的字符串。 AC 自动机常用于将字符串询问类的问题进行离线处理，也经常与各种DP 结合，或是补全成Trie 图。 广义border1.推广到两个串：对于两个串S 和T，相等的p 长度的S 的后缀和T 的前缀称为一个border。2.推广到一个字典：对于串S 和一个字典D，相等的p 长度的S 的后缀，和任意一个字典串T 的前缀称为一个border。3.失配（Fail）指针： 对于Trie 中的每一个节点（即某个字典串的前缀），它与Trie 中所有串的最大Border 即为失配指针ac自动机维护的是当前状态的最大后缀满足这个后缀是字典树的前缀 struct AC { static constexpr...
max-element的min-element的基本用法
title: max-element的min-element的基本用法categories: - ICPCtags: - nullabbrlink: 55b56468date: 2023-03-07 00:00:00转载自https://blog.csdn.net/qq_37978559/article/details/109782755?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169173063816800197041324%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169173063816800197041324&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2
线性基
title: 线性基categories: - ICPCtags: - nullabbrlink: fa56ba17date: 2023-03-07 00:00:00线性基解决异或问题除了字典树，剩下很常用的就是线性基。理解线性基的作用就是极大线性无关向量组，只不过在线代中我们一般讨论的是线性加减运算，而在竞赛中往往是异或运算。 对于一个向量能不能在当前的基中表示，也就是它能不能被基的某个子集异或出来，那我们如何简单高效的判断呢。首先最暴力的是直接按位拆开，高斯消元，对于每一列，也就是每一位只保留1行有1.设原集合为S,线性基为B。线性基的性质： B是极小的满足线性基性质的集合，它的任何真子集都不可能是线性基；B是线性无关的 S中的任意元素都可以唯一表示为 中若干个元素异或起来的结果。 直接给出最优算法：设集合 S中最大的数在二进制意义下有 L位，我们使用一个 大小为Ld的a数组 来储存线性基。 首先，线性基是动态构造的，我们只需要从空的a 开始，每次考虑在一个已存在的线性基中插入一个数t 即可。 从 t最高位上的 1开始考虑，设这是第...
trick——1和2可达性系列
title: trick——1和2可达性系列categories: - ICPCtags: - nullabbrlink: 9c5a2d2ddate: 2023-03-05 00:00:001和2可达性系列https://codeforces.com/gym/104768/problem/H https://codeforces.com/contest/1896/problem/D 题源：https://www.luogu.com.cn/problem/P3514 带修改加强： https://www.luogu.com.cn/problem/P6859
二分图
title: 二分图categories: - ICPCtags: - nullabbrlink: 973bc934date: 2023-03-05 00:00:00 染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图时间复杂度是 $O(n+m)$, $n$ 表示点数，$m$ 表示边数bool dfs(int u,int c){//判断存在奇环，存在返回true color[u]=c; for(auto v:e[u]){ if(!color[v]){ if(dfs(v,3-c))return 1; } else if(color[v]==c)return 1;//有奇环 } return 0; } bool check() {//判断是不是二分图 fill(color,color+1+n,0); bool flag = true; for (int i = 1; i <= n; i ++...
和为k的连续子序列 存在吗
title: 和为k的连续子序列 存在吗categories: - ICPCtags: - nullabbrlink: c25c7836date: 2023-03-05 00:00:00题意是这样的，给你一个串，只有 T 和 W。令 T=2，W=1，将其变成数字串。然后每次给一个k,问是否存在一个子段和为k一筐题目：https://www.acwing.com/problem/content/description/4040/ 基础版本，只需要存在性并输出任意一组合法解https://www.luogu.com.cn/problem/P3514 英文版基础版本，只需要存在性并输出任意一组合法解https://codeforces.com/contest/1896/problem/D 带修改版本但不用输出具体是哪段https://www.luogu.com.cn/problem/P6859 带修改版本并且需要输出左端点最小的解https://qoj.ac/contest/1404/problem/7684?v=1 ...
曼哈顿距离与切比雪夫距离
title: 曼哈顿距离与切比雪夫距离categories: - ICPCtags: - nullabbrlink: b4c59b70date: 2023-03-04 00:00:00曼哈顿距离与切比雪夫距离距离 - OI Wiki (oi-wiki.org)已经说的比较清晰，提取要点和结论便于复习使用。 曼哈顿距离：$d \left(\right. A , B \left.\right) = \left|\right. x_{1} - x_{2} \left|\right. + \left|\right. y_{1} - y_{2} \left|\right.$ 切比雪夫距离：$d \left(\right. A , B \left.\right) = max \left(\right. \left|\right. x_{1} - x_{2} \left|\right. , \left|\right. y_{1} - y_{2} \left|\right....