网络流 最大流 Dinic 算法
title: 网络流 最大流 Dinic 算法categories: - ICPCtags: - nullabbrlink: 58d50340date: 2024-01-14 00:00:00#define LL long long #define N 10010 #define M 200010 using namespace std; int n,m,S,T; //n,m,s,t，分别表示点的个数、有向边的个数、源点序号、汇点序号 struct edge{LL v,c,ne;}e[M]; int h[N],idx=1; //从2,3开始配对 int d[N],cur[N]; void add(int a,int b,int c){ e[++idx]={b,c,h[a]}; h[a]=idx; } bool bfs(){ //对点分层，找增广路 memset(d,0,sizeof d); queue<int>q; q.push(S); d[S]=1; ...
可撤销并查集
title: 可撤销并查集categories: - ICPCtags: - nullabbrlink: f3cf0596date: 2024-01-11 00:00:00可撤销并查集给定n个结点，q次询问，每次询问分为三类： 1 x y：可以选择将x,y两个点连通，如果已经连通则不操作。 2 ：撤销上一次的操作（若全部撤销完了则不操作）。 3 x y：询问x*,*y是否连通，如果是则输出”YES”，反之输出”NO”，请注意都是大写字母，不包含引号。 struct DSU { std::vector<int> siz; std::vector<int> f; std::vector<std::array<int, 2>> his; DSU(int n) : siz(n + 1, 1), f(n + 1) { std::iota(f.begin(), f.end(), 0); } int find(int x) { ...
容斥原理应用Acwing890借鉴题解
title: 容斥原理应用Acwing890借鉴题解categories: - ICPCtags: - nullabbrlink: 3c2dfe70date: 2024-01-11 00:00:00参考文献简单的容斥原理介绍请看下图： C++ 代码简单的容斥原理介绍请看下图： 本题思路：将题目所给出的m个数可以看成是m位的二进制数，例如当p[N]={2,3}时，此时会有01,10,11三种情况而二进制的第零位表示的是p[0]上面的数字2,第1位表示p[1]上面的数字3所以当i=1时表示只选择2的情况，当i=2（10）时,表示只选择3的情况,当i=3时,表示2和3相乘的情况在过程中可以用标记变量t记录,可以按照t的值来选择是”+”还是“-” 代码如下： #include #include using namespace std; typedef long long LL; const int N=20; int p[N]; int main() { int n,m; ...
树上路径问题—树形dp
title: 树上路径问题—树形dpcategories: - ICPCtags: - nullabbrlink: b48701c5date: 2024-01-05 00:00:00树上路径问题—树形dp[「REMAKE系列」树形dp篇 - Roshin - 博客园 (cnblogs.com)](https://www.cnblogs.com/Roshin/p/remake_tree_dp.html#:~:text=树上路径1 link) dls的树形dp - 牛佳文 - 博客园 (cnblogs.com) Codeforces 633 F The Chocolate Spree(树形dp，两条不相交链节点权值和最大)_树上求不相交的两条权值最大路径-CSDN博客 SPOJ Two Paths 树上不相交路径乘积最大值_树上最多路径 边不相交路径-CSDN博客 [P9047 [PA2021] Poborcy podatkowi - 洛谷 | 计算机科学教育新生态...
2024牛客寒假算法基础集训营6
title: 2024牛客寒假算法基础集训营6categories: - ICPCtags: - nullabbrlink: db08c90fdate: 2023-12-31 00:00:00I题：要求矩阵的最大子矩阵和，其中第i行第j列是ai*bj。经过代数变形问题等价求:a的连续子段和b的连续子段和.考虑到有负数存在，我们四个dp数组分别记录a的最小子段和a的最大子段,b同理。答案就是最值最值（4种可能） j题：给出一个有根树，1为根。给出节点颜色，要求红节点的子树点权和是3的倍数。每个点的点权为1或2，给出任意一种构造方案。解法：分析可知两种情况下无法构造 红叶子没有子节点，子树和无法到3. 红节点的儿子不存在白节点
最小表示法学习笔记
title: 最小表示法学习笔记categories: - ICPCtags: - nullabbrlink: 2d46b897date: 2023-12-27 00:00:00最小表示法有一个长度为 $n$的字符串 s，如果我们不断把它开头的字符移到结尾，可以得到 n个字符串，这些字符串是循环同构的，其中字典序最小的就是 s的最小表示。 string getmin(string s){ int len=s.size(); s+=s; s=" "+s; int i=1,j=2;//i,j表示以其位置开头的循环串 while(j<=len){ int k=0;//时间复杂度线性 while(k<len&&s[i+k]==s[j+k])k++; if(s[i+k]>s[j+k]){ i+=k+1; } else j+=k+1; if(i==j)j++; if(i>j)swap(i,j); } ...
CCPC2023秦皇岛
title: CCPC2023秦皇岛categories: - ICPCtags: - nullabbrlink: d7d0f40cdate: 2023-12-22 00:00:00CCPC2023秦皇岛C.题意：给定一个字符串，多次区间询问给定一个子串。问有多少种方案删掉最短的区间使得子串变成回文串Sol：考虑每次询问可以独立处理，当然并不是指把子串单独提出来，而是按顺序正常回答。 一个关键的点是，考虑如果第一个字符和最后一个字符不一样，那一定要删一个，依次推理下去，我们可以得到应该保留最长回文前缀或最长回文后缀。 再考虑如果第一个字符和最后一个字符一样，那我们类双指针缩小删除区间，直到两边不一样。此时又回归到第一种情况。 根据上面这个观察，我们得到获得最小删除代价的做法： 对于一个区间[l, r] 我们首先可以先让首尾相同字符不断相消, 最后剩余区间[x, y], 如果这个区间为空则为回文串。这一部分等价于求原串后缀l 和反串后缀n − r + 1 的最长公共前缀( LCP ), 再对区间长度取min。 如果不为回文串, 那么$str[x] =...
树上连通块计数
title: 树上连通块计数categories: - ICPCtags: - nullabbrlink: 254db057date: 2023-12-21 00:00:00树上连通块计数《解决树上连通块问题的一些技巧和工具》 学习笔记 - evenbao - 博客园 (cnblogs.com)
欧拉路
title: 欧拉路categories: - ICPCtags: - nullabbrlink: cad745fdate: 2023-12-10 00:00:00欧拉路构造题中的欧拉回路 | tyqtyq 的博客 2018的国家集训队论文《欧拉图相关的生成与计数问题探究》 [Tricks] 记各类欧拉回路问题 - 樱雪喵 - 博客园 欧拉路径是满足恰经过所有边一次的通路 欧拉回路是起点和终点相同的一条欧拉路径. 判别法则： 有向图存在欧拉回路: G中所有度数非0的点是强连通的，且所有点入度均等于出度. 有向图存在欧拉通路: 将边看成无向边后，G中所有度数非0的点是连通的。 最多只有一个点入度比出度大 1，作为欧拉通路的起点 最多只有一个点出度比入度大 1，作为欧拉通路的终点 其他所有点入度均等于出度 无向图存在欧拉回路: G中所有度数非0的点是连通的且所有点度数均为偶数. 无向图存在欧拉通路: G中所有度数非0的点是连通。并且G中恰好存在0或2个奇度点。 其他所有点度数均为偶数。那两个奇度点中, 一个作为欧拉通路之起点,...
Codeforces Round 944 (Div. 4)
title: Codeforces Round 944 (Div. 4)categories: - ICPCtags: - nullabbrlink: a8fa2257date: 2023-12-08 00:00:00Codeforces Round 944 (Div. 4) 需要一些trick的一场 H: 2 -sat的板子，已经计入2-sat专题，此处不再详细描述。题目用矩阵包装和博弈包装，我们需要慢慢读题，分析样例，找到问题的关键点。G：题意：给定一个数组，数组中任何两个数异或<4的数对可以交换位置...