菜鸟追梦旅行

这个屌丝很懒，什么也没留下！

热门标签

Acwing算法笔记

作者：菜鸟追梦旅行 | 2024-04-01 21:37:40

踩

Acwing算法笔记

持续更新中…

第一章

1.快排

#include <bits/stdc++.h>
using  namespace std;
const int N = 1e5+10;
int main() {
    int a[N];
    int n;
    cin>>n;
    for (int i = 0; i < n; i ++ ){
        cin>>a[i];
    }
    sort(a,a+n);
    for (int i = 0; i < n; i ++ ){
        cout<<a[i]<<" ";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.归并排序

#include <bits/stdc++.h>
using  namespace std;
const int N = 1e6 + 10;
int a[N], tmp[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]) 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];
}
int solve(){
    int n;
    cin>>n;
    int a[N];
    for (int i = 0; i < n; i ++ )
    cin>>a[i];
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i ++ )
    cout<<a[i]<<" ";
}
signed main(){
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

AcWing 788. 逆序对的数量 

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

#define int long long

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

int merge_sort(int l,int r){
    if(l >= r) return 0;
    
    int mid = l+r>>1;
    
    int res = merge_sort(l,mid) + merge_sort(mid+1,r);   //递归左右两部分
    
    //归并部分
    int k = 0,i = l,j = mid+1;
    while(i <= mid && j <= r)
    if(a[i] <= a[j]) tmp[k++] = a[i++]; //注意是小于等于
    else {
        tmp[k++] = a[j++];
        res+=mid-i+1;
    }
    while(i <= mid){
        tmp[k++] = a[i++];
    }
    while(j <= r){
        tmp[k++] = a[j++];
    }
    //物归原主
    for(int i = l,j = 0;i<=r;i++,j++){
        a[i] = tmp[j];
    }
    return res;
}
signed main(){
    cin>>n;
    for (int i = 0; i < n; i ++ ) cin>>a[i];
    cout<<merge_sort(0,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
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

3.整数二分

#include<bits/stdc++.h>
const int N = 1e5+10 ;
using namespace std;
int n,q;
int a[N];
int k;
void check(int x,int n){
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] < x) l = mid + 1;
            else r = mid;
        }
        if ( a[l]!= x){
            cout << "-1 -1" << endl;
            return;
        }
        int l1 = l,r1 = n;
        while (l1+1 <r1){
            int mid = l1+r1>>1;
            if(a[mid] <= x) l1 = mid;
            else r1 = mid;
        }
        ::printf("%d %d\n",l,l1);
}
int main()
{
	cin>>n>>q;
    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }
    for (int i = 0; i < q; i++) {
        cin>>k;
        check(k,n);
    }
    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

4.差分

定义：首先给定一个原数组a：a[1], a[2], a[3], a[n]；然后我们构造一个数组b ： b[1] ,b[2] , b[3], b[i];使得 a[i] = b[1] + b[2 ]+ b[3] +, + b[i]；也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。

一维差分结论：给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。
https://www.acwing.com/problem/content/description/799/

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
const int mod  = 998244353;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1,0);
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
    }
    vector<int> b(n+10,0);
    for (int i = 1; i <= n; ++i) {
        b[i] = a[i] - a[i-1];
    }
    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        b[l]+=c;
        b[r+1] -= c;
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i-1] + b[i];
        cout<<a[i]<<" ";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    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

c++库模版

binary_search:查找某个元素是否出现：binary_search(arr[],arr[]+size,indx)
lower_bound:查找第一个大于或等于某个元素的位置：lower_bound(arr[],arr[]+size,indx)
upper_bound : 查找第一个大于某个元素的位置：upper_bound(arr[] , arr[]+size , indx)

二分的记忆方法

有加必有减

int SL(int l, int r, int x) {
  while (l < r) {
    int mid = l + r >> 1;
    if (q[mid] >= x) r = mid;
    else l = mid + 1 ;
  }
  return l;
}

