- 博客(16)
- 收藏
- 关注
RSS订阅原创 数论——板子
数论欧几里得算法证明 O（ logn ）gcd求A和B的最大公约数假设X为最大公约数间接条件：X | A X | B假设A >= B建立方程式A + KB = C = A % B∵ X | A X | KB∴ X | A + KB∴ X | C∴ GCD（A,B）== GCD（B, A%B）然后我们就可以不断的往下辗转相除求GCD（B,C）B和C最大公约数也是X何时是个头GCD（KX , X ）其实这里能被整除，就已经知道求到GCD了再往下GCD （X ,
2021-01-27 11:33:33
430
原创 DP——板子
DP最长上升子序列（LIS）——O（nlogn）定义最长上升子序列是：1：只包含ai的子序列2：满足j<i并且aj<ai3：子序列长度最长朴素算法O（n^2） dp+二分（nlogn）dp数组维护的是以pos位置结尾最小可能的值，如果要打印最长上升子序列路径，开辟新数组path,倒着找合法序列，正序寻找就会出现1 2 4 6（2 8 6 7）这种不合法序列。虽然满足所有ai <aj 但是存在i>jvector<int>dp;for(int i=0
2021-01-23 19:56:35
257
原创 数据结构——板子
数据结构树状数组单点修改-区间修改注意1：记得空间初始化为n就可以了，内部自动开辟n+1空间struct BIT{ int n; vector<int>vec; BIT(int len=0) { n=len; vec.resize(n+1,0); } int pre(int x) { int sum=0; while(x) sum+=vec[x
2020-11-24 00:23:20
261
原创 图论——板子
图论最小生成树克鲁斯卡尔算法(Kruskal算法)——时间复杂度O（eloge）特性：稀疏图和记录路径普里姆算法——时间复杂度O（n^2）最小生树是否唯一问题：（次小生成树问题）朴素算法（m^2）1：暴力删除最小生树上的2：判断权值和以及是否是一棵树优化后，理论（mlogm）跑一次克鲁斯卡尔即可边权相等的边，边两点不同的并查集的边数<=所在不同的并查集个数-1保证最小生成树唯一 最小生成树：所有边权之和最小瓶颈生成树：定义无向图G，G的瓶颈生成树是一棵 “ 树上最大边权值
2020-11-10 01:10:22
225
原创 基础算法——板子
基础算法不AC各种情况TLE：1：多组测试案例，输入到文本结束2：多组测试案例，数组一定要清空WA：1：定义变量：注意要一个全局跟一个局部相同，意想不到得错误Codeblocks编译器问题1：数组越界，任然可以计算，不会报错2：int函数无返回值，任然可以返回，不会报错。快读template<class T>void read(T& x){ T res = 0, f = 1; char c = getchar(); while (!isdigit(c))
2020-09-17 11:44:55
754
原创 板子总和+
国庆板子前言对拍模板bat@echo off:loopD:/LSNU/codeforces/code/MakeData.exeD:/LSNU/codeforces/code/A.exeD:/LSNU/codeforces/code/force.exefc AC.txt WA.txtif not errorlevel 1 goto looppause:end说明模板//#pragma comment(linker,"/STACK:1024000000,1024000000")
2020-09-03 14:05:52
2498
原创 主席树入门浅谈
前言前因：朋友推给我一个主席树算法变种题，由于板子有改动就不会了，所以得出结论，算法没吃透精髓，然后白学。因此写了一篇博客写博客的原因有：1：以前自己假装懂了算法，会用板子，但是发现这样的习惯不好，必须得养成手撸算法的习惯，算法模型才是真正的吃透。（个人经验所得吧）2：写这篇博客当然主要方便自己以后复习，有一些遗忘的时候，可以回头来瞧瞧。如果不能理解得话，请多见谅———————————————————————————————————————主席树主席树 全称 可持久化线段树作用：可持久化维
2020-08-27 08:45:54
156
原创 乘法逆元的理解（一学就会的逆元）
为什么要使用乘法逆元1b\frac{1}{b}b1 mod p，这种是无法求模的，数学家就引入了逆元。逆元：用在模p意义下的整数代替在模p意义下的分数。在非模的情况下公式：a * b=1我们就可以说b是a的逆元，也可以说a是b的逆元。逆元==倒数。∵ a * 1a\frac{1}{a}a1 = 1∵ a * b = 1∴ b == 1a\frac{1}{a}a1性质：a的逆元（倒数）具有唯一性在模的情况下公式：a * b ≡\equiv≡ 1（mod p）我们可以说b是a的逆元
2020-07-15 15:41:04
1206
3
原创 字符串——板子
字符串回文字符串1：动态规划–O(n^2）string longestPalindrome(string s){ const int n = s.size(); bool dp[n][n]; memset(dp, 0, sizeof(dp)); int maxlen = 1; //保存最长回文子串长度 int start = 0; //保存最长回文子串起点 for(int i = 0; i < n; ++i) {
2020-06-08 16:50:21
113
原创 区间DP总结
一般问题把相邻符合条件的合并，来获得最优解概念区间类型动态规划是线性动态规划的拓展，它在分阶段划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。（例：f[i][j]=f[i][k]+f[k+1][j]）区间类动态规划的特点：合并：即将两个或多个部分进行整合。特征：能将问题分解成为两两合并的形式。求解：对整个问题设最优值，枚举合并点，将问题分解成为左右两个部...
2020-03-11 11:00:21
124
原创 floyd为什么可行？
总结最开始，看到这个算法，感觉代码简洁，好用，就只是把这个板子记住了，但是发现这样的习惯真心不好，所以现在想理解一下首先空间O（n2）== 时间O（n3）==== 作用：多源最短路径==...
2020-01-27 19:12:22
235
1
原创 排列组合数学的相邻问题（插空法-捆绑法-隔板法）
主要解决相邻或者不相邻问题插空法（处理不相邻问题）插空法就是对于解决 某几个元素要求不相邻 的问题时，先将其他元素排好，再将所指定的不相邻的元素插入它们的间隙或两端位置。首要特点就是不相邻。例题1：把1，2，3，4，5组成没有重复数字且数字 1，2不相邻的五位数，则所有不同排法有多少种？解析：本题直接解答较为麻烦，因为可先将 3，4，5三个元素排定，共有A（3，3）种排法，然后再将 1，...
2020-01-16 23:11:05
22332
1
转载 组合数学
组合数学符号C：组合数A：排列数（在旧教材为P）N：元素的总个数R：参与选择的元素个数!：阶乘，如5！=5×4×3×2×1=120C：Combination 组合P：Permutation排列 (现在教材为A-Arrangement)n个不同物品的排列数A（n,n）=A!原理：A（n,n）=n*（n-1)(n-2)···(n-n+1)=A!变形一下：从n个不同物品取m个的...
2020-01-16 10:59:43
226
原创 几何板子
板子成长史const int N=1e6+5;struct point{ double x,y;};struct line{ point p1,p2;} s[N];
2020-01-12 14:25:44
156
原创 loga(b)问题
换底公式但是这样得话，由于计算机double处理会缺少精度ex:int a=2,b=8;(int)log(b)/log(a)!=3,而是等于2；这里得问题就是精度得缺少解决方案(int)(log(b)/log(a)+0.5),这里用四舍五入得方法保证绝大多数正确答案优点O（1）时间复杂度这样的方法我提交CF的代码，也过了，但是目前自己无法证明这个公式绝对正确，但是CF过了，就能保...
2019-10-02 18:25:47
1797
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人