快速排序


参考文献:快速排序算法快速排序(图解详细流程)1. 排序流程快速排序算法通过多次比较和交换来实现排序,其排序流程如下:(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边

差分数组


参考文献:什么是差分数组?背景如果给你一个包含5000万个元素的数组,然后会有频繁区间修改操作,那什么是频繁的区间修改操作呢?比如让第1个数到第1000万个数每个数都加上1,而且这种操作时频繁的。此时你应该怎么做?很容易想到的是,从第1个数开始遍历,一直遍历到第1000万个数,然后每个数都加上1,如

基数排序


基数排序时间复杂度 O(kn),k 为要排序的数字的最大长度例如对 342、58、576、356 进行排序不足的位数看做是 0342 058 576 356第一步按照个位将数字依次放到不同的位置0: 1: 2: 3423: 4: 5: 6: 576, 3567: 8: 0589: 把上边的数字依次拿

容斥定理


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

分解质因子


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

矩形的交面积


矩形边平行X轴或Y轴输入:矩形某对角线上两个点输出:交面积#include<iostream>#include<cmath>using namespace std;int main() {double x1,y1,x2,y2;double x3,y3,x4,y4;double

莫队算法 牛客多校赛题


题目描述Given a sequence of integers a 1 , a 2 , ..., a n and q pairs of integers (l 1 , r 1 ), (l 2 , r 2 ), ..., (l q , r q ), find count(l 1 , r 1 ),co

汉诺塔模板


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

欧拉降幂


欧拉定理:phi(n)为n的欧拉函数值,当n为质数时,n的欧拉函数值为n-1降幂公式:对于一个问题求 a^b %n可以直接根据右边的条件把式子转换成上面三个中的一个例题:题目大意:求2n%1e9+7结果,1<=n<=10100000题解:n很大,所以要用大数取模。p与2互质,所以2n%p