再也不想上机的时候手写堆了。

万能头：

#include <bits/stdc++.h>

vector 变长数组

动态数组，可以变长。

头文件：

#include <vector>

初始化

// 一维
vector<int> a; // <>里面写数据类型
vector<int> v(n); // 指定长度为n，初始值均为0
vector<int> v(n, 114514); // 指定长度为n、初始值都是n-1
vector<int> a{1,2,3,4,5}; // 初始化，数组长度为5
// 拷贝初始化
vector<int> a(n, 1);
vector<int> b(a); // b也是长度为n、初始值为1的数组
vector<int> c = a; // 另一种拷贝初始化方法

// 二维
vector<int> v[5]; // 第一维固定长度5，第二位可变长
vector<vector<int>> v; // 二维长度均可变，可以直接push_back进去一个数组
vector<vector<int>> a(n, vector<int>(n, 0)); // 行列均长度n且初始值为0

阅读全文

线性DP：递推方程有明显的线性的顺序。
考虑两个问题：如何状态表示（集合+属性）、如何状态计算（划分状态转移集合）
T1：

状态表示： 记录所有从起点走到(i,j)的路径中的路径数字之和的最大值。
状态计算：f[i,j] = max(f[i-1][j], f[i-1][j-1]) + a[i,j]
需要注意需要把f[i,j]初始化为极小值，避免算到三角形右边的元素。

T2：最长上升子序列

状态表示：使用一维数组，f[i]表示以第i个数结尾的上升子序列的长度的最大值。
状态计算：计算f[i]，去看倒数第二个数是哪个数，共i种可能，以编号1、2、3、……、i-1结尾或原本没有数（记为0）。每个循环先看是否满足上升的条件，若满足，则这个f[i]_j = f[j]+1，最后计算一个最大的f[i]_j就得出了f[i]的值。
时间复杂度计算：状态数量 × 转移的数量。此时是$n^2$。

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int a[N], f[N];

int main(){
    scanf(“%d”, &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++){
        f[i] = 1; //先全部赋值为1，只有a[i]一个数
        for(int j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, f[i]);
    printf("%d\n", res);
    return 0;
}

如何保存最长序列？
创建一个数组g[i]，存储每个转移是怎么转移过来的（记录上一个状态的id，也就是找f[i,j]最大值时找到的位置）。

阅读全文

本章主要介绍动态规划的常用思路，并介绍了背包问题里面的01背包、多重背包的解题思路和代码

01背包

01背包问题为：给定背包总体积，给N个物品，每个物品有一个体积和重量，只能用一次或不用，问最大重量是多少？
下面是思路，定义函数f(i,j)代表：仅包含前i个物品且总体积小于等于j的背包的最大价值是多少，故最终需要的结果是f(N,V)。
初始时把所有值都设为0，且i或j等于0的本身值就为0。
对于一个新的状态f(i,j)，可能的值有下面两种可能，如果包含i，则答案为f(i-1，j-vi) + wi；如果不包含i，则为f(i-1,j)。这两个值取最大值就可以算出f(i,j)。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for(int i=1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i=1; i <= n; i++)｛
        for(int j = 1; j <= m; j++){
            f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    ｝
    cout << f[n][m] << endl;
}

阅读全文

数据结构是大一下的课程，总体学的还好，就当复习一下，以及看看有没有什么其他内容。

链表与邻接表

数组模拟单链表

使用两个数组e[N]和nxt[N]，使用下标关联起来。其他操作与正常链表一样。

数组模拟双链表

使用三个数组e[N]、l[N]和r[N]。

初始化：

r[0] = 1;
l[1] = 0;

阅读全文

本节主要学习双指针、位运算、离散化、区间合并等知识。

双指针算法

常见类型：指向两个不同序列 或者 指向同一个系列的不同位置。

通用模版

for(i = 0, j =0; i < n; i++){
    while(j<i && check(i,j)) j++;
    //每道题目的具体逻辑
}

阅读全文