开学机试速通

本文最后更新于：几秒前

基础算法

快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void quicksort(int num[],int i,int j){
    //特判
    if(i >= j) return;
    //两端赋值,中间为基准数
    int l = i-1,r = j+1,m=num[(l+r)/2];
    //两端向中间移动，交换，使之满足基准数左边<=m,基准数右边>=m
    while(l < r){
        do l++; while(num[l]<m);
        do r--; while(num[r]>m);
        if(l < r) {
            swap(num[l], num[r]);
        }
    }
    //递归基准数两边
    quicksort(num,i,r);
    quicksort(num,r+1,j);
}

归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void mergesort(int num[],int l,int r){
    //特判
    if(l >= r)return;
    //取中间为分治点
    int m = (l+r)/2,tp[r-l+1];
    //两边递归分支
    mergesort(num,l,m);
    mergesort(num,m+1,r);
    //双指针归并
    int i = l,j = m+1,k = 0;
    while(i <= m && j <= r){
        if(num[i] < num[j]){
            tp[k] = num[i];i++;k++;
        }
        else{
            tp[k] = num[j];j++;k++;
        }
    }
    //收尾
    while(i <= m){
        tp[k] = num[i];i++;k++;
    }
    while(j <= r){
        tp[k] = num[j];j++;k++;
    }
    for(int i = 0;i < k;i++){
        num[l+i] = tp[i];
    }
}

逆序数思想：

res = mergesort(l,m) + mergesort(m+1,r)+[当num[i]>num[j]时，i到m的m-i+1个数均为j指向数的逆序数]

二分法

本质：对边界情况的讨论，如下图

image-20220831133428119

模板：

1、确定二分中间值 m=(l+r)/2 或 m=(l+r+1)/2;

2、确定check函数

3、判断，移动端点位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//红色框的右端点:小于的最大值
bool check(int m,int q){
    return num[m] < q?true:false;
}
//如果下一个值大于等于q,则l对应值就是小于的最大值
bool valid(int l,int q){
	return num[l+1] >= q?true:false;
}
int idx(int l,int r,int q){
    //判断相遇
    while(l < r){
        //确定中间值,因为l = m,所以用m=(l+r+1)/2,防止若m=r-1时，下取整会一直处在m == l的循环。
        m = l+r+1 >> 1;
        //如果在红色框内，则将左边界向右推
        if(check(m,q)) l = m;
        //否则右端点向左推，而且框内不包括m对应值
        else r = m-1;
    }
    //判断是否有效
    if(valid(l,q)) return l;
    else return -1;
}

二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

C++ 代码模板：

1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

C++ 代码模板：

1
2
3
4
5
6
7
8
9
10
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;
}

浮点数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int main(){
    double n;cin >> n;
    //确定两个边界
    double l = -10000,r = 10000,m;
    //确定最小插值
    while(r-l >= 1e-8){
        m = (l+r)/2;
        //check函数
        if(m*m*m >= n) r = m;
        else l = m;
    }
    printf("%.6f",m);
    return 0;
}

高精度算数(记成所有方法都要去除前导零)

加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N = 1e5+10;
vector<int> add(vector<int> va,vector<int> vb){
    int c=0,i=0;vector<int>res;
    //每两位相加，c是进位，i是指针
    while(i < va.size() || i < vb.size()){
        if(i < va.size()) c+=va[i];
        if(i < vb.size()) c+=vb[i];
        res.push_back(c%10);
        c /= 10;i++;
    }
    //若c仍有进位，则将其压入
    if(c)res.push_back(c);
    //前导零（其实没有也没关系）
    while(res.size()>0 && res.back()==0) res.pop_back();
    return res;
}
int main(){
    char a[N],b[N];
    scanf("%s%s",a,b);
    vector<int> va,vb;
    //倒序存储
    for(int i = strlen(a)-1;i >= 0;i--)va.push_back(a[i]-'0');
    for(int i = strlen(b)-1;i >= 0;i--)vb.push_back(b[i]-'0');
    vector<int> res = add(va,vb);
    for(int i = res.size()-1;i >= 0;i--)cout << res[i];
    return 0;
}

