Acwing算法总结

算法基础

快速排序算法模板

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

AcWing 785. 快速排序

#include<iostream>
using namespace std;
const int N=1e6+10;
int a[N];int n;
void quick_sort(int *a,int l,int r){ 
    if(l>=r)return;
    int i=l-1,j=r+1;int t=a[(l+r)>>1];
    while(i<j){
        do i++;while(a[i]<t);
        do j--;while(a[j]>t);
        if(i<j)swap(a[i],a[j]);
    }
    quick_sort(a,l,j);quick_sort(a,j+1,r);
    
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    quick_sort(a,0,n-1);
     for(int i=0;i<n;i++){
       cout<<a[i]<<" ";
    }
    
    return 0;
}

归并排序算法模板

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

AcWing 787. 归并排序

#include<iostream>
using namespace std;
const int N=1e6+10;
int q[N],n,temp[N];
void merge_sort(int q[],int l,int r){
    if(l>=r)return;
    int mid=l+r>>1;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j])temp[k++]=q[i++];
        else temp[k++]=q[j++];
    }
    while(i<=mid)temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];
    
    for(i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>q[i];
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++)cout<<q[i]<<" ";
    
    return 0;
}

AcWing 788. 逆序对的数量

#include<iostream>
using namespace std;
const int N=1e6+10;
int n,q[N],temp[N];
long long  ans=0;
void merge_sort(int q[],int l,int r){
    if(l>=r)return;
    int mid=l+r>>1;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j])temp[k++]=q[i++];
        else ans+=mid-i+1,temp[k++]=q[j++];
    }
    while(i<=mid)temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];
    
    for(i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>q[i];
    }
    merge_sort(q,0,n-1);
    cout<<ans;
    return 0;
}

整数二分算法模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

AcWing 789. 数的范围

#include<iostream>
using namespace std;
const int N=1e6+10;
int n,q,k,a[N];

int main(){
    cin>>n>>q;
    for(int i=0;i<n;i++)cin>>a[i];
    while(q--){
        cin>>k;
        int l=0,r=n-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(a[mid]<k)l=mid+1;//当a[mid]<k时，最左边的那个k值肯定在mid右边，所以l=mid+1
            else r=mid-1;
        }
        if(a[l]!=k){
            cout<<"-1 -1"<<endl;
            continue;
            
        }
        int l1=l,r1=n;
        while(l1+1<r1){
            int mid=l1+r1>>1;
            if(a[mid]<=k)l1=mid;
            else r1=mid-1;//当a[mid]>k时，最右边的那个k值肯定在mid左边，所以r1=mid-1
        }
        cout<<l<<" "<<l1<<endl;
        
    }
    return 0;   
}

浮点数二分算法模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

AcWing 790. 数的三次方根

#include<iostream>
using namespace std;
double n;
int main(){
    cin>>n;
    double l=-10000,r=100000;
    while(r-l>1e-7){
        double mid=(l+r)/2;
        if(mid*mid*mid<=n)l=mid;
        else r=mid;
        
    }
    printf("%.6f",l);
    
    return 0;
}

高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度乘低精度

// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

高精度除以低精度

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

一维前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

AcWing 795. 前缀和

#include<iostream>
using namespace std;
const int MAX=100000+10;
int sum[MAX];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        sum[i]=sum[i-1]+a;
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
    
    
    return 0;
}

二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

AcWing 796. 子矩阵的和

#include<iostream>
using namespace std;
const int MAX=1010;
int a[MAX][MAX];
int n,m,q;
int sum[MAX][MAX];
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    }
    while(q--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<endl;
    }
    
    return 0;
}

一维差分

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

AcWing 797. 差分

#include<iostream>
using namespace std;
const int N=100010;
int b[N],n,q,a[N];
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        b[i]=a[i]-a[i-1];
    }
    while(q--){
        int l,r,c;
        cin>>l>>r>>c;
        b[l]+=c;
        b[r+1]-=c;
    }
    for(int i=1;i<=n;i++){
        b[i]=b[i]+b[i-1];
        cout<<b[i]<<" ";
    }
    
    
    return 0;
}

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

AcWing 798. 差分矩阵

#include<iostream>
using namespace std;
const int N=1010;
int n,m,q,a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int t;
            cin>>t;
            insert(i,j,i,j,t);
        }
    }
    while(q--){
        int x1,y1,x2,y2,x;
        cin>>x1>>y1>>x2>>y2>>x;
        insert(x1,y1,x2,y2,x);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
         a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

位运算

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

AcWing 801.二进制中1的个数

//方法一
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,a[N],x;

int main(){
    cin>>n;
    while(n--){
        cin>>x;
        int ans=0;
        while(x){
            ans+=x&1;
            x=x>>1;
        }
        cout<<ans<<" ";
    }

    return 0;
}
//方法二
#include<iostream>
using namespace std;
int lowbit(int x){
    return x&(-x);
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;

        int res=0;
        while(x) x-=lowbit(x),res++;

        cout<<res<<' ';
    }
    return 0;
}

