网络流 最大流 Dinic 算法
title: 网络流 最大流 Dinic 算法 categories: ICPC tags: null abbrlink: 58d50340 date: 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: ICPC tags: null abbrlink: f3cf0596 date: 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...
容斥原理应用Acwing890借鉴题解
title: 容斥原理应用Acwing890借鉴题解 categories: ICPC tags: null abbrlink: 3c2dfe70 date: 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; cin>>n>>m; ...
树上路径问题—树形dp
title: 树上路径问题—树形dp categories: ICPC tags: null abbrlink: b48701c5 date: 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牛客寒假算法基础集训营6 categories: ICPC tags: null abbrlink: db08c90f date: 2023-12-31 00:00:00 I题：要求矩阵的最大子矩阵和，其中第i行第j列是ai*bj。 经过代数变形问题等价求:a的连续子段和b的连续子段和. 考虑到有负数存在，我们四个dp数组分别记录a的最小子段和a的最大子段,b同理。 答案就是最值最值（4种可能） j题：给出一个有根树，1为根。给出节点颜色，要求红节点的子树点权和是3的倍数。 每个点的点权为1或2，给出任意一种构造方案。 解法：分析可知两种情况下无法构造 红叶子没有子节点，子树和无法到3. 红节点的儿子不存在白节点
最小表示法学习笔记
title: 最小表示法学习笔记 categories: ICPC tags: null abbrlink: 2d46b897 date: 2023-12-27 00:00:00 最小表示法 有一个长度为 nnn的字符串 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: ICPC tags: null abbrlink: d7d0f40c date: 2023-12-22 00:00:00 CCPC2023秦皇岛 C.题意：给定一个字符串，多次区间询问给定一个子串。问有多少种方案删掉最短的区间使得子串变成回文串 Sol：考虑每次询问可以独立处理，当然并不是指把子串单独提出来，而是按顺序正常回答。 一个关键的点是，考虑如果第一个字符和最后一个字符不一样，那一定要删一个，依次推理下去，我们可以得到应该保留最长回文前缀或最长回文后缀。 再考虑如果第一个字符和最后一个字符一样，那我们类双指针缩小删除区间，直到两边不一样。此时又回归到第一种情况。 根据上面这个观察，我们得到获得最小删除代价的做法： 对于一个区间[l, r] 我们首先可以先让首尾相同字符不断相 消, 最后剩余区间[x, y], 如果这个区间为空则为回文串。这一部分等价于求原串后缀l 和反串后缀n − r + 1 的最长公共前缀( LCP ), 再对区间长度取min。 如果不为回文串,...
树上连通块计数
title: 树上连通块计数 categories: ICPC tags: null abbrlink: 254db057 date: 2023-12-21 00:00:00 树上连通块计数 《解决树上连通块问题的一些技巧和工具》 学习笔记 - evenbao - 博客园 (cnblogs.com)
欧拉路
title: 欧拉路 categories: ICPC tags: null abbrlink: cad745f date: 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: ICPC tags: null abbrlink: a8fa2257 date: 2023-12-08 00:00:00 Codeforces Round 944 (Div. 4) 需要一些trick的一场 H: 2 -sat的板子，已经计入2-sat专题，此处不再详细描述。题目用矩阵包装和博弈包装，我们需要慢慢读题，分析样例，找到问题的关键点。 G：题意：给定一个数组，数组中任何两个数异或<4的数对可以交换位置 ，可以交换无限次，求能够形成的字典序最小的数组。 ...