树的重心
title: 树的重心 categories: ICPC tags: null abbrlink: a5c898a date: 2023-03-13 00:00:00 const 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: ICPC tags: null abbrlink: 60cbacb1 date: 2023-03-13 00:00:00 AcWing 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: ICPC tags: null abbrlink: 572bc114 date: 2023-03-12 00:00:00 无向图无环的，无环的图总是可以展成树的形式。 然后考虑无向图，顶多有回边指向父节点。不可能有回边指向祖先。更不可能有横向边，因为无环啊。所以只需要考虑指向父节点的回边就可以无需使用Vis。
AC自动机
title: AC自动机 categories: ICPC tags: null abbrlink: 5c28c80e date: 2023-03-10 00:00:00 AC自动机 AC 自动机= Trie + KMP AC 自动机基于Trie，将KMP 的Border 概念推广到多模式串上。 AC 自动机是一种离线型数据结构，即不支持增量添加新的字符串。 AC 自动机常用于将字符串询问类的问题进行离线处理，也经常与各种 DP 结合，或是补全成Trie 图。 广义border 1.推广到两个串：对于两个串S 和T，相等的p 长度的S 的后缀和T 的前缀称为一个border。 2.推广到一个字典：对于串S 和一个字典D，相等的p 长度的S 的后缀，和任意一个字典串T 的前缀称为一个border。 3.失配（Fail）指针： 对于Trie 中的每一个节点（即某个字典串的前缀），它与Trie 中所有串的最大Border 即为失配指针 ac自动机维护的是当前状态的最大后缀满足这个后缀是字典树的前缀 struct AC { static...
max-element的min-element的基本用法
title: max-element的min-element的基本用法 categories: ICPC tags: null abbrlink: 55b56468 date: 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: ICPC tags: null abbrlink: fa56ba17 date: 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: ICPC tags: null abbrlink: 9c5a2d2d date: 2023-03-05 00:00:00 1和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: ICPC tags: null abbrlink: 973bc934 date: 2023-03-05 00:00:00 染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图 时间复杂度是 O(n+m)O(n+m)O(n+m), nnn 表示点数，mmm 表示边数 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...
和为k的连续子序列 存在吗
title: 和为k的连续子序列 存在吗 categories: ICPC tags: null abbrlink: c25c7836 date: 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: ICPC tags: null abbrlink: b4c59b70 date: 2023-03-04 00:00:00 曼哈顿距离与切比雪夫距离 距离 - OI Wiki (oi-wiki.org)已经说的比较清晰，提取要点和结论便于复习使用。 曼哈顿距离：d(A,B)=∣x1−x2∣+∣y1−y2∣d \left(\right. A , B \left.\right) = \left|\right. x_{1} - x_{2} \left|\right. + \left|\right. y_{1} - y_{2} \left|\right.d(A,B)=∣x1−x2∣+∣y1−y2∣ 切比雪夫距离：d(A,B)=max(∣x1−x2∣,∣y1−y2∣)d \left(\right. A , B \left.\right) = max \left(\right. \left|\right. x_{1} - x_{2} \left|\right. , \left|\right. y_{1} -...