减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
const int N = 1e5+10;
//减法首先保证大数减小数
bool upper(vector<int> va,vector<int> vb){
    //size不一致
    if(va.size() != vb.size()) return va.size() > vb.size();
    else{
        //size一致，从高位到低位判断
        for(int i = va.size()-1;i >= 0;i--){
            if(va[i] != vb[i])return va[i]>vb[i];
        }
    }
    //相等
    return true;
}
vector<int> minus_(vector<int> va,vector<int> vb){
    vector<int> res;
    //借位和指针
    int t=0,i=0;
    while(i < va.size()){
        //t=a-t-b
        t=va[i]-t;
        if(i<vb.size())t-=vb[i];
        //余位为(t+10)%10;
        res.push_back((t+10)%10);
        t<0?t=1:t=0;i++;
    }
    //留个0
    while(res.size()>1&&res.back()==0)res.pop_back();
    return res;
}
int main(){
    char a[N],b[N];scanf("%s%s",a,b);
    vector<int> va,vb;
    for(int i = strlen(a)-1;i >= 0;i--) va.push_back(a[i]-'0');
    for(int i = strlen(b)-1;i >= 0;i--) vb.push_back(b[i]-'0');
    vector<int> res;
    if(upper(va,vb))res = minus_(va,vb);
    else res = minus_(vb,va);
    if(!upper(va,vb))cout << "-";
    for(int i = res.size()-1;i >= 0;i--)cout << res[i];
    return 0;
}

乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//大数用vector存，小数用int存
vector<int> mul(vector<int> a,int b){
    vector<int> res;
    int c=0,i=0;
    //进位(a*b+c)/10,本位(a*b+c)%10;
    while(i < a.size()){
        res.push_back((a[i]*b+c)%10);
        c = (a[i]*b+c)/10;i++;
    }
    //收尾
    if(c)res.push_back(c);
    //去除前导零，这里其实没必要去除，记成都去除一下吧
    while(res.size()>1 && res.back()==0)res.pop_back();
    return res;
}

除法（注意除法是正序处理，不用从个位开始倒序处理）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//reverse的库
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int r = 0;
vector<int> divide(vector<int> a,int b){
    vector<int> res;
    int i = 0;
    //除商：(r*10+a)/b;余数(r*10+a)%b;
    while(i < a.size()){
        res.push_back((r*10+a[i])/b);
        r = (r*10+a[i])%b;i++;
    }
    //倒过来，去除前导零
    reverse(res.begin(),res.end());
    while(res.size()>1&&res.back()==0)res.pop_back();
    return res;
}

前缀和

用于计算某个序列中一段子序列的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N = 1e5+10;
int s[N],a[N];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        //s[i]：前i个数的和，a[i]：第i个数
        s[i] = a[i]+s[i-1];
    }
    while(m--){
        int l,r;cin >> l >> r;
        cout << s[r]-s[l-1] << endl;
    }
    return 0;
}

二维前缀和：

s[i,j] = s[i,j-1]+s[i-1,j] - s[i,j]+a[i,j];

求解[x1,y1] -> [x2,y2] ：s[x2,y2]-s[x1-1,y2]-s[x2,y1-1]+s[x1-1,y1-1] //注意x1-1,y1-1

差分

构造一个数组b，使当前数组a是b的前缀和数组，我们只要有b数组，通过前缀和运算，就可以在O(n) 的时间内得到a数组 。

给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;

始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

首先让差分b数组中的 b[l] + c ,a数组变成 **a[l] + c ,a[l+1] + c,,,,,, a[n] + c;**，对a[i]及之后的元素产生影响

然后我们打个补丁，b[r+1] - c, a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdlib>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
int main(){
    int n,m;
    cin >> n >> m;a[0]=0;
    for(int i = 1;i <= n;i++){
        /*a[i]是b[i]的前缀和数组
        因为a[i] = a[i-1]+b[i]
        所以b[i] = a[i]-a[i-1]
        */
        cin >> a[i];
        b[i] = a[i]-a[i-1];
    }
    while(m--){
        int l,r,c;
        cin >> l >> r >> c;
        //b[l]+=c使a[l]到最后的元素+c
        //b[r+1]使a[r+1]到最后的元素-c
        b[l]+=c;b[r+1]-=c;
    }
    for(int i = 1;i <= n;i++){
        a[i] = a[i-1]+b[i];
        cout << a[i] << " ";
    }
    return 0;
}

双指针算法

板子：

1
2
3
4
for(int i = 0,j = 0;i < n;i++){
	while(j<i && check(i,j))j++;
	//具体逻辑		
}

