AcWing-周赛第96场题解

T1: AcWing 4876. 完美数

题目

如果一个正整数能够被 2520 整除，则称该数为完美数。
给定一个正整数 n，请你计算 [1,n] 范围内有多少个完美数。

输入格式

一个整数 n。

输出格式

一个整数，表示 [1,n] 范围内完美数的个数。

数据范围

前 3个测试点满足 1≤n≤3000。
所有测试点满足 1≤n≤1e18。

输入样例

输出样例

题解

#include <iostream>
using namespace std;

int main()
{
    long long n; // 会爆int(2.1 x 10 ^9)
    cin >> n;
    // 完美数的个数k,应要满足 k * 2520 <= n, 即 k <= (n / 2520) 下取整即可
    cout << n / 2520 << endl; 
    return 0;
}

T2: AcWing 4877. 最大价值

题目

有一个容量为 n 的背包和 m+1 种物品，每种物品都有无限多个。

物品种类编号为 0∼m。

第 i种物品的体积为 vi，价值为 wi。

在使用背包装入物品时，每种物品的限重如下：

第 0 种物品：重量忽略不计，在装入时没有重量限制。
第 1∼m 种物品：第 i 种物品的单个重量为 hi，如果该种物品的装入总重量超过 li，则视为超重。

现在，请你挑选物品装入背包，要求

所有装入物品的总体积不得超过背包容量。
所有存在重量限制的物品均不得超重。
满足以上所有条件的前提下，所有装入物品的总价值尽可能大。

输出总价值的最大可能值。

注意审题，不要将 n,m的含义弄混。

输入格式。

第一行包含四个整数 n,m,v0,w0。

接下来 m 行，每行包含四个整数 li,hi,vi,wi。

输出格式

一个整数，表示总价值的最大可能值。

数据范围

前 44 个测试点满足 1≤n≤100，1≤m≤2。
所有测试点满足 1≤n≤1000，1≤m≤10，1≤li,hi,vi,wi≤100。

输入样例1

1
2
3

10 2 2 1
7 3 2 100
12 3 1 10

输出样例1

输入样例2

1 2	100 1 25 50 15 5 20 10

输出样例2

题解

#include <iostream>
using namespace std;

const int N = 1010;
int n, m, v[N], w[N];
int dp[N]; // dp[j]表示背包容量为j时的最大价值
int s[N]; // 每个物品最多有s[i]个转化为多重背包问题

int main()
{
    // 数组范围10^6，完全背包+多重背包优化结合
    cin >> n >> m >> v[0] >> w[0];
    for(int i = 1; i <= m; i ++)
    {
        int l, h;
        cin >> l >> h >> v[i] >> w[i];
        s[i] = l / h;
    }
    
    // 第0种物品m0，有无限多个，完全背包问题
    for(int i = v[0]; i <= n; i ++) // 预处理第0件物品的最大价值
        dp[i] = max(dp[i], dp[i - v[0]] + w[0]); 
    
    // 第1∼m种物品，最多有(l/h)个，多重背包问题(三重for循环)
    for(int i = 1; i <= m; i ++)
        for(int j = n; j >= 1; j --)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++)
                // 该状态是从(i-1)层转移过来，需从大到小来枚举体积n
                dp[j] = max(dp[j], dp[j - k * v[i]] + k *w[i]); 
    
    cout << dp[n] << endl;
    return 0;
}