Keep Runing
最大团算法 最大团算法
写在前面, 补图的最大独立集点数 = 原图的最大团点数。在原图中有的边在补图中都没有,原图的最大团的所有边去掉之后,其就是补图的最大独立集。 最大团一般图中的最大团问题写在前面,求最大团,我们用算法3,最快,极大团数量只能用算法1。
2021-04-15
线性复杂度求解n次多项式 -- Horner算法 线性复杂度求解n次多项式 -- Horner算法
算法分析 代码实现#include<iostream> using namespace std; int main(){ int n, x, sum = 0; cin>>n>>x; int a[20];
2020-11-21
最近对问题 最近对问题
详解见教材《算法分析与设计基础》 板子#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <al
2020-11-21
凸包问题 凸包问题
写在前面,以下算法的时间复杂度都为$O(nlogn)$ 快包讲解见教材《算法设计与分析基础》 #include<stdio.h> #include<stdlib.h> int g_result[240][2]; /* *注:
2020-11-20
欧几里得算法求最大公约数正确性证明与时间复杂度分析 欧几里得算法求最大公约数正确性证明与时间复杂度分析
正确性证明Portal 时间复杂度分析 两数相除,余数必定严格小于除数,被除数不一定。 我们可以发现两轮,a,b都各自缩小一半,直到递归结束(我们也不清楚),所以最坏时间复杂度为$O(log(a + b))$(得出结论不严谨,但是我们只需
2020-09-12
点与直线之间的位置关系 点与直线之间的位置关系
规定直线的方向只能指向只能为上,右之间 证明 二维向量的叉积即为有向面积。式子其实就是向量CA与向量CB的叉积/2即为三角形ABC的面积,叉积为正,即$sina$为正,即为逆时针,c点在左侧,反之为顺时针在右侧。
2020-08-18
向量的点积与叉积 向量的点积与叉积
写在前面,这里我们只考虑二维,三维叉积。高维叉积无实际应用,不做赘述。 点积与叉积点积又被称为内积,叉积又被称为外积。只有在三维向量空间中,我们才能将叉积具象化,二维无法,高维不讨论。 计算公式$\vec a$ = $(x1, x1, x
2020-08-17
字符串结论小结 字符串结论小结
Periodicity Lemma(周期性引理): 两个由长度分别为a,b进行无限循环的字符串,如果它们前(a+b-gcd(a,b))个字符相同,那么它们就是相同的。例题 2020牛客多校第一场F题
2020-08-10
EK算法求最小费用流 EK算法求最小费用流
写在前面,费用流也称作最小费用流. 给定流量的问题称为最小费用流问题, 给定流量为最大流的问题我们称为最小费用最大流问题. 解决问题求一个图中, 一个点到另一个点, 在保证最大流量的情况下, 求最小费用. 图中每条边有三个特性, 容量, 单
2020-07-04
1 / 2