雨羊的博客

归并排序

参考链接：图解排序算法(四)之归并排序归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略【分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"整合"在一起，即分而治之】。根据图所示，首先将序列递归分解，直到分成的

排序

容斥定理

要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。简单来说，就是奇加偶减。举个例子：求1~n中多少个数不是2,3,5,7的倍数，当n=10,结果只有

数学问题

分解质因子

任何一个合数可以分解为几个质数的乘积，这些质数也必然是这个合数的约数。超时模板： #include<bits/stdc++.h> using namespace std; vector<int> fun(int n) { vector<int> v; for (int i = 2; i <=

数学问题

素数

素数判断 bool is_prime(int u) { if (u == 0 || u == 1)return false; if (u == 2)return true; if (u % 2 == 0)return false; for (int i = 3; i <= sqrt(u);

数学问题

欧拉降幂

欧拉定理： phi(n)为n的欧拉函数值，当n为质数时，n的欧拉函数值为n-1 降幂公式：对于一个问题求 a^b %n 可以直接根据右边的条件把式子转换成上面三个中的一个

数学问题

汉诺塔模板

//汉诺塔 # include <stdio.h> void hanoi ( int n, char a, char b, char c ) { if (n == 1) //只剩一个盘子时 { printf("%c ->

递归

欧拉函数

参考链接浅谈欧拉函数什么是欧拉函数欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示。特殊的，φ(1)=1。如何计算欧数值拉函欧拉函数的通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn),其中p1, p2……pn为n的所有

数学问题

线段树

参考链接据结构——线段树引例给出n个数，n<=100，和m个询问，每次询问区间[l，r]的和，并输出。一种回答：这也太简单了，O（n）枚举搜索就行了。另一种回答：还用得着o(n）枚举，前缀和o(1)就搞定。那好，我再修改一下题目。给出n个数，n<=100，和m个操作，每个操作可能有两种

树

LIS-最长上升子序列

LIS 方法一：DP dp动态规划状态设计：dp[i]代表以a[i]结尾的LIS的长度状态转移：dp[i]=max(dp[i], dp[j]+1) (0<=j< i, a[j]< a[i]) 时间复杂度：O(N^2) 例题：https://blog.csdn.net/y201619819/art

动态规划

组合数C(n,m)的计算

C(n,m)的计算方式： 1.公式：C(n,m) = n!/((n-m)! * m!)，在算法上较难实现，阶乘很快会爆 long long 2.递推：C(n,m) = C(n-1,m-1) + C(n-1,m) 在算法上当然会采用第二种方式计算，而且因为 C(n,m)本身值很大，所以大多数碰见它的情

数学问题