题目链接

A 完美数

签到题，不要循环，记得开ll。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int main()
{
    long long n;
    cin>>n;
    cout<<n/2520<<endl;
    return 0;
}

B 最大价值

这个题是一个完全背包加多重背包的题，先对重量为0的物品做一遍完全背包，在对剩下的物品做一次多重背包即可。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main() {
    cin >> n >> m >> v >> w;
    for (int i = v; i <= n; i++)f[i] = max(f[i], f[i - v] + w);

    int l, h;
    for (int i = 1; i <= m; i++) {
        cin >> l >> h >> v >> w;
        for (int j = n; j >= v; j--) {
            for (int k = 0; k * h <= l && k * v <= j; k++) {
                f[j] = max(f[j], f[j - k * v] + k * w);
            }
        }
    }
    cout << f[n] << endl;
    return 0;
}

借鉴了其他人的题解发现也可以把所有物品重新打包，因为无限去也不能无限取，背包的容量有限制，重新打包对每一份物品取还是不取，从而转化为一个01背包的问题。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010, M = 1010;

int v[N], w[N], f[N][M];
int n, m, v0, w0;

int main() {
    cin >> n >> m >> v0 >> w0;
    int q = n / v0;
    int t = 1;
    while (q--)v[t] = v0, w[t] = w0, t++;
    while (m--) {
        int l, h, v1, w1;
        cin >> l >> h >> v1 >> w1;
        q = l / h;
        while (q--)v[t] = v1, w[t] = w1, t++;
    }
    for (int i = 1; i < t; i++) {
        for (int j = 0; j <= n; 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[t - 1][n] << endl;
    return 0;
}

C 维护数组

这是一题典型的动态求一段区间的和的题目，可以用树状数组来做，可以将整段区间分为前后两个数组，分别对两个树状数组求和即可，最后再把两个加起来就是答案，但唯一要注意的是每次修改某个数的值要和给定的值取min。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 200010;

int tr1[N], tr2[N];
int  s[N];
int n, k, a, b, q;

int lowbit(int x) {
    return x & (-x);
}

void add(int tr[],int x,int y) {
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += y;
}

int query(int tr[],int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main() {
    cin >> n >> k >> a >> b >> q;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            add(tr1, x, min(s[x] + y, b) - min(s[x], b));
            add(tr2, x, min(s[x] + y, a) - min(s[x], a));
            s[x] += y;
        } else {
            int p;
            cin >> p;
            cout << query(tr1, p - 1) + query(tr2, n) - query(tr2, p + k - 1) << endl;
        }
    }
}