克鲁斯卡尔重构树
title: 克鲁斯卡尔重构树categories: - ICPCtags: - nullabbrlink: 1877ddc4date: 2023-09-02 00:00:00一类以并查集在建树过程中维护各种信息的值——克鲁斯卡尔重构树前身第一次见到是在zzu的校赛中，印象深刻。 H. Sum of Maximum Weights题意给定一棵树，求树上任意两点间最短路径中的最大边权的和。 官方 Solution 将边按权值排序，每次处理当前的最大权值。 处理每条边时，由于树的性质，边的起点和终点一定连通。设两个组 $U$ 和 $V$，则 $U$ 组中任意成员到 $V$ 组中任意成员的最大路径边权必为当前边的权值 $e$，故可以写出 $ans += siz[u] \times siz[v] \times e$。 将两组合并，重复上述过程，最终得到答案。 我的理解如果了解克鲁斯卡尔重构树，这就是一道板子题。 #include <bits/stdc++.h> #define int long long using namespace...
单调栈
title: 单调栈categories: - ICPCtags: - nullabbrlink: 16518a5ddate: 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 l[N]; int...
SOSdp
title: SOSdpcategories: - ICPCtags: - nullabbrlink: 4588451bdate: 2023-08-24 00:00:00从子集和问题到and卷积枚举子集：$O(3^{n})$ 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] = \sum_{j \subseteq i} a[j]$ 一个平凡的做法是直接枚举子集：$O(3^{n})$ for (int i =...
判负环——spfa
title: 判负环——spfacategories: - ICPCtags: - nullabbrlink: aad58836date: 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 i=1;i<=n;i++) ...
一类哈密顿路径_回路为背景的状压dp
title: 一类哈密顿路径_回路为背景的状压dpcategories: - ICPCtags: - nullabbrlink: 1033a034date: 2023-08-21 00:00:00https://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: - ICPCtags: - nullabbrlink: f6229479date: 2023-08-20...
KMP
title: KMPcategories: - ICPCtags: - nullabbrlink: ad32db8fdate: 2023-08-19 00:00:00题目描述给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l, r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。对于 $s_2$，你还需要求出对于其每个前缀 $s’$ 的最长 border $t’$ 的长度。 输入格式第一行为一个字符串，即为 $s_1$。第二行为一个字符串，即为 $s_2$。 输出格式首先输出若干行，每行一个整数，按从小到大的顺序输出 $s_2$ 在 $s_1$ 中出现的位置。最后一行输出 $|s_2|$ 个整数，第 $i$ 个整数表示 $s_2$ 的长度为 $i$ 的前缀的最长 border 长度。 样例...
行列式与矩阵树定理
title: 行列式与矩阵树定理categories: - ICPCtags: - nullabbrlink: b76954abdate: 2023-08-12 00:00:00行列式与矩阵树定理行列式取模板子：对于模数非质数采用辗转相除 消元操作是$ Θ(n^3)$的，辗转相除法是 $Θ(logp)$ 的，因为辗转相除和消元每次必然使得数变小，势能只会减少，所以这个是均摊到$ Θ(n^2)$ 的，最终有复杂度 $Θ(n^2logn+n^3)$。 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 = i + 1; k <= n; ++k) { ...
DFS序专题
title: DFS序专题categories: - ICPCtags: - nullabbrlink: abe64aeedate: 2023-08-09 00:00:00DFS序专题NC13611 https://ac.nowcoder.com/acm/problem/13611题意：要求树上任意两点相同颜色之间的路径上的点也是相同颜色，k种颜色，求方案数Solution：原问题等价于将树分割成若干连通块且相互之间颜色不同其实是道数论题。 题意可以转化为将树分割为不超过 $k$ 个连通块，每个连通块颜色不同。若将树分割为 $i$ 个连通块，则需要删去 $i-1$ 条边，故方案数为 $\mathrm{C}{n-1}^{i-1}$ 。同时，要从 $k$ 种颜色中选出 $i$ 中颜色染色，而且是有顺序的，故方案数为 $\mathrm{A}{k}^{i}$ 。 综上，总的方案数为： $ans= \sum_{i=1}^{\min(n,k)}\mathrm{C}{n-1}^{i-1}\mathrm{A}{k}^{i}$ 可以线性求逆元，枚举 $i$ 实现。...
gausstmp
title: gausstmpcategories: - ICPCtags: - nullabbrlink: dd749cdfdate: 2023-08-04 00:00:00当我们枚举到第 $i$ 个变量，且前 $i$ 个变量都不是自由元时，如果第 $i\sim n$ 行中这个变量的系数均为 $0$，那么第 $i$ 个变量是自由元。 $$\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 & a_{4,4} & a_{4,5} \0 & 0 & 0 & 0 & a_{5,5}\end{matrix} \middle...