不重复连续子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int c[N],f[N];
int main(){
    int n,r=0;cin >> n;
    /*
    	i指针用来遍历，j指针在i指针左边，j指向能够使从j到i的不重复连续子序列最远的点，
    */
    for(int i = 0;i < n;i++)cin >> f[i];
    for(int i = 0,j = 0;i < n;i++){
        //计数
        c[f[i]]++;
        //移动左指针，当i指向的点仍重复时，移动j指针直到i指向点不重复。
        while(c[f[i]]>1 && j<n){
            c[f[j]]--;j++;
        }
        //题目逻辑
        r = max(r,i-j+1);
    }
    cout << r;
    return 0;
}

数组元素目标和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int c[N],f[N];
int main(){
    int n,m,x;cin >> n >> m>>x;
    for(int i = 0;i < n;i++)cin >> c[i];
    for(int i = 0;i < m;i++)cin >> f[i];
    for(int i = 0,j = m-1;i < n;i++){
        while(c[i]+f[j] > x)j--;
        if(c[i]+f[j] == x){
            cout << i<< " " << j;
            break;
        }
    }
    return 0;
}

判断子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int c[N],f[N];
int main(){
    int n,m;cin >> n >> m;
    for(int i = 0;i < n;i++)cin >> c[i];
    for(int i = 0;i < m;i++)cin >> f[i];
    int cnt = 0;
    for(int i = 0,j = 0;i < n;i++){
        while(c[i]!=f[j]&&j<m){
            j++;
        }
        //cnt用于计数
        if(j < m){
            cnt++;j++;
        }
    }
    if(cnt==n)cout << "Yes";
    else cout << "No";
    return 0;
}

位运算

二进制中1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int n;cin >> n;
    for(int i = 0;i < n;i++){
        int tp,cnt=0;cin >> tp;
        while(tp){
            //循环判断
            if(tp & 1)cnt++;
            //移位操作
            tp >>= 1;
        }
        cout << cnt <<" ";
    }
    return 0;
}

离散化

特指整数、有序的离散化

特点：值域很大，但数量很少，因此可以将数值从离散映射到连续，

注意：

①原数组中可能有重复值 ——> 去重

②如何算出x映射后的值 ——>因为原数组有序，所以可以二分

过程：

1、排序，模拟数轴

2、去重 all.erase(unique(all.begin(),all.end()),all.end());

1
2
3
//去重
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());

3、对原位置的操作换成对二分之后的位置的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//理解：**将x,l,r单独压入一个vector，访问时只使用vector中的下标进行访问**
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
vector<int> alls;
vector<PII> add,query;
int a[N],s[N];
//find函数通过二分确定映射位置
int find(int q){
    int l = 0, r = alls.size()-1;
    while(l < r){
        int m = (l+r)/2;
        if(alls[m] >= q) r = m;
        else l = m+1;
    }
    return r;
}

int main(){
    int n,m;cin >> n >> m;
    //将离散的坐标x放到vector中，之后排序
    for(int i = 0;i < n;i++){
        int x,c;cin >> x >> c;
        alls.push_back(x);
        //存储需要增加的值
        add.push_back({x,c});
    }
    //将l,r也放到离散vector中
    for(int i = 0;i < m;i++){
        int l,r;cin >> l >> r;
        alls.push_back(l);
        alls.push_back(r);
        query.push_back({l,r});
    }
    //离散化处理
    //有序化
    sort(alls.begin(),alls.end());
    //去重
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    //对所有离散后的x所在坐标+=c
    for(int i = 0;i < n;i++){
        int x = find(add[i].first);
        a[x] += add[i].second;
    }
    //前缀和
    int s[N];s[0] = a[0];
    for(int i = 1;i < alls.size();i++){
        s[i] = a[i]+s[i-1];
    }
    //输出
    for(int i = 0;i < m;i++){
        int l = find(query[i].first);
        int r = find(query[i].second);
        if(!l) cout << s[r] << endl;
        else cout << s[r]-s[l-1] << endl;
    }
    return 0;
}

区间合并

左端点排序，判断两个区间之间能够存在的三种位置关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 100010,M = -1e9;
typedef pair<int,int> PII;
vector<PII> prd;
//自定义排序方法
bool cmp(const PII &a,const PII &b){
    return a.first <= b.first;
}
int main(){
    int n;cin >> n;
    for(int i = 0;i < n;i++){
        int l,r; cin >> l >> r;
        prd.push_back({l,r});
    }
    //区间左端点排序
    sort(prd.begin(),prd.end(),cmp);
    //判断区间的三种情况
    int i=1,st=prd[0].first,ed=prd[0].second,cnt=0;
    while(i < n){
        int l = prd[i].first,r = prd[i].second;i++;
        if(l <= ed && r <= ed)continue;
        else if(l <= ed && r > ed){
            ed=r;continue;
        }
        else{
            cnt++;st=l;ed=r;
        }

    }
    cout << cnt;
    return 0;
}