int SR (int l, int r, int x) {
  while (l < r) {
    int mid = l + r + 1 >> 1;//(加)
    if(q[mid] <= x) l = mid;
    else r = mid - 1;//（减）
  }
  return r;
}

作者：CPT1024
链接：https://www.acwing.com/solution/content/107848/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

## 第四章
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5.高精度

高精度加法(https://www.acwing.com/problem/content/793/)

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod  = 1e9 + 7;
vector<int> add(vector<int> &A,vector<int> &B)  // C = A + B, A >= 0, B >= 0
{
    vector<int>C;
    int t = 0;
    for (int i = 0; i < A.size() || i< B.size(); i ++ ){
        if(i < A.size()) t+=A[i];
        if(i< B.size()) t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t) C.push_back(1);
    return C;
}

void solve(){
    string a,b;
    cin>>a>>b;
    vector<int> A,B;
    for(int i = a.size() - 1;i >= 0;i --){
        A.push_back(a[i]-'0');
    }
    for(int i = b.size() - 1;i >= 0;i --){
        B.push_back(b[i]-'0');
    }
    auto C = add(A,B);
    for(int i = C.size() - 1; i >= 0;i --){
        cout << C[i];
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    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

高精度减法(https://www.acwing.com/problem/content/794/)

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod  = 1e9 + 7;
//首先判断A和B的大小
bool cmp(vector<int> &A,vector<int> &B){
    if(A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size()-1; i >= 0; i -- ){
        if(A[i] != B[i]){
            return A[i] > B[i];
        }
    }
    return true;    //  A和B相等
}
vector<int> sub(vector<int> &A,vector<int> &B)  // C = A - B, A >= 0, B >= 0
{
    vector<int> C;
    int t = 0;
    for (int i = 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;
}

void solve(){
    string a,b;
    cin>>a>>b;
    vector<int> A,B;
    for(int i = a.size() - 1;i >= 0;i --){
        A.push_back(a[i]-'0');
    }
    for(int i = b.size() - 1;i >= 0;i --){
        B.push_back(b[i]-'0');
    }
    if(cmp(A,B)){
        auto C = sub(A,B);
        for(int i = C.size() - 1; i >= 0;i --){
        cout << C[i];
        }
    }else{
        auto C = sub(B,A);
        cout << "-";
        for(int i = C.size() - 1; i >= 0;i --){
        cout << C[i];
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

高精乘低精(https://www.acwing.com/activity/content/problem/content/827/)

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod  = 1e9 + 7;
vector<int> mul(vector<int> &A,int b)  // C = A*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;
}

void solve(){
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i = a.size() - 1;i >= 0;i --){
        A.push_back(a[i]-'0');
    }
    auto C = mul(A,b);
    for(int i = C.size() - 1; i >= 0;i --){
        cout << C[i];
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    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

高精度除法(https://www.acwing.com/problem/content/796/)

高精除以低精

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod  = 1e9 + 7;
vector<int> div(vector<int> &A,int b,int &r)  // C = A/b ,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;
}

void solve(){
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i = a.size() - 1;i >= 0;i --){
        A.push_back(a[i]-'0');
    }
    int r;
    auto C = div(A,b,r);
    for(int i = C.size() - 1; i >= 0;i --){
        cout << C[i];
    }
    cout << endl<<r<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    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

第四章：数论

1.判断素数

bool isprime(int x){
    if(x < 2) return false;
    for(int i = 2;i <= x/i; ++i){
        if(x % i == 0) return false;
    }
    return true;
}
1
2
3
4
5
6
7

2.质因数分解

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void divide(){
    int a;
    cin>>a;
    for (int i = 2; i <= a/i; i ++ ){
        if(a%i == 0){
            int s = 0;
            while(a%i == 0){
            a/=i;
            s++;
           }
           cout << i << " "<< s<<endl;  //每个质因数和个数（s为个数）
        }
    }
    if(a > 1) cout << a<<" "<<1<<endl;  //唯一的大于sqrt（n）的数
    cout << endl;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        divide();
    }
}
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

3.快速幂和快速幂求逆元

p为质数：

//快速幂
/**
 * 快速的求出a^k mod p 的结果
 */
#define int long long
int qmi(int a,int b,int p){
    int res = 1;
    while(b){
        if(b&1) res= res*a%p;
        b >>=1;
        a = a*a%p;
    }
    return res;
}
//快速幂求逆元
int inv(int a,int b){
    return qmi(a,b-2,b);//费马小定理
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

**p不是质数：**原题等价于求ax + by = 1中的x, y

我们可以使用拓展欧几里得来求：

/**
 *假设a的逆元为x，那么有a * x ≡ 1 (mod p)
*等价：ax + py = 1
*exgcd(a, p, x, y)
*/
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
//x即为逆元，a与p互质时间才有逆元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.欧几里得定理和拓展欧几里得定理

欧几里得定理：求a和b的最大公约数

ll gcd(ll a,ll b){
    if(b == 0) return a;
    return gcd(b,a%b);
}
1
2
3
4

拓展欧几里得定理：

1.用于求解方程 ax+by=gcd(a,b)的解

2.求解更一般的方程 ax+by=c，当且仅当gcd(a,b)与c互质有解

3.求解一次同余方程 ax≡b(modm)，特别的当 b=1 且 a与m互质时则所求的x即为a的逆元

ll exgcd(ll a, ll b, ll &x, ll &y) {    //返回gcd并求出解（引用带回）
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;   //gcd
}
1
2
3
4
5
6
7
8
9

第五章 STL

1.map

map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。

常见用法：
begin() 返回指向map头部的迭代器
clear() 删除所有元素
empty() 判断map是否为空
end() 返回指向map末尾的迭代器
erase() 删除一个元素
find() 查找一个元素
insert() 插入元素
size() 返回map中元素的个数

使用map模拟链表

题目

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod  = 1e9 + 7;
void solve(){;
    int q;
    cin>>q;
    map<int,int> l,r;
    int op = -1e9-1,ed = 1e9+1;//使用map模拟的初始化 
    r[op] = ed;//头结点的右边为尾节点，尾节点的左边为头结点 
    l[ed] = op;
    int sz = 0;
    while (q--){
        int chk;
        cin>>chk;
        if(chk == 1){	//使用map模拟链表，l[i]代表元素i左节点，r代表元素i右节点 
            int x,y;
            cin>>x>>y;
            int ll,rr;		//插入位置的左节点和右节点 
            if(y == 0){
            	ll = op;
            	rr = r[op];
			}else{
				ll = y;
				rr = r[y];
			} 
            r[x] = rr;	//先更新插入元素的右节点 
			l[x] = ll;		//更新插入元素的左节点 
			l[rr] = x;	//更新插入元素右边元素的左节点 
			r[ll] = x;		//更新插入元素左边元素的右节点 
			 sz++;
        } else{
            int x;		//模拟链表的删除 
            cin>>x;
            int ll = l[x],rr = r[x];
            r[ll] = rr;
			l[rr] = ll;
			sz--; 
        }
    }
    cout<<sz<<endl;//输出 
    for(int i = r[op];i != end;i = r[i]){
    	cout<<i<<" ";
	} 
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    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
48
49
50
51
52
53
54
55
56
57

2.unordered_map：

unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)。
优点：因为内部实现了哈希表，因此其查找速度非常的快。
用法与map基本相同。

3.priority_queue:

优先队列，定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆（降序）
例子：

priority_queue q / priority_queue<int,vector,greater> q(升序)

还可重写functional函数，实现自定义让优先级高的排在队列前面,优先出队。

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第六章 dp

1.十一讲背包

（1）01背包

题目：01背包

这是最基础的背包问题，每种物品仅有一件，可以选择放或不放。

二维写法：

void solve(){
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i]>>w[i];
    }
    //dp[i][j]代表i个物品，背包容量为j的最大价值
    for (int i = 1; i <= n; ++i) {
        //枚举容量,最大容量为m
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = dp[i-1][j];  //首先让dp[i][j]等于i-1个物品容量为j最大价值
            if(j >= v[i]){  //判断需不需要更新，（这个物品能不能放下）
                dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]);//判断拿和不拿哪个大
            }
        }
    }
    cout<<dp[n][m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

一维写法：

void solve(){
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i]>>w[i];
    }
    //dp[i]背包容量为i的最大价值
    //需要注意的是一维度需要逆序更新，因为正序更新
    //对于第i个，可能由i-2转移，却还是使用的i-1转移，所以逆序
    for (int i = 1; i <= n; ++i) {      //枚举物品
        for (int j = m; j >= v[i]; --j) {   //从大容积向小容积枚举，注意j小于v[i]就不必更新
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);     //更新最大价值
        }
    }
    cout<<dp[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（2）完全背包

题目：完全背包

这个问题与01背包的不同就在于一个物品可以多拿，所以我们需要加一层循环，来枚举拿物品的个数，但这种二维做法是TLE的！但是优化可以去掉k层循环

二维写法：

void solve(){
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i]>>w[i];
    }
    //dp[i][j]代表i个物品，背包容量为j的最大价值
    for (int i = 1; i <= n; ++i) {
        //枚举容量,最大容量为m
        for (int j = 0; j <= m; ++j) {   //注意与01背包的差别，01背包是倒序
            //优化可以去掉k层循环
            dp[i][j] = dp[i-1][j];
            if(j >= v[i]){
                dp[i][j] = max(dp[i][j],dp[i][j-v[i]] + w[i]);//注意与01背包的差别，01背包是与dp[i-1][j - v[i]] + w[i]比
            }
        }
    }
    cout<<dp[n][m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

一维写法（优化版）：我们可以模仿01背包的一维

void solve(){
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i]>>w[i];
    }
    //dp[i]代表背包容量为i的最大价值
    for (int i = 1; i <= n; ++i) {
        //枚举容量,最大容量为m
        for (int j = v[i]; j <= m; ++j) {   //注意与01背包的差别，01背包是倒序
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]); //注意与01背包区分
        }
    }
    cout<<dp[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

（3）多重背包1

题目：多重背包

这个问题，我们可以转化为n个01背包来求解

做法：

int dp[N];
int a[N],b[N];
int n,m;
void solve(){   //注意数组的大小不要开小了
    int v,w,s;
    int t = 0;  //跟新数组下标，把n个物品全都放到一个数组中
    cin>>n>>m;
    while (n--){
        cin>>v>>w>>s;
        while (s--){
            a[++t] = v;
            b[t] = w;
        }   //拆开，把多重背包拆成一个背包;
    }
    for (int i = 1; i <= t; ++i) {  //01背包模板
        for (int j = m; j >= a[i]; --j) {
            dp[j] = max(dp[j],dp[j-a[i]] + b[i]);
        }
    }
    cout<<dp[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

（4）多重背包2

题目：多重背包

数据范围大的话，二进制优化：

int dp[N/2];
int v[N],w[N];
int n,m;
void solve(){   //注意数组的大小不要开小了
    cin>>n>>m;
    int cnt = 0;    //分组的类别
    for (int i = 1; i <= n; ++i) {
        int a,b,s;
        cin>>a>>b>>s;
        int k = 1;  //每个组的个数
        while (k <= s){
            cnt++;
            v[cnt] = a*k;   //整体体积
            w[cnt] = b*k;   //整体价值
            s -= k; //s要减小
            k *= 2;
        }
        if(s > 0){
            cnt ++;
            v[cnt]  = a*s;
            w[cnt] = b*s;
        }
    }
    n = cnt;
    //01背包模板
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= v[i]; --j) {
            dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
        }
    }
    cout<<dp[m]<<endl;
}
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

（5）多重背包3

题目：多重背包

int dp[M];
int v[N],w[N],s[N];
int g[M],q[M];
int n,m;
void solve(){   //注意数组的大小不要开小了
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i]>>w[i]>>s[i];
    }
    for (int i = 1; i <= n; ++i) {
        memcpy(g,dp,sizeof g);
        for (int r = 0; r < v[i]; ++r) {
            int hh = 0,tt = -1;
            for (int j = r; j <= m; j += v[i]) {
                while (hh <= tt && j - q[hh] > s[i]*v[i]) hh++;
                while (hh <= tt && g[q[tt]] + (j - q[tt])/v[i]*w[i] <= g[j])--tt;
                q[++tt] = j;
                dp[j] = g[q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout<<dp[m]<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

（6）混合三种背包问题

题目：混合背包

有的物品只可取一次，有的物品可取有限次，有的物品可取无限次。

对于这个问题，我们采取把01背包和完全背包转化为分组背包，在使用分组背包的二进制优化做法（转化为01背包）

int dp[N];
int v[N],w[N];
int n,m;
void solve(){   //注意数组的大小不要开小了
    cin>>n>>m;
    /**
     * 对于范围小的，我们采用转化法，将01背包和完全背包转化为多重背包
     */
     int cnt = 1;
    for (int i = 1; i <= n; ++i) {
        int a,b,s;
        cin>>a>>b>>s;
        if(s == -1){
            s = 1;
        } else if(s == 0){
            s = m/a;    //若为完全背包，则在最优情况下，只能取总体积/该物品体积向下取整
        }
        int k = 1;  //计算当前物品分为0,2,4,6.....
        while (k <= s){ //多重背包转化为01背包，二进制优化转化过程
            v[cnt] = a*k;
            w[cnt] = b*k;
            s -= k;
            k *= 2;
            cnt++;
        }
        if(s > 0){  //计算剩下的一部分
            v[cnt] = a*s;
            w[cnt] = b*s;
            cnt++;
        }
    }
    //01背包模版
    for (int i = 1; i <= cnt; ++i) {
        for (int j = m; j >= v[i]; --j) {
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
        }
    }
    cout<<dp[m]<<endl;
}
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

（7）分组背包问题

题目：分组背包

这道题和01背包差不多，直接写优化后的代码

做法：

int dp[N*2];
int v[N][N],w[N][N],s[N];
int n,m;
void solve(){   //注意数组的大小不要开小了
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>s[i];
        for (int j = 1; j <= s[i]; ++j) {
            cin>>v[i][j]>>w[i][j];
        }
    }
    //模仿01背包的写法；
/*    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {  //从大体积向小体积枚举
            dp[i][j] = dp[i-1][j];
            for (int k = 1; k <= s[i]; ++k) {
                if(j >= v[i][k]) dp[i][j] = max(dp[i][j],dp[i-1][j-v[i][k]] + w[i][k]);
            }
        }
    }*/
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= 0; --j) {  //从大体积向小体积枚举
            for (int k = 1; k <= s[i]; ++k) {
                if(j >= v[i][k]) dp[j] = max(dp[j],dp[j-v[i][k]] + w[i][k]);
            }
        }
    }
    cout<<dp[m]<<endl;
}
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

（8）二维费用的背包问题

题目：二维费用的背包问题

这个题目与01背包的区别就在于又多了一个限制条件，多了一个总重量不超过背包可承受的最大重量。

int dp[N][N];        //dp[i][j]代表容量为i，重量为j的最大价值
int v[N],w[N],x[N];
int n,m,z;
void solve(){   //注意数组的大小不要开小了
    cin>>n>>m>>z;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i]>>x[i]>>w[i];
    }
    //类似01背包，在循环里面再多加一层循环
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= v[i]; --j) {
            for (int k = z; k >= x[i]; --k) {
                dp[j][k] = max(dp[j][k],dp[j - v[i]][k - x[i]] + w[i]);
            }
        }
    }
    cout<<dp[m][z]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（9）背包问题求方案数

