基础算法

快速幂

主要是用来求解,基于二分的思想

typedef long long ll;
ll binPow(ll a, ll b, ll mod)
{
    if(b==0) return 1;
    if(b%2==1)//为奇数 转换成b-1
    {
        return a * binPow(a, b-1, mod) % mod;
    }else{
        ll mul = binPow(a, b/2, mod);
        return mul * mul %mod;
    }
}

其实根据这个可以引申出来快速乘

//插个位置吧

二分法

int bin_search(int *a, int n, int x)
{
    int left = 0, right = n;
    while (left < right)
    {
        int mid = (left + right) >> 1;
        if(a[mid] >= x) right = mid;
        else left = mid + 1;
        
    }
    return left;
}

前缀和与差分

离散化

离散化的作用就是,当一系列的数出现的时候,数组可能开不了这么多,但是又需要存下来,就可以离散化,相当于就是把这些数字给排个名,所以排序完用二分查找位置

#include <bits/stdc++.h>
using namespace std;
// 离散化

const int maxn = 1e5;
int olda[maxn];
int newa[maxn];

int main()
{
	int n;cin >> n;
	for(int i = 0;i<n;i++)
	{
		scanf("%d",&olda[i]);
		newa[i] = olda[i];
	 } 
	
	sort(olda,olda+n);
	int size = n;
    // 这个是去重的操作 
//	size = unique(olda,olda+n) - olda;
	for(int i = 0;i<size;i++)
	{
		//这个值就是对应在数组中的位置 相当于在整体数组中的大小排名
		newa[i] = lower_bound(olda,olda+n,newa[i]) - olda;
	}
	for(int i = 0;i<size;i++)
	{
		cout << newa[i] <<" ";
	}
	return 0;
}

排列

next_permutation()函数

自写排列函数

#include <bits/stdc++.h>
using namespace std;

bool vis[100];
int b[20];
//int a[20] = {1,2,3,4,5,6,7,8,9,10,11,12,13};
int a[20] = {4,3,5,1,2};
int sum = 0;
//s表示的是当前新数组的位置指针
//t表示的是需要循环的轮数
// 每次挑选都是经过for循环遍历 因此所有的数字都会被选到 但是当你进入那一层递归的时候 需要先置为访问
void dfs(int s, int t)
{
	if(s==t)
	{
		for(int i = 0;i<s;i++)
		{
			cout << b[i];
		}
		cout << "\n";
		sum++;
		return;
	}
	for(int i = 0;i<t;i++)
	{
		if(!vis[i])
		{
			vis[i] = true;
			b[s] = a[i];
			dfs(s+1,t);
			vis[i] = false;
		}
	}
}
int main()
{
	dfs(0, 5);
	cout << sum;
	return 0;
}

递归

这个可以输出一个数字由各个数字的组成方式,并且罗列出来

#include <bits/stdc++.h>
using namespace std;
//表示每次递归的当前的值 递减到0 就结束了
//前面代表一个指针 指向数组位置
int n;
vector<int>num;
void dfs(int sum)
{
	if(sum>n) return;
	if(sum==n)
	{
		for(int i = 0;i<num.size();i++)
		{
			cout << num[i]<<" ";
		}
		cout <<"\n";
		return;
	}
	int start = num.empty() ? 1 : num.back();
	//这个可以限制输出顺序是增序还是平替
	for(int i = start;i<=n;i++)
	{
		num.push_back(i);
		dfs(sum+i);
		num.pop_back();
	}
}

int main()
{
	// 这是数据的规模
	cin >> n;
	dfs(0);
	return 0;
}