双指针算法

AcWIng 799. 最长连续不重复子序列

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main(){
    int n,r=0;
    cin>>n;
    for(int i=0,j=0;i<n;i++){
        cin>>a[i];
        ++b[a[i]];
        while(b[a[i]]>1){
            --b[a[j++]];
        }
        r=max(r,i-j+1);
    }
    cout<<r;
    
    return 0;
}

AcWing 800. 数组元素的目标和

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,x,a[N],b[N];
int main(){
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];
    int i=0,j=m-1;
    while(a[i]+b[j]!=x&&i<n&&j>0){
        if(a[i]+b[j]>x)j--;
        else i++;
    }
    cout<<i<<" "<<j;
    return 0;
}

acwing2816. 判断子序列

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N],n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];
    int i=0,j=0;
    while(j<m){
        if(a[i]==b[j])++j,++i;
        else ++j;
    }
    if(i!=n)cout<<"No";
    else cout<<"Yes";
    return 0;
}

常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

离散化

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

AcWing 802. 区间和

区间合并

// 将所有存在交集的区间合并
void merge(vector &segs)
{
vector res;

sort(segs.begin(), segs.end());

int st = -2e9, ed = -2e9;
for (auto seg : segs)
    if (ed < seg.first)
    {
        if (st != -2e9) res.push_back({st, ed});
        st = seg.first, ed = seg.second;
    }
    else ed = max(ed, seg.second);

if (st != -2e9) res.push_back({st, ed});

segs = res;

}

AcWing 803. 区间合并

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int ,int> PII;
vector<PII>regs;
int N=100010;
void merge(vector<PII>&regs){
    vector<PII> ans;
    sort(regs.begin(),regs.end());
    int l=-2e9,r=-2e9;
    for(auto reg:regs){
        if(reg.first>r){
            if(r!=-2e9)ans.push_back({r,l});
            l=reg.first;
            r=reg.second;
        }else r=max(r,reg.second);
    }
    if(l!=-2e9)ans.push_back({l,r});
    regs=ans;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int x,c;
        cin>>x>>c;
        regs.push_back({x,c});
    }
    merge(regs);
    cout<<regs.size()<<endl;
    return 0;
}

单链表

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

AcWing 826. 单链表

双链表

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

AcWing 827. 双链表

栈 —— 模板题 AcWing 828. 模拟栈

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}

队列 —— 模板题 AcWing 829. 模拟队列

1. 普通队列：
   // hh 表示队头，tt表示队尾
   int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}
2. 循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)
{

}
单调栈 —— 模板题 AcWing 830. 单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
单调队列 —— 模板题 AcWing 154. 滑动窗口
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}

KMP —— 模板题 AcWing 831. KMP字符串

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
Trie树 —— 模板题 AcWing 835. Trie字符串统计
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
并查集 —— 模板题 AcWing 836. 合并集合, AcWing 837. 连通块中点的数量
(1)朴素并查集：

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);

(2)维护size的并查集：

int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    size[i] = 1;
}

// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

(3)维护到祖宗节点距离的并查集：

int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x)
    {
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

堆 —— 模板题 AcWing 838. 堆排序, AcWing 839. 模拟堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}

void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}

void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
一般哈希 —— 模板题 AcWing 840. 模拟散列表
(1) 拉链法
int h[N], e[N], ne[N], idx;

// 向哈希表中插入一个数
void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

// 在哈希表中查询某个数是否存在
bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;

    return false;
}

(2) 开放寻址法
int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

字符串哈希 —— 模板题 AcWing 841. 字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^{k mod 2}64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}

C++ STL简介

vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序

pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址

queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素

priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector, greater> q;

stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素

deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)

set/multiset
    insert()  插入一个数
    find()  查找一个数
    count()  返回某一个数的个数
    erase()
        (1) 输入是一个数x，删除所有x   O(k + logn)
        (2) 输入一个迭代器，删除这个迭代器
    lower_bound()/upper_bound()
        lower_bound(x)  返回大于等于x的最小的数的迭代器
        upper_bound(x)  返回大于x的最小的数的迭代器
map/multimap
    insert()  插入的数是一个pair
    erase()  输入的参数是pair或者迭代器
    find()
    []  注意multimap不支持此操作。 时间复杂度是 O(logn)
    lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]

count()  返回有多少个1

any()  判断是否至少有一个1
none()  判断是否全为0

set()  把所有位置成1
set(k, v)  将第k位变成v
reset()  把所有位变成0
flip()  等价于~
flip(k) 把第k位取反

树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a][b] 存储边a->b

