克鲁斯卡尔重构树
title: 克鲁斯卡尔重构树 categories: ICPC tags: null abbrlink: 1877ddc4 date: 2023-09-02 00:00:00 一类以并查集在建树过程中维护各种信息的值——克鲁斯卡尔重构树前身 第一次见到是在zzu的校赛中，印象深刻。 H. Sum of Maximum Weights 题意 给定一棵树，求树上任意两点间最短路径中的最大边权的和。 官方 Solution 将边按权值排序，每次处理当前的最大权值。 处理每条边时，由于树的性质，边的起点和终点一定连通。设两个组 UUU 和 VVV，则 UUU 组中任意成员到 VVV 组中任意成员的最大路径边权必为当前边的权值 eee，故可以写出 ans+=siz[u]×siz[v]×eans += siz[u] \times siz[v] \times eans+=siz[u]×siz[v]×e。 将两组合并，重复上述过程，最终得到答案。 我的理解 如果了解克鲁斯卡尔重构树，这就是一道板子题。 #include...
单调栈
title: 单调栈 categories: ICPC tags: null abbrlink: 16518a5d date: 2023-08-27 00:00:00 从单调栈到笛卡尔树 功能1：单调栈可以在线性时间内为每个数找到序列中下一个比它的大的数，以及上一个比它大的数 https://vjudge.net/problem/POJ-2796单调栈基本功能代表作 poj的c++98首先对size函数不是O（1）的，然后还卡关了同步流的cin，关键数据范围才1e5,逆天毒瘤，耽误我40min，以后poj的题目先测试一下是不是卡常数。然后我不熟悉printf的输出longlong，应该用%lld 题意：给定一个数组，找到一个区间，使得 最大化 区间里的数的和×\times×区间最小值 Sol：直接单调栈维护每个数作为最小值能到的左右边界，然后O（n)枚举更新答案即可，前缀和优化一下。 int a[N]; ll s[N]; stack<int>pre; stack<int>nxt; //找到两侧第一个比它小的下标 int...
SOSdp
title: SOSdp categories: ICPC tags: null abbrlink: 4588451b date: 2023-08-24 00:00:00 从子集和问题到and卷积 枚举子集：O(3n)O(3^{n})O(3n) int u=15; for (int s = u; s; s = (s - 1) & u) { b=s ; cout<<b<<endl; } /* 1111 1110 1101 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001 */ 子集和问题参考好的博客https://ottffyzy.github.io/algos/dp/sosdp/ 其实这类算法更多的是解决子集和 （sum of subset） 问题，因此也叫 SOS DP。 也就是对于i从1-n我们希望求出sum[i]=∑j⊆ia[j]sum[i] = \sum_{j \subseteq i}...
判负环——spfa
title: 判负环——spfa categories: ICPC tags: null abbrlink: aad58836 date: 2023-08-22 00:00:00 #单测试点有多组测试数据，注意fill手动清空 int e[M],ne[M],w[M],h[N],idx; int d[N],cnt[N],vis[N]; //为了卡常用spfa的时候就用链式前向星 void init(){ fill(h,h+n+1,-1);idx=0; } void add(int a,int b,int c){//调用之前h要全部变成-1 e[idx]=b;w[idx]=c; ne[idx]=h[a];h[a]=idx++; } bool spfa(){ //判负环，存在返回true fill(d,d+n+1,inf); fill(vis,vis+n+1,0); fill(cnt,cnt+n+1,0); queue<int>q; for(int...
一类哈密顿路径_回路为背景的状压dp
title: 一类哈密顿路径_回路为背景的状压dp categories: ICPC tags: null abbrlink: 1033a034 date: 2023-08-21 00:00:00 https://codeforces.com/contest/1950/problem/G 在非连通图上找到一条包含点最多的路径，dp数组维护可达性 // Problem: G. Shuffling Songs // Contest: Codeforces - Codeforces Round 937 (Div. 4) // URL: https://codeforces.com/contest/1950/problem/G // Memory Limit: 256 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define ll long long //#...
常用数学库函数
title: 常用数学库函数 categories: ICPC tags: null abbrlink: f6229479 date: 2023-08-20...
KMP
title: KMP categories: ICPC tags: null abbrlink: ad32db8f date: 2023-08-19 00:00:00 题目描述 给出两个字符串 s1s_1s1 和 s2s_2s2，若 s1s_1s1 的区间 [l,r][l, r][l,r] 子串与 s2s_2s2 完全相同，则称 s2s_2s2 在 s1s_1s1 中出现了，其出现位置为 lll。 现在请你求出 s2s_2s2 在 s1s_1s1 中所有出现的位置。 定义一个字符串 sss 的 border 为 sss 的一个非 sss 本身的子串 ttt，满足 ttt 既是 sss 的前缀，又是 sss 的后缀。 对于 s2s_2s2，你还需要求出对于其每个前缀 s′s's′ 的最长 border t′t't′ 的长度。 输入格式 第一行为一个字符串，即为 s1s_1s1。 第二行为一个字符串，即为 s2s_2s2。 输出格式 首先输出若干行，每行一个整数，按从小到大的顺序输出 s2s_2s2 在 s1s_1s1...
行列式与矩阵树定理
title: 行列式与矩阵树定理 categories: ICPC tags: null abbrlink: b76954ab date: 2023-08-12 00:00:00 行列式与矩阵树定理 行列式取模板子：对于模数非质数采用辗转相除 消元操作是$ Θ(n^3)$的，辗转相除法是 Θ(logp)Θ(logp)Θ(logp) 的，因为辗转相除和消元每次必然使得数变小，势能只会减少，所以这个是均摊到$ Θ(n^2)$ 的，最终有复杂度 Θ(n2logn+n3)Θ(n^2logn+n^3)Θ(n2logn+n3)。 P7112 【模板】行列式求值 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) ll MOD; int cal(vector<vector<int>>& a, int n) { ll flag = 1; // 转化成上三角矩阵 for (int i = 1; i <= n; ++i) { // 枚举行 for (int k =...
DFS序专题
title: DFS序专题 categories: ICPC tags: null abbrlink: abe64aee date: 2023-08-09 00:00:00 DFS序专题 NC13611 https://ac.nowcoder.com/acm/problem/13611 题意：要求树上任意两点相同颜色之间的路径上的点也是相同颜色，k种颜色，求方案数 Solution：原问题等价于将树分割成若干连通块且相互之间颜色不同 其实是道数论题。 题意可以转化为将树分割为不超过 kkk 个连通块，每个连通块颜色不同。若将树分割为 iii 个连通块，则需要删去 i−1i-1i−1 条边，故方案数为 Cn−1i−1\mathrm{C}_{n-1}^{i-1}Cn−1i−1 。同时，要从 kkk 种颜色中选出 iii 中颜色染色，而且是有顺序的，故方案数为 Aki\mathrm{A}_{k}^{i}Aki 。 综上，总的方案数为： ans=∑i=1min(n,k)Cn−1i−1Akians=...
gausstmp
title: gausstmp categories: ICPC tags: null abbrlink: dd749cdf date: 2023-08-04 00:00:00 当我们枚举到第 iii 个变量，且前 iii 个变量都不是自由元时，如果第 i∼ni\sim ni∼n 行中这个变量的系数均为 000，那么第 iii 个变量是自由元。 [a1,1a1,2a1,3a1,4a1,50a2,2a2,3a2,4a2,5000a3,4a3,5000a4,4a4,50000a5,5|c1c2c3c4c5]\left[\begin{matrix} a_{1,1} & a_{1,2} & a_{1, 3} & a_{1,4} & a_{1,5} \\ 0 & a_{2,2} & a_{2, 3} & a_{2,4} & a_{2,5} \\ 0 & 0 & \color{red}{0}& a_{3,4} & a_{3,5} \\ 0 & 0 & 0 &...