链表

单链表板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//默认从1开始记录
void init(){
    head=-1;idx=1;
}
//插入头结点
void add_to_head(int x){
    e[idx]=x;ne[idx]=head;head=idx;idx++;
}
//插入
void add(int k,int x){
    e[idx]=x;ne[idx]=ne[k];ne[k]=idx;idx++;
}
//删除
void remove(int k){
    ne[k] = ne[ne[k]];
}

双链表板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void init(){
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}
void add(int k,int x){
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    r[k] = idx;
    l[r[idx]] = idx;
    idx++;
}
void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

表达式求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<unordered_map>
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
stack<char> d;
stack<int> r;
//执行计算
void eval(){
    char p = d.top();d.pop();
    int b = r.top();r.pop();
    int a = r.top();r.pop();
    switch (p) {
        case '+': r.push(a+b);break;
        case '-': r.push(a-b);break;
        case '*': r.push(a*b);break;
        case '/': r.push(a/b);break;
    }
}


int main(){
    unordered_map<char,int> m = {{'+',1},{'-',1},{'*',2},{'/',2}};
    char s[N];scanf("%s",s);
    //四种情况
    for(int i = 0;i < strlen(s);i++){
        if(isdigit(s[i])){
            int num = 0;
            while(isdigit(s[i])){
                num = num*10+s[i]-'0';i++;
            }
            //记得回退一个位置
            i--;r.push(num);
        }
        else if(s[i] == '(') d.push(s[i]);
        else if(s[i] == ')'){
            while(d.top()!='(') eval();
            //注意去除'('
            d.pop();
        }
        else{
            //前缀表达式的优先级是>=
            while(d.size() && m[d.top()] >= m[s[i]])eval();
            d.push(s[i]);
        }
    }
    while(d.size()) eval();
    cout << r.top();
    return 0;
}

单调栈：左边最小的数

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

思路：保证栈内的元素保序单调上升。

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
    int n;cin >> n;
    stack<int> s;
    while(n--){
        int t;cin >> t;
        //保序单调上升
        while (!s.empty() && s.top()>=t)s.pop();
        if(s.empty())cout << "-1" << " ";
        else cout << s.top() << " ";
        s.push(t);
    }
    return 0;
}

单调队列：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int n,k;
//q数组存储元素下标所构成的队列
int num[N],q[N],fr=0,rr=-1;
void init(){
    fr = rr = 0;
    q[fr] = 0;
}
bool empty(){
    return fr == rr;
}
int main(){
    cin >> n >> k;
    for(int i = 0;i < n;i++){
        cin >> num[i];
    }
    //比如滑动窗口里有 3,-1，那么当-3进入到窗口之后，有3,-1的时候一定有-3，因此3和-1可以直接丢弃
    //因此只需要保证队列里是单调递增的，即可以以O(1)的复杂度拿到最小值
    init();
    for(int i = 0;i < n;i++){
        //移动左端点，如果fr所指的下标对应的元素不在窗口里了，则右推
        if(!empty() && q[fr]<i-k+1)fr++;
        //当右端点的值大于i的值时，队列右端点左推
        while(!empty() && num[q[rr-1]] > num[i]) rr--;
        //压入队列
        q[rr]=i;rr++;
        //输出
        if(i >= k-1) cout << num[q[fr]] << " ";
    }
    init();cout<<endl;
    for(int i = 0;i < n;i++){
        if(!empty() && q[fr]<i-k+1)fr++;
        while(!empty() && num[q[rr-1]] < num[i])rr--;
        q[rr]=i;rr++;
        if(i >= k-1) cout << num[q[fr]] << " ";
    }
    return 0;
}

并查集

合并集合

1、首先将每个数做成一个集合

2、合并的时候将p[a] = b；

三种操作：注意这里找父节点用的是find函数
1、集合合并：p[find[a]] = find[b]
2、判断是否属于同一个集合：find[a] == find[b]
3、找到父节点：p[a] = find(p[a])

并查集操作：

