编程实用模版（更新中**...**）

1.最长非连续(上升/不上升/下降/不下降)子序列求解（时间复杂度最佳）**1.最长非连续(上升/不上升/下降/不下降)**子序列求解（时间复杂度最佳）

// O(nlogn) 复杂度求解
// 例：最长上升子序列 

#include <bits/stdc++.h>

using namespace std;
const int N = 1000005;
int n, ans, a[N], d[N], f[N];

int max_len(int x) //求解d数组中第一个(大于/大于等于/小于/小于等于)x的数下标
{
    int l = 1, r = n, mid, ans = n + 1;

    while (l <= r)
    {
        mid = (l + r) / 2;
      
        // if (d[mid] > x) //最长不下降子序列
        // if (d[mid] <= x) //最长下降子序列
        // if (d[mid] < x) //最长不上升子序列
        // if (d[mid] >= x) //最长上升子序列
        if (d[mid] >= x)
		{
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
  
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        d[i] = 1000000; //最长(上升/不下降)子序列
        //d[i] = 0; //最长(下降/不上升)子序列
    }
  
    for (int i = 1; i <= n; i++)
    {
        int now = max_len(a[i]); //求解下标
        f[i] = now;
        d[now] = a[i];
        ans = max(f[i], ans); //更新ans
    }
  
    cout << ans;
  
    return 0;
}

Copy

2.最长 山峰子序列/峡谷子序列（非连续）（第一个的变体）**2.最长山峰子序列/**峡谷子序列（非连续）（第一个的变体）

// O(n*n)
// 例：山峰子序列 

#include <bits/stdc++.h>

using namespace std;
int n, ans, a[105], f[105], g[105];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
  
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
        {
        	// if (a[j] < a[i]) // 山峰子序列(先上升后下降最长子序列) 
        	// if (a[j] > a[i]) // 峡谷子序列(先下降后上升最长子序列) 
		    if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
        }
    }
    for (int i = n; i >= 1; i--)
    {
        g[i] = 1;
        for (int j = n; j > i; j--)
        {
    	    // if (a[j] < a[i]) // 山峰子序列(先上升后下降最长子序列) 
        	// if (a[j] > a[i]) // 峡谷子序列(先下降后上升最长子序列) 
		    if (a[j] < a[i])
                g[i] = max(g[i], g[j] + 1);
    	}
	}
    for (int i = 1; i <= n; i++)
        ans = max(ans, f[i] + g[i] - 1);

    cout << ans << endl;
  
    return 0;
}

Copy

3.归并排序**3.**归并排序

逆序对定义：对于给定的一段正整数序列，如果排在前面的一个数字大于后面的数字，那么这两个数字就组成了一个逆序对。

//归并排序 O(nlogn)

#include <bits/stdc++.h>

using namespace std;

const int N = 5005;
int n, a[N], t[N];

void Mergesort(int l, int r)
{
    //1.只剩一个元素时返回
    if (l == r)
        return ;
    int mid = (l + r) / 2;
  
    //2.平分出两半进行分别处理
    Mergesort(l, mid);
    Mergesort(mid + 1, r);
  
    //3.合并 a[l ~ mid] 和 a[mid + 1 ~ r] 的两个有序数组
    int pl = l;
    int pr = mid + 1;
    int pt = l;
    while (pl <= mid && pr <= r)
    {
        // 降序 if(a[pl] >= a[pr])
        if (a[pl] <= a[pr]) {
            t[pt++] = a[pl++];
        } else {
            t[pt++] = a[pr++];
    		//逆序对 ans += mid - pl + 1;
		}
	}
    //4.处理剩余的 pl 或 pr 部分
    while (pl <= mid)
        t[pt++] = a[pl++];
    while (pr <= r)
        t[pt++] = a[pr++];
  
    //5.将 t 数组重新覆盖 a 数组
    for (int i = l; i <= r; i++)
        a[i] = t[i];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
  
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    Mergesort(1, n);
  
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
  
    return 0;
}

Copy

4.01背包+完全背包+分组背包dp（动态规划）4.01背包**+完全背包+分组背包dp（动态规划）**

//优化空间复杂度(一维数组)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, m, v[101], w[101], f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
  
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
  
    // 填满背包的做法补充:
	// memset(f, 0xcf, sizeof(f));
    // f[0] = 0; 
  
  
    // f[j]:在前 i 件物品中,选出总体积不超过 j 的物品,能够获得的最大价值
    // 由于 f[j] 需要从 f[j - v[i]] 转移而来,所以遍历 j 时应从大到小遍历
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m];
    // cout << max(f[m], 0); 
  
    return 0;
}

Copy

//完全背包(空间压缩版)
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5; //范围任意
int t, k, v[N], w[N], f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
  
    //输入
    cin >> t >> k;
    for (int i = 1; i <= k; i++)
        cin >> v[i] >> w[i];
  
    for (int i = 1; i <= k; i++)
        for (int j = v[i]; j <= t; j++) //从前往后便利
        //保证在使用f[j]时已经确定i - 1个物品的状态
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[t] << endl;
  
    return 0;
}

Copy

//分组背包dp(空间压缩版)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;
int n, m, s[N], f[N]; //f[j]表示前i个物品花费j元的最大价值
int v[N][N], w[N][N]; //如果数组过大可考虑vector存储如下
vector v[N], w[N]; //读入用v[].push_back()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
  
    //输入
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        //有n组物品,每组有s[i]个物品
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--) //倒叙遍历确保f[j - v[i][j]]还没更新
            for (int k = 1; k <= s[i]; k++)
                if (j >= v[i][k]) //饭钱不能比兜里的贵啊！
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m];
  
    return 0;
}

Copy

5.快速幂**5.**快速幂

ll fast_pow(ll a, ll b, ll p) { //计算 a ^ b % p 的结果 
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a % p;
        } a = a * a % p;
        b >>= 1;
    } return ans;
}

Copy

6.最大字段和dp6.最大字段和dp

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
int n, a[N], f[N];
int ans = -10005;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
  
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        f[i] = max(a[i], a[i] + f[i - 1]);
        ans = max(ans, f[i]);
    }
  
    cout << ans;
  
    return 0;
}

Copy

7.快速排序**7.**快速排序

//快速排序 quick sort
//时间复杂度：O(nlogn) ~ O(n²)
//稳定性：不稳定

void qsort(int l, int r)
{
    int x = a[(l + r) / 2]; //设定基准数x
    int i = l, j = r;       //设定左右边界i,j
    while (i <= j)
    {
        //升序
        while (a[i] < x) i++;
        while (a[j] > x) j--;
      
        //降序
        //while (a[i] > x) i++;
        //while (a[j] < x) j--;
      
        if (i <= j) //如果还没有交叉
        {
            swap(a[i], a[j]); //交换两个数
            i++;
            j--;
        }
    }
    if (l < j) qsort(l, j); //左端是否到底
    if (i < r) qsort(i, r); //有段是否到底
}

Copy

8.快读快写**8.**快读快写

//T 为输入输出数据类型

inline T Read()  {
	int sum = 0, fl = 1;
	int ch = getchar();
	for (; !isdigit(ch); ch = getchar())
	if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

inline void Write(T x)  {
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); // 48 是 '0'
}

Copy

9.递推求逆元**9.**递推求逆元

求 22 ~ n-2n−2 模 nn 的逆元

cin >> n;
    inv[1] = 1;
    for (int i = 2; i < n; i++) {
        inv[i] = ((-1 * (n / i) * inv[n % i] % n) + n) % n;
        cout << inv[i] << ' ';
    }

我的世界：https://classic.minecraft.net/?join=F31BFw4IAsD4YPkR