均值不等式
均值不等式 （1）对实数a,b有a2+b2>=2ab(当且仅当a=b时取“=”号)，a2+b2>=−2ab(当且仅当a=−b时取“=”号)a^2+b^2>=2ab(当且仅当a=b时取“=”号)，a^2+b^2>=-2ab(当且仅当a=-b时取“=”号)a2+b2>=2ab(当且仅当a=b时取“=”号)，a2+b2>=−2ab(当且仅当a=−b时取“=”号) （2）对于非负实数a,b,有$a+b>=2\sqrt{ab},即{a+b \over 2}>=\sqrt{ab} $ （3）对非负实数a,b有a(a−b)>=2ab>=0a(a-b)>=2 \sqrt{ab} >=...
质数筛选
常见方法有： 试除法： 朴素筛法O(nlogn)O(nlogn)O(nlogn)： 埃氏筛法O(nloglogn)O(nloglogn)O(nloglogn)： 线性筛法O(n)O(n)O(n)： Java代码模板(朴素筛时间复杂度O(nlogn)O(nlogn)O(nlogn) 12345678910111213141516171819202122232425262728293031323334import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(primes(n)); } /** * 朴素筛法 */ static int primes(int n) { boolean st[] = ...
逆元
逆元 ≡符号的意思 在数学中，符号≡表示模同余的关系。当我们写a≡b(modm)a \equiv b \pmod{m}a≡b(modm)时，意思是a与b在模m下同余，也就是说它们除以m后得到相同的余数。换句话说，a和b的差是m的倍数。例如，17≡3(mod7)17 \equiv 3 \pmod{7}17≡3(mod7)表示17和3在模7下同余，因为它们相减得到的结果是7的倍数，即17−3=14=2×717 - 3 = 14 = 2 \times 717−3=14=2×7。 逆元的本质： 逆元的定义： 假设 a 除 b，且a和b都是整数，非浮点数，那么我们希望不做除法，因为取余数的话除法很麻烦，所以我们希望把除法变成乘法，希望找到一个数，使得a/b的余数 == ax%m。 即对于某一个b，我们能够找到一个数x，使得a/b和ax模m的余数相同的话， 则把x记作b的模m的逆元，记作b的-1次方； 即b的逆元， b的-1次方，是一个整数，是一个标记。即我们可以把所有a/b的情况转化为a*b的逆元的情况下 %...
互质
互质 什么是互质： 互质是公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形。 在考虑两个区间互质的情况之前我们先考虑它的一个子问题，一个数x与一个区间[l,r]的互质问题。 处理这个问题，最简单的方法肯定是遍历区间，复杂度为O(n)，n为区间长度，显然太慢。 这时我们可以逆向思维，转换问题，我们可以考虑求不互质的个数，然后再用全部个数减去不互质的个数。 不互质也就是说，有公共的因子，如果把问题转换成求同有某个因子的数量，那就好处理， 比如如果计算都有因子2，设区间为[l,r]，那我们只要计算1~r的个数减去1~l-1的个数，也非常好算，只要r/2-(l-1)/2...
算法题型分析
算法题型分析 DFS算法： 数据类模拟类算法题 地图模拟类算法题
正向代理和反向代理
正向代理和反向代理 一、代理 代理就相当于中间商,本来A和B是可以直接连接的,但是此时添加了一个C在中间,A跟B不直接连接,而是通过C作为中介进行连接。最常见的例子就是二手东,其实很多我们租房子时签约的人不是房子的真正房东,而是房东委托的中介,房东不想管事或者房子太多,只靠自己无法进行管理,所以才会通过中介(代理)进行处理,像蛋壳、自如这样的租房软件其实也是中介的一种,真正的房东是直接将房子委托给这样的第三方中介进行出租。 一个完整的请求是由: client(客户端) -> proxy(代理) -> server(服务端) 组成。 二、正向代理 正向代理: 顺着请求的方向进行的代理，即代理服务器它是由你配置为你服务，去请求目标服务器地址。 举例一:...
快速幂
快速幂 说明： 快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以$$O(logn)$$的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。 让我们先来思考一个问题：7的10次方，怎样算比较快？ 方法1：最朴素的想法，7*7=49，49*7=343，… 一步一步算，共进行了9次乘法。 这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。 方法2：先算7的5次方，即7*7*7*7*7，再算它的平方，共进行了5次乘法。 但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。 方法3：先算7*7得49，则7的5次方为49*49*7，再算它的平方，共进行了4次乘法。 模仿这样的过程，我们得到一个在$$O(logn)$$时间内计算出幂的算法，也就是快速幂。 Java模板(迭代法) 12345678910static long qpow(long a,int n){ long sum =1; while(n!=0){...
排列组合
排列组合 Java模板 12345678910111213141516171819202122232425```## C++模板```c++int arrange(int m,int n){ if(m==n) return n; return m*arrange(m-1,n);}void dfs(int x){ if(x==n){ for(int i =1;i<=n;++i) printf("%d",a[i]); for(int i=1;i<=n;++i){ if(!mark[i]){ a[x]=i;++mark[i]; } dfs(x+1); mark[i]=0; //回溯 } }}
个人算法学习进度表
个人算法学习进度表 算法名称 是否已学 算法名称称 是否已学 算法名称 是否已学 算法名称称 是否已学 DFS ✅ BFS ✅ 二分 ✅ 全排列 ✅ 差分 ✅ 前缀和 ✅ 二维差分 ✅ 二维前缀和 ✅ 树状数组 ✅ 并查集 ✅ 贪心 ✅ 线性筛 ✅ 杜教筛 ✅ Dijkstra ✅ Kruskal ✅ Manacher ✅ 逆元 ✅ 快速幂 ✅ 质因数分解 ✅ Prim ✅ Segment Tree(线段树) ✅ 背包DP ✅ 线性DP ✅ 状态压缩DP ✅ 树形DP ✅ 数位DP ✅ 互质 ✅ KMP ✅ 链式向前星 ✅ 模拟退火 ✅ ST表 ✅
竞赛算法使用分析
竞赛算法使用分析 说明： 关于算法分析本人全凭经验之谈，具体还是要根据自身和题目情况而定 针对有序性数据（单调增、或者减）可以联想到二分或者双指针等算法 针对时序性数据可以联想使用优先队列。 带有状态绑定的可以联想DP 数字或者字符特征统计的可以尝试联想数位DP或者Manacher或者KMP 数据区间操作类可以联想差分、前缀和、树状数组、线段树 矩阵类可以试着联想纬度压缩后进行双指针，或者使用二分差分或者二维前缀和 关于线性平均类题型可以思考一下方差相关的数学定理和平均相关的数学定理 前缀和的问题开数组最好是从1开始比较好