1
2
3
4
5
int find(int x){
    //如果不是根节点，则一直上溯，上溯到的一定是根节点，然后在这条路上的所有点的父节点都变成根节点（路径压缩）
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

DFS

排列数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 10;
int st[N],p[N],n;
void DFS(int cnt){
    if(cnt > n){
        for(int i = 1;i <= n;i++){
            cout << p[i] << " ";
        }
        cout << endl;
    }
    //st数组用于记录是否已经使用，p数组按顺序存储已经使用过的数据回溯。
    for(int i = 1;i <= n;i++){
        if(!st[i]){
            st[i]=1;p[cnt]=i;
            DFS(cnt+1);
            st[i]=0;p[cnt]=0;
        }
    }
}
int main(){
    cin >> n;
    DFS(1);
    return 0;
}

八皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//三种下棋的方向，r在迭代中有所表现
int c[N],d[M],u[M],n;
//记录下棋的方位
char s[N][N];
void dfs(int cnt){
    if(cnt > n){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                cout << s[i][j];
            }
            cout << endl;
        }
        cout << endl;
        return;
    }
    for(int i = 1;i <= n;i++){
        //注意这里的截距算法
        if(!c[i] && !d[cnt-i+n] && !u[i+cnt]){
            s[cnt][i] = 'Q';
            c[i] = d[cnt-i+n] = u[i+cnt] = 1;
            dfs(cnt+1);
            s[cnt][i] = '.';
            c[i] = d[cnt-i+n] = u[i+cnt] = 0;
        }
    }
}


int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            s[i][j] = '.';
        }
    }
    dfs(1);
    return 0;
}

BFS

走迷宫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N = 110;
typedef pair<int,int> PII;
queue<PII> q;int n,m,sum=0;
//d记录最短距离，理论上第一次到达时的距离一定是最短距离
int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0},loc[N][N],d[N][N];
void bfs(){
    memset(d,-1,sizeof d);
    d[1][1]=0;
    while(!q.empty()) {
        PII p = q.front();
        q.pop();
        int x = p.first, y = p.second;
        if (x == n && y == m) {
            cout << d[x][y];
            return;
        }
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !loc[xx][yy] && d[xx][yy]==-1) {
                q.push({xx, yy});d[xx][yy]=d[x][y]+1;
            }
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin >> loc[i][j];
        }
    }
    q.push({1,1});
    bfs();
    return 0;
}

01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N = 1010;
int v[N],w[N],f[N];
int main(){
    int n,m;cin >> n >>m;
    for(int i = 1;i <= n;i++){
        cin >> v[i] >> w[i];
    }
    //降到一维之后，原有的不选第i个物品就直接随着i的增加而自动迭代到了下一层
    //但是，如果还是从小到大进行迭代，可能f[i][j]需要f[i-1][j-v[i]]的值，但是f[i-1][j-v[i]]在前面迭代成了f[i][j-v[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;
    return 0;
}

完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
using namespace std;
const int N = 1010;

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

/*
    01背包的转移方程 f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i])
    完全背包中选择第i件物品的推导
    f[i][j] = max(f[i-1][j-v[i]]+w[i],f[i-1][j-2v[i]]+2w[i]+...)
    减一个v
    f[i][j-v[i]] = max(f[i-1][j-2v[i]]+w[i],f[i-1][j-3v[i]]+2w[i]+...)
    所以
    完全背包转移方程 f[i][j] = max(f[i-1][j],f[i][j-v[i]]+w[i])
    
    所以01背包和完全背包的区别在于选择i时的更新是从i-1更新还是从i更新
    
    所以01背包从后往前遍历，防止i-1 --> i
    而完全背包正需要将i-1 --> i，所以从前向后遍历
    
*/