(2) 邻接表：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);
树与图的遍历
时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
(1) 深度优先遍历 —— 模板题 AcWing 846. 树的重心

int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过

for (int i = h[u]; i != -1; i = ne[i])
{
    int j = e[i];
    if (!st[j]) dfs(j);
}

}
(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次

queue q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
int t = q.front();
q.pop();

for (int i = h[t]; i != -1; i = ne[i])
{
    int j = e[i];
    if (!st[j])
    {
        st[j] = true; // 表示点j已经被遍历过
        q.push(j);
    }
}

}
拓扑排序 —— 模板题 AcWing 848. 有向图的拓扑序列
时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
bool topsort()
{
int hh = 0, tt = -1;

// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
    if (!d[i])
        q[ ++ tt] = i;

while (hh <= tt)
{
    int t = q[hh ++ ];

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (-- d[j] == 0)
            q[ ++ tt] = j;
    }
}

// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;

}
朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I
时间复杂是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < n - 1; i ++ )
{
    int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
    for (int j = 1; j <= n; j ++ )
        if (!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j;

    // 用t更新其他点的距离
    for (int j = 1; j <= n; j ++ )
        dist[j] = min(dist[j], dist[t] + g[t][j]);

    st[t] = true;
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];

}
堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II
时间复杂度 O(mlogn)O(mlogn), nn 表示点数，mm 表示边数
typedef pair<int, int> PII;

int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector, greater> heap;
heap.push({0, 1}); // first存储距离，second存储节点编号

while (heap.size())
{
    auto t = heap.top();
    heap.pop();

    int ver = t.second, distance = t.first;

    if (st[ver]) continue;
    st[ver] = true;

    for (int i = h[ver]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (dist[j] > distance + w[i])
        {
            dist[j] = distance + w[i];
            heap.push({dist[j], j});
        }
    }
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];

}
Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路
时间复杂度 O(nm)O(nm), nn 表示点数，mm 表示边数
注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。

int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离

struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
    for (int j = 0; j < m; j ++ )
    {
        int a = edges[j].a, b = edges[j].b, w = edges[j].w;
        if (dist[b] > dist[a] + w)
            dist[b] = dist[a] + w;
    }
}

if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];

}
spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路
时间复杂度 平均情况下 O(m)O(m)，最坏情况下 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

queue<int> q;
q.push(1);
st[1] = true;

while (q.size())
{
    auto t = q.front();
    q.pop();

    st[t] = false;

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (dist[j] > dist[t] + w[i])
        {
            dist[j] = dist[t] + w[i];
            if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
            {
                q.push(j);
                st[j] = true;
            }
        }
    }
}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];

}
spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

queue<int> q;
for (int i = 1; i <= n; i ++ )
{
    q.push(i);
    st[i] = true;
}

while (q.size())
{
    auto t = q.front();
    q.pop();

    st[t] = false;

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (dist[j] > dist[t] + w[i])
        {
            dist[j] = dist[t] + w[i];
            cnt[j] = cnt[t] + 1;
            if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
            if (!st[j])
            {
                q.push(j);
                st[j] = true;
            }
        }
    }
}

return false;

}
floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3)O(n3), nn 表示点数
初始化：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
朴素版prim算法 —— 模板题 AcWing 858. Prim算法求最小生成树
时间复杂度是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中

// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);

int res = 0;
for (int i = 0; i < n; i ++ )
{
    int t = -1;
    for (int j = 1; j <= n; j ++ )
        if (!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j;

    if (i && dist[t] == INF) return INF;

    if (i) res += dist[t];
    st[t] = true;

    for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}

return res;

}
Kruskal算法 —— 模板题 AcWing 859. Kruskal算法求最小生成树
时间复杂度是 O(mlogm)O(mlogm), nn 表示点数，mm 表示边数
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组

struct Edge // 存储边
{
int a, b, w;

bool operator< (const Edge &W)const
{
    return w < W.w;
}

}edges[M];

int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

int kruskal()
{
sort(edges, edges + m);

for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
    int a = edges[i].a, b = edges[i].b, w = edges[i].w;

    a = find(a), b = find(b);
    if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
    {
        p[a] = b;
        res += w;
        cnt ++ ;
    }
}

if (cnt < n - 1) return INF;
return res;

}
染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图
时间复杂度是 O(n+m)O(n+m), nn 表示点数，mm 表示边数
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (color[j] == -1)
{
if (!dfs(j, !c)) return false;
}
else if (color[j] == c) return false;
}

return true;

}

bool check()
{
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!dfs(i, 0))
{
flag = false;
break;
}
return flag;
}
匈牙利算法 —— 模板题 AcWing 861. 二分图的最大匹配
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}

return false;

}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}
01背包
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int v[N], w[N];
int n, m;
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 = m; j >= v[i]; j--) {
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}

cout << f[m] << endl;

}