题目：背包问题求方案数

就是求01背包问题最优方案有多少种方案

int dp[N],cnt[N];        //dp[i]代表容量为i的最大价值,cnt[i]代表容积不超过i的最大方案数
int v[N],w[N];
int n,m;
void solve(){   //注意数组的大小不要开小了
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i]>>w[i];
    }
    //先初始化，初始什么也不装为1；
    for (int i = 0; i <= m; ++i) {
        cnt[i] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= v[i]; --j) {
            int value = dp[j-v[i]] + w[i];
            if(value > dp[j]){  //如果转移的话，cnt也跟着转移
                dp[j] = value;
                cnt[j] = cnt[j - v[i]];
            }else if(value == dp[j]){   //相等的话，cnt[j] += cnt[j-v[i]]
                cnt[j] = (cnt[j] + cnt[j-v[i]])%mod;
            }
        }
    }
    cout<<cnt[m]<<endl;
}
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

（10）背包问题求具体方案数

void solve(){   //注意数组的大小不要开小了
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i]>>w[i];
    }
    /*
     * 01背包模版求最大价值
     * 不同的是要求输出字典序最小的方案，所以我们求最大价值应当倒序
     */
    for (int i = n; i >= 1; --i) {
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = dp[i+1][j];
            if(j >= v[i]){
                dp[i][j] = max(dp[i][j],dp[i+1][j - v[i]] + w[i]);
            }
        }
    }
    /**
     * 正序求路径
     */
    for (int i = 1,j = m; i <= n; ++i) {
        if(j >= v[i] && dp[i][j] == dp[i+1][j-v[i]] + w[i]){
            path.push_back(i);
            j -= v[i];
        }
    }
    for (int i = 0; i < path.size(); ++i) {
        cout<<path[i]<<" ";
    }
    cout<<endl;
}
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