int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        int a,b;
        cin >> a >> b;
        v[i] = a;
        w[i] = b;
    }
    for(int i = 1;i <= n;i++){
        //从v[i]开始
        for(int j = v[i];j <= m;j++){
            f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

多重背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N = 1010;
int v[N],w[N],s[N],f[N];
int main(){
    int n,m;cin >> n >>m;
    for(int i = 1;i <= n;i++){
        cin >> v[i] >> w[i] >> s[i];
    }
    for(int i = 1;i <= n;i++){
        for(int j = m;j >= v[i];j--){
            for(int k = 1;k <= s[i];k++){
                if(j >= k*v[i]) f[j] = max(f[j],f[j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

分组背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;
const int N = 110;

int f[N];
int v[N][N],w[N][N],s[N];

int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        cin >> s[i];
        for(int j = 0;j < s[i];j++){
            cin >> v[i][j] >> w[i][j];
        }
    }
    
    //01背包
    for(int i = 0;i < n;i++){
        for(int j = m;j >= 1;j--){
            for(int k = 0;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] << endl;
    return 0;
}

线性DP

数字金字塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
const int N = 510;
int f[N][N];
int main(){
    int n;
    cin >> n;
    int cnt=0;
    while(cnt++ < n){
        for(int i = 1;i <= cnt;i++){
            cin >> f[cnt][i];
        }
    }
    //从下向上可以解决分支问题
    for(int i = n-1;i > 0;i--){
        for(int j = 1;j <= i;j++){
            f[i][j] = max(f[i+1][j],f[i+1][j+1])+f[i][j];
        }
    }
    cout << f[1][1];
    return 0;
}

上升子序列（优化到O(nlogn)）

O(n^2)做法：第n个元素所在的上升子序列的最大值取决于倒数第二个元素是什么，找到倒数第二个元素所对应的最长子序列，然后+1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const int N = 100010;
int a[N],f[N];
//题的思路是这么来的
//数据冗余：相同的最长上升子序列，但是当前值不一样，我们期待使用更小的值而不是更大的值	，因为值越小其后面更可能有比这个数大的数
//所以定义一个数组f存储每次迭代到的最长为k的序列对应的当前位置m
//当找到一个f[i-1]<a<f[i]的时候，证明a一定是能够在i-1之后加上

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)cin >> a[i];
    int len = 0;
    //保证有一个数小于a[i]
    f[0] = -2e9;
    for(int i = 1;i <= n;i++){
        //找到一个小于a[i]的最大的f值
        //复习二分
        int l = 0,r = len;
        while(l < r){
            int mid = (l+r+1) >> 1;
            if(f[mid] < a[i]) l = mid;
            else r = mid-1;
        }
        //对应位置r+1是找到的f值对应的距离点
        //更新最大距离
        len = max(len,r+1);
        //如果f[r]<a[i]<f[r+1]，在对f[r]后面加一个a[i]一定会有f[r+1]再次变小，我们期待使用更小的数
        //所以需要更新f[r+1]
        f[r+1] = a[i];
    }
    cout << len;
    return 0;
}

最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
    分析
    状态表示 f[i][j]
            定义：表示a的前i个字符和b的前j个字符所组成的所有子序列
            属性：长度最大值
    状态计算：看成集合
            这个状态下产生不同的原因是是否有a[i]或者b[j]
            f[i][j]的计算针对于a[i],b[j]可以由以下几个部分组成：
                1、有a[i]和b[j]     if(a[i] == b[j]) f[i][j] = f[i-1][j-1]+1;
                2、没有a[i]或b[j]    f[i][j] = f[i-1][j-1]
                3、有a[i]没b[j]   f[i][j-1]表示的是a的前i个字符和b的前j-1个字符的子序列最大值，包含了当前情况
                                  而且f[i][j-1]是不超过集合f[i][j]的，即f[i][j-1]集合的最大值包含当前情况且没有出界
                                  所以可以用f[i][j-1]代替本情况
                4、有b[i]没a[i]   同上,用f[i-1][j]代替本情况
*/ 
int f[N][N];
int main(){

    int n,m;
    char a[N],b[N];
    cin >> n >> m >> a+1 >> b+1;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            f[i][j] = max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]) f[i][j] = max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout << f[n][m];

    return 0;
}

最短编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
    1、状态表示：f[i][j]
        定义：从a[1..i]到b[1..j]的操作
        属性：求操作次数最小值
    2、状态计算：（从最后的操作出发）
        对于一个f[i][j]，求解的情况有三种（注意这里，对a的删除理论上和对b的增加一致，所以只考虑对a的操作）
        a.删除   f[i][j] = f[i-1][j]+1 （从a的后面删除一个字符）
        b.增加   f[i][j] = f[i][j-1]+1 （在a的后面增加一个字符）
            最后一步是增加：若最后一步是增加，为了使a[1 ~ i] = b[1 ~ j]那最后一步增加的一定是b[j]。
            那么f[i][j]就可以看成是，首先将a[1 ~ i]转化成b[1 ~ j - 1]，这时候所操作的步骤数为f[i][j - 1]，下一步在b[j - 1]后面添加一个b[j]，那么f[i][j] = f[i][j - 1] + 1。
            也就是说，我们的转化过程为：a[1 ~ i] -> b[1 ~ j - 1] -> b[1 ~ j]，
            f[i][j]的意义是将a[1 ~ i]转化为b[1 ~ j]的步骤数，不能理解为直接在a[i]后面添加一个数，这是一个动态的变化的过程。
        c.修改   f[i][j] = if(a[i] == b[j])f[i-1][j-1]（不用改） else f[i-1][j-1]+1（加上修改操作）
*/
int main(){
    int n,m;
    char a[N],b[N];
    cin >> n >> a+1 >> m >> b+1;

    //判断一下是否需要边界条件
    //只进行增加操作
    for(int i = 0;i <= m;i++)f[0][i] = i;
    //只进行删除操作
    for(int i = 0;i <= n;i++)f[i][0] = i;

    //dp过程
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            //增加和删除
            f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
            //修改判断
            if(a[i] == b[j]) f[i][j] = min(f[i][j],f[i-1][j-1]);
            else f[i][j] = min(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout << f[n][m];
    return 0;
}

区间DP

石子合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/*
    1、集合表示f[i][j]
        定义：从第i个石子到第j个石子的所有合并情况
        属性：代价最小值
    2、集合计算
        对于一个从i到j的集合，可以从[i,i],[i+1,j] / [i,i+1],[i+2,j] / ... / [i,k],[k+1,j] / ... / [i,j-1],[j,j]这样来枚举
        即对每一个可能的合并情况进行处理
*/

int n;
int s[N],a[N],f[N][N];
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++)cin >> a[i];
    for(int i = 1;i <= n;i++)s[i] = a[i]+s[i-1];

    //长度为1时不需要合并，为0
    // for(int i = 1;i <= n;i++)f[i][i] = a[i];
    //区间dp的第一步一般为对区间长度进行枚举
    //O(n^3)的时间复杂度
    for(int len = 2;len <= n;len++){
        for(int i = 1;i + len-1 <= n;i++){
            int j = i+len-1;
            f[i][j] = 1e7;
            //转移方程
            for(int k = i;k <= j-1;k++){
                f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]);
            }
            //f[i][j] = f[i][k]+f[k][j]+s[j]-s[i-1];
            f[i][j] += s[j]-s[i-1];
        }
    }
    cout << f[1][n];
    return 0;
}

计数类DP

整数划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
/*
    1、状态表示f[i][j]：
        定义：总和为i，划分个数为j的方案
        属性：方案数量
    2、状态计算
        初始化：
        f[i][0] = 0;
        f[0][i] = 0;
        f[0][0] = 1;
        集合划分：将f[i][j]划分成方案中有1和方案中没有1
            对于方案中有1 f[i][j] = f[i-1][j-1]
            对于方案中没有1 f[i][j] = f[i-j][j]
        所以
            f[i][j] = f[i-1][j-1]+f[i-j][j]
        最后需要把所有情况加和

*/
const int N = 1010,mod = 1e9+7;
int f[N][N];
int n;
int main(){
    cin >> n;
    f[0][0] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            f[i][j] = (f[i-1][j-1]+f[i-j][j])%mod;
        } 
    }
    int r = 0;
    for(int i = 1;i <= n;i++) r = (r+f[n][i]) % mod;
    cout << r;
}

