书P368题目地址：https://ac.nowcoder.com/acm/contest/1056/C ① 0/1分数规划https://blog.nowcoder.net/n/70ad985a57bc4085aaee4d40fd2a9451 ② Prim算法https://blog.nowcoder.net/n/012b92baab1f4ee59bb17b9bcb8dadb4 #include<bits/stdc++.h> using namespace std; const double inf=1e18; const int N=15e4+10; const int max...

书P185 0/1分数规划是指给定n对整数ai和bi，从中选若干对，使选出的数对的a之和与b之和的商最大 猜测一个值L，然后考虑是否存在一组解{x1,x2,...,xn}，满足：  如果：则L比答案小，否则比答案大 因为L具有单调性，所以可以使用二分法。 模版题：POJ2976 更详细地介绍：https://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html

题目链接：https://ac.nowcoder.com/acm/contest/1056/B书P368 ①：Kruskal算法https://blog.nowcoder.net/n/012b92baab1f4ee59bb17b9bcb8dadb4本题中用这个算法求去掉根节点1后的最小生成树 ②贪心策略本题要找满足1号节点度数不超过S的最小生成树如果去掉节点1后，连通块个数为T大于S，则无解。接下来我们从每个连通块中寻找与节点1边长最短的点，加入生成树然后还可以改S-T条边，每条（1,x）的边，我们找到与1的本身路径最长的一条减去（1,x）的长度，那么整个生成树长度就减少了 /*#includ...

题目地址：https://ac.nowcoder.com/acm/contest/1056/A思路：n个节点的树有n条边，先把边从小到大排序，依次扫描每一条边。如果是一条边，那么就不需要加边如果是二条边，需要加一条边，这条边的权值应该是当前边的权值+1，如果加边的权值相同，最小生成树就不唯一如果是三条边，需要加二条边，二条边权值加起来是（当前权值+1）× 2...... #include<bits/stdc++.h> using namespace std; const int maxn=6000+10; struct rec { int x,y,z; }edge[maxn*5];...

①Kuskal算法（克鲁斯卡尔） 时间复杂度为O(m log m) #include<bits/stdc++.h> using namespace std; const int maxn=2e5+10; struct edge { int u,v,w; }; edge a[maxn]; bool cmp(edge f1,edge f2) { return f1.w<f2.w; } int fa[5010]; int checkk(int k) { if(fa[k]==k) return k; return fa[k]=checkk(fa[k]); } int main() {...

书P156设 A 是 n * m 矩阵，B 是 m * p 矩阵，则 C = A * B 是 n * p 矩阵 则：  即 C 第 i 行 第 j 列数，是由 A 的第 i 行的 m 个数与 B 的第 j 列的 m 个数分别相乘再相加得到的得到的是一个 n * p 的矩阵 矩阵乘法满足结合律，分配律，但不一定A * B = B * A 例子：

题目地址：https://ac.nowcoder.com/acm/contest/1055/G《算法进阶》P362 ①关于min的矩阵乘法：https://blog.nowcoder.net/n/09c63cb41aba4ab5bf67450b243e0eba若矩阵 保存任意两点之间恰好经过m条边的最短路，则： 相当于增加一个中转点就增加一条边 ②矩阵快速幂本来两个二维数组不能直接相乘，但重载运算符后，直接按照矩阵乘法规律相乘，方便许多 总时间复杂度O (T^3 log N) #include<bits/stdc++.h> using namespace std; const in...

#include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; const int maxn=300+10; int a[maxn][maxn],d[maxn][maxn],pos[maxn][maxn];//d[i][j]表示点i到j的最短距离，pos[i][j]表示点i到j路径的中转点，如果没有为0 int n,m,ans=INF; vector<int> path;//记录路径 void get_path(int x,int y)//寻找路径 { if(pos[x][y]==0) { r...

#include<bits/stdc++.h> using namespace std; const int maxn=26+1; int n,m; int a[maxn][maxn],b[maxn][maxn]; int floyd() { memcpy(b,a,sizeof(b)); for(int k=0;k<n;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { b[i][j]|=b[i][k]&b[k][j]; if(b[i][j]==b[j][i]&&b[i][j]==1&a...

今天看《算法竞赛进阶指南》，刚好看到了容斥原理一章，所以就和大家说一下我对容斥原理的理解： 容斥原理是一种人们为了可以不遗漏，不重复发明的新计数方法。 基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去 比如下面这张图：  先把A、B、C集合加起来，再去掉A∩B ，B∩C ，A∩C 和 A∩B∩C的。 这是容斥原理的计算公式：  先把全部加在一起，去掉两个集合重复的，去掉三个集合重复的，一直下去，就会得到结果 还有推荐练习题：https://ac.nowcoder.com/acm/contest/1027/A这道题利用了容斥原理的思...

比赛地址 ： https://www.luogu.com.cn/contest/28258我参加的是Div.2,比Div.1简单第一题:只要你有耐性，慢慢敲就好了。代码： #pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; int main() { string a; cin>>a; if(a[0]=='M'&&a[1]=='D'&&a[2]=='A') { int p; for(int i=7;i>=0;i--) { if(a[i]>='0...

N个矩形的面积并 算法原理：线段树 基础习题: https://www.luogu.com.cn/problem/P5490 #include <stdio.h> #include <iostream> #include <algorithm> #define lson (x << 1) #define rson (x << 1 | 1) using namespace std; const int MAXN = 1e6 + 10; typedef long long ll; int n, cnt = 0; ll x1, y1, x2...

算法原理：线段树 基础习题: http://poj.org/problem?id=1177 #include <iostream> #include <stdio.h> #include <algorithm> #define lson (x << 1) #define rson (x << 1 | 1) using namespace std; const int MAXN = 2e4; int n, X[MAXN << 1]; int x1, y1, x2, y2, pre = 0; /* 先初始化为 0 */ str...