爱飞鱼的blog

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#define LL long long#define N 10010#define M 200010using 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);...

可撤销并查集 给定n个结点，q次询问，每次询问分为三类： 1 x y：可以选择将x,y两个点连通，如果已经连通则不操作。 2 ：撤销上一次的操作（若全部撤销完了则不操作）。 3 x y：询问x*,*y是否连通，如果是则输出"YES"，反之输出"NO"，请注意都是大写字母，不包含引号。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768struct 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(),...

参考文献 简单的容斥原理介绍请看下图： 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的值来选择是”+”还是“-” 代码如下： 12345678910111213141516171819202122232425262728293031323334353637383940#include#includeusing namespace std;typedef long long LL;const int N=20;int p[N];int main(){ int n,m; cin>>n>>m; for(int i=0;i>p[i]; int res=0; ...

树上路径问题—树形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 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P9047#:~:text=给定一棵 nnn 个) 树上路径问题常见手法：树上动态规划（路径问题） - 算法小站...

I题：要求矩阵的最大子矩阵和，其中第i行第j列是ai*bj。 经过代数变形问题等价求:a的连续子段和b的连续子段和. 考虑到有负数存在，我们四个dp数组分别记录a的最小子段和a的最大子段,b同理。 答案就是最值最值（4种可能） j题：给出一个有根树，1为根。给出节点颜色，要求红节点的子树点权和是3的倍数。 每个点的点权为1或2，给出任意一种构造方案。 解法：分析可知两种情况下无法构造 红叶子没有子节点，子树和无法到3. 红节点的儿子不存在白节点

最小表示法 有一个长度为 nnn的字符串 s，如果我们不断把它开头的字符移到结尾，可以得到 n个字符串，这些字符串是循环同构的，其中字典序最小的就是 s的最小表示。 123456789101112131415161718string 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); } //最终字典序最小的是以i开头的 return s.substr(i,len);} P1368...

CCPC2023秦皇岛 C.题意：给定一个字符串，多次区间询问给定一个子串。问有多少种方案删掉最短的区间使得子串变成回文串 Sol：考虑每次询问可以独立处理，当然并不是指把子串单独提出来，而是按顺序正常回答。 一个关键的点是，考虑如果第一个字符和最后一个字符不一样，那一定要删一个，依次推理下去，我们可以得到应该保留最长回文前缀或最长回文后缀。 再考虑如果第一个字符和最后一个字符一样，那我们类双指针缩小删除区间，直到两边不一样。此时又回归到第一种情况。 根据上面这个观察，我们得到获得最小删除代价的做法： 对于一个区间[l, r] 我们首先可以先让首尾相同字符不断相 消, 最后剩余区间[x, y], 如果这个区间为空则为回文串。这一部分等价于求原串后缀l 和反串后缀n − r + 1 的最长公共前缀( LCP ), 再对区间长度取min。 如果不为回文串, 那么str[x]=str[y]str[x] = str[y]str[x]=str[y], x, y 其中之一会被删除。 删除最少长度, 等价于保留最多长度, 即保留x 开头的一个 回文串或y...

树上连通块计数 《解决树上连通块问题的一些技巧和工具》 学习笔记 - evenbao - 博客园 (cnblogs.com)

欧拉路 构造题中的欧拉回路 | tyqtyq 的博客 2018的国家集训队论文《欧拉图相关的生成与计数问题探究》 [Tricks] 记各类欧拉回路问题 - 樱雪喵 - 博客园 欧拉路径是满足恰经过所有边一次的通路 欧拉回路是起点和终点相同的一条欧拉路径. 判别法则： 有向图存在欧拉回路: G中所有度数非0的点是强连通的，且所有点入度均等于出度. 有向图存在欧拉通路: 将边看成无向边后，G中所有度数非0的点是连通的。 最多只有一个点入度比出度大 1，作为欧拉通路的起点 最多只有一个点出度比入度大 1，作为欧拉通路的终点 其他所有点入度均等于出度 无向图存在欧拉回路: G中所有度数非0的点是连通的且所有点度数均为偶数. 无向图存在欧拉通路: G中所有度数非0的点是连通。并且G中恰好存在0或2个奇度点。 其他所有点度数均为偶数。那两个奇度点中, 一个作为欧拉通路之起点, 另一个作为终点. 算法流程：感性理解：先找一条起点到终点的通路，然后不断回溯找环。 先用充要条件也就是度数和连通性去判断是不是存在欧拉路...

Codeforces Round 944 (Div. 4) 需要一些trick的一场 H: 2 -sat的板子，已经计入2-sat专题，此处不再详细描述。题目用矩阵包装和博弈包装，我们需要慢慢读题，分析样例，找到问题的关键点。 G：题意：给定一个数组，数组中任何两个数异或<4的数对可以交换位置 ，可以交换无限次，求能够形成的字典序最小的数组。 Sol：我们希望能够快速将能够交换的数对都聚集在一起，然后内部排个序，再按顺序送回每个位置上，时间复杂度O(nlogn)O(nlogn)O(nlogn)。所以我们只需要思考两个数怎么样才能异或起来<4，那么显然应该二进制位下分析，我们发现只需要高29位一样，剩的低三位随便怎么样我们不在乎，也就是说这样的数共有的特征是x>>2都是一样的，所以我们直接map<int,vector>存一下每个数，再对于每个vector排序.又由于不想存下标，所以我们只能倒着做回去利用vector的pop_back功能 12345678910111213141516171819void solve(){ ...