状态DP

哈密特路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const int N = 21,M = 1 << 20;
int n;
int f[M][N],w[N][N];
int main(){
    cin >> n;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            cin >> w[i][j];
        }
    }
    //因为求最小值，所以初始化每个点是无限大
    memset(f,0x3f,sizeof f);
    //从1开始走
    f[1][0] = 0;
    //从0到111...1进行状态遍历
    for(int i = 0;i < 1<<n;i++){
        //判断当前状态下是否有每个点j
        for(int j = 0;j < n;j++){  
            //如果存在j
            if(i >> j & 1){
                //则判断去掉j点之后是否含k点，有的话代表可以从k点转移到j点
                for(int k = 0;k < n;k++){
                    if(i ^ (1 << j) & k){
                        //可以转移的话则判断是否可以取到最小值
                        f[i][j] = min(f[i][j],f[i ^ (1 << j)][k]+w[k][j]);
                    } 
                }
            }
        }
    }
    cout << f[(1<<n)-1][n-1];
    return 0;
}

树形DP

没有上司的酒会

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 6010;
int h[N],e[N],ne[N],hp[N],up[N],n,idx;
int f[N][2];
void add(int a,int b){
    e[idx] = b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int n){
    //选择n点
    f[n][1] = hp[n];
    for(int i = h[n];i != -1;i = ne[i]){
        //dfs
        int d = e[i];dfs(d);
        //如果不选择n点，则d可选可不选
        f[n][0] += max(f[d][0],f[d][1]);
        //如果选择n点，则d必不选
        f[n][1] += f[d][0];
    }
}
int main(){
    //初始化
    cin >> n;memset(h,-1,sizeof h);
    for(int i = 1;i <= n;i++){
        cin >> hp[i];
    }
    for(int i = 1;i <= n-1;i++){
        int a,b;cin >> a >> b;
        up[a]=1;add(b,a);
    }
    //找到根节点
    int root=1;
    while(up[root]) root++;
    dfs(root);
    cout << max(f[root][0],f[root][1]);
    return 0;
}