（11）01背包装满背包的情况

int dp[N];   
int v[N],w[N];
int n,m;
void solve(){   //注意数组的大小不要开小了
    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) {
            dp[j] = max(dp[j-v[i]] + w[i],dp[j]);
        }
    }
    cout<<dp[m]<<endl;
    /**
     * 类似01背包，不同的是需要初始化dp为负无穷
     */
    memset(dp,-0x3f3f3f,sizeof dp);
    //初始化为负无穷，这样如果dp[j-v[i]]不能到达，dp[j]也不能到达
    //因为dp[i-v[i]]没到达则为负无穷，负无穷加一个w[i]也为负无穷
    //需要注意的是dp[0]需要初始化为0，因为容积为0不放任何东西是合法的
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= v[i]; --j) {
            dp[j] = max(dp[j-v[i]] + w[i],dp[j]);
        }
    }
    if(dp[m] < 0){
        cout<<"0";  //不能到达体积为m
    } else{
        cout<<dp[m];
    }
    cout<<endl;
}
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<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
	int n;
	cin>>n;
	//背包dp问题
	int dp[205][80010]; //由于j可能为负数，需要偏移，40000代表0,0代表-40000

	//dp[i][j]代表i个元素使得求和结果为j的最小选择个数

	/**
	*对于i,j，第i个元素为x，那么当前元素x可以选择保持初始符号，
	*直接加进来，那么dp[i,j]从dp[i-1,j-x]转移过来，
	*也可以选择取反再加，那么dp[i,j]从dp[i-1,j+x]+1转移过来，
	*由于进行了取反操作，操作次数加一。
	*/
	memset(dp,0x3f,sizeof(dp));//初始化操作次数为无穷大
	dp[0][40000] = 0;
	for(int i = 1;i<=n;i++){
		int x = 0;
		cin>>x;
		for(int j = 0;j<=80000;j++){
            if(j-x >= 0 && j-x <= 80000) dp[i][j] = min(dp[i][j],dp[i-1][j-x]);
		    if(j+x >= 0 && j+x <= 80000) dp[i][j] = min(dp[i][j],dp[i-1][j+x] + 1);
        }
	}
	if(dp[n][40000] <= n){
		cout<<dp[n][40000];
	}else{
		cout<<"-1";
	}
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/350174

Acwing算法笔记