记忆化路径

滑雪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstring>
using namespace std;
const int N = 310;
int n,m;
int f[N][N];
int h[N][N];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int dp(int x,int y){
    if(f[x][y]) return f[x][y];//如果已经记录过了，就不用再算了 
    f[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];//到下一个点 
        int yy=y+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&h[x][y]>h[xx][yy])//点在范围内，且此点高度，比刚才的点矮就滑过去 
        {
            f[x][y]=max(f[x][y],dp(xx,yy)+1);//比较大小，取出最大的 
        }                                       //+1，是因为如果到从两个点的滑雪距离一样的话，再滑一步，就滑到x，y这个点了，所以+1 
    }
    return f[x][y];//返回最终值 
}

int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin >> h[i][j];
        }
    }
    int r = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            r = max(r,dp(i,j));
        }
    }
    cout << r;
    return 0;
}

区间问题

区间选点/最大不相交区间数量

右排序->判断左端点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
vector<PII> v;
bool cmp(PII a,PII b){
    return a.second <= b.second;
}
int main(){
    int n;cin >> n;
    for(int i =0;i < n;i++){
        int l,r;cin >> l >> r;
        v.push_back({l,r});
    }
    sort(v.begin(),v.end(),cmp);
    int r = -2e9,sum = 0;
    for(int i = 0;i < n;i++){
        int l = v[i].first;
        if(r < l){
            sum++;r = v[i].second;
        }
    }
    cout << sum;
    return 0;
}

区间分组

左端点排序->小根堆存储每个分组的最右端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
vector<PII> v;
bool cmp(PII a,PII b){
    return a.first <= b.first;
}
int main(){
    int n;cin >> n;
    for(int i = 0;i < n;i++){
        int l,r;cin >> l >> r;
        v.push_back({l,r});
    }
    sort(v.begin(),v.end(),cmp);
    priority_queue<int,vector<int>,greater<int>> q;
    int sum;
    for(int i = 0;i < n;i++){
        int l = v[i].first,r = v[i].second;
        if(q.empty() || q.top() >= l){
            sum++;q.push(r);
        }
        else{
            q.pop();q.push(r);
        }
    }
    cout << sum;
    return 0;
}

区间覆盖

左端点排序->寻找最远的右端点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
vector<PII> v;
bool cmp(PII a,PII b){
    return a.first <= b.first;
}
int main(){
    int s,t;cin >> s >> t;
    int n;cin >> n;
    for(int i = 0;i < n;i++){
        int l,r;cin >> l >> r;
        v.push_back({l,r});
    }
    sort(v.begin(),v.end(),cmp);
    int ss = -2e9;int sum = 0;bool c = false;
    for(int i = 0;i < n;i++){
        int r=-2e9,j=i;
        for(;j < n;j++){
            if(v[j].first <= s){
                r = max(r,v[j].second);
            }
            else break;
        }
        if(r < s)break;sum++;
        if(r >= t){
            c=true;break;
        }
        s=r;i=j-1;
    }
    if(c)cout << sum;
    else cout << "-1";
    return 0;
}

总结

区间选点问题：右排序，优先选择最右点

区间分组问题：左排序，如果最小分组的max_r都大于当前区间的l，则代表区间与所有分组有冲突，新开一组

区间覆盖问题：左排序，如果l<s，则找到其符合条件区间的最右端点并更新成s，注意判断断点和结束点

绝对值不等式

货仓选址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N = 100010;
int f[N];
int main(){
    cin >> n;
    
    for(int i = 0;i < n;i++)cin >> f[i];
    sort(f,f+n);
    int r = 0;
    int m = n/2;
    for(int i = 0;i < n;i++){
        r += abs(f[i]-f[m]);
    }
    cout << r;
    return 0;
}
学习笔记
#机试
开学机试速通
http://paopao0226.site/post/bf1e6b0b.html
作者
Ywj226
发布于
2022年8月28日
更新于
2023年9月23日
许可协议