文章目录
- 第一题 AcWing 4876. 完美数
- 一、题目
- 1、原题链接
- 2、题目描述
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
- 第二题 AcWing 4877. 最大价值
- 一、题目
- 1、原题链接
- 2、题目描述
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
- 第三题 AcWing 4878. 维护数组
- 一、题目
- 1、原题链接
- 2、题目描述
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
第一题 AcWing 4876. 完美数
一、题目
1、原题链接
4876. 完美数
2、题目描述
如果一个正整数能够被 2520 整除，则称该数为完美数。
给定一个正整数 n，请你计算 [1,n] 范围内有多少个完美数。
输入格式
一个整数 n。
输出格式
一个整数，表示 [1,n] 范围内完美数的个数。
数据范围
前 3 个测试点满足 1≤n≤3000。
所有测试点满足 1≤n≤1018。输入样例：
3000输出样例：
1
二、解题报告
1、思路分析
（1）注意数据范围要开long long。
（2）因为能够被2520整除的是2520的倍数，所以当前n是2520的多少倍（下取整），即存在多少个能够被2520整除的数。
2、时间复杂度
时间复杂度为O(1)
3、代码详解
#include <iostream>
using namespace std;
typedef long long LL;
LL n;
int main()
{ cin>>n;
cout<<n/2520;
return 0;
}
第二题 AcWing 4877. 最大价值
一、题目
1、原题链接
4877. 最大价值
2、题目描述
有一个容量为 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。
输出格式
一个整数，表示总价值的最大可能值。
数据范围
前 4 个测试点满足 1≤n≤100，1≤m≤2。
所有测试点满足 1≤n≤1000，1≤m≤10，1≤li,hi,vi,wi≤100。输入样例1：
10 2 2 1 7 3 2 100 12 3 1 10输出样例1：
241输入样例2：
100 1 25 50 15 5 20 10输出样例2：
200
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
（1）装入第0个物品相当于是0-1背包问题，而装入后面物品相当于是多重背包问题（也可以直接看成多重背包问题，将第一个物品的数量设置为正无穷）。
（2）按照上述思路进行求解即可。
2、时间复杂度
时间复杂度为O(n2)
3、代码详解
法1
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int dp[N],w[N],v[N],l[N],h[N];
int n,m;
int main(){
cin>>n>>m>>v[0]>>w[0];
for(int i=1;i<=m;i++) cin>>l[i]>>h[i]>>v[i]>>w[i];
//完全背包，处理第0件物品
for(int j=v[0];j<=n;j++) dp[j]=max(dp[j],dp[j-v[0]]+w[0]);
//多重背包，处理后面物品
for(int i=1;i<=m;i++){
for(int j=n;j>=v[i];j--){
for(int k=0;k*v[i]<=j&&k<=l[i]/h[i];k++){
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
}
}
cout<<dp[n];
return 0;
}
法2
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int v[N],w[N],l[N],h[N];
int dp[N];
int n,m;
int main()
{ cin>>n>>m>>v[0]>>w[0];
l[0]=0x3f3f3f3f,h[0]=1; //初始化第0件物品可以装无限个，即l[0]/h[0]=正无穷
for(int i=1;i<=m;i++){
cin>>l[i]>>h[i]>>v[i]>>w[i];
}
//转化成多重背包问题求解
for(int i=0;i<=m;i++){
for(int j=n;j>=0;j--){
for(int k=0;k<=l[i]/h[i]&&k*v[i]<=j;k++)
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
}
cout<<dp[n];
return 0;
}
第三题 AcWing 4878. 维护数组
一、题目
1、原题链接
4878. 维护数组
2、题目描述
给定一个长度为 n 的整数序列 d1,d2,…,dn 以及三个整数 k,a,b。
初始时，所有 di 均为 0。
你需要对序列依次进行 q 次操作，操作分为以下两种：
1 x y，将 dx 增加 y。2 p，计算并输出输入格式
第一行包含 5 个整数 n,k,a,b,q。
接下来 q 行，每行描述一个操作，格式如题面所述。
输出格式
每个
2 p操作，输出一行一个整数表示结果。数据范围
前 3 个测试点满足 1≤k≤n≤10，1≤q≤10。
所有测试点满足 1≤k≤n≤2×105，1≤b<a≤10000 ，1≤q≤2×105，1≤x≤n，1≤y≤10000，1≤p≤n−k+1。输入样例1：
5 2 2 1 8 1 1 2 1 5 3 1 2 1 2 2 1 4 2 1 3 2 2 1 2 3输出样例1：
3 6 4输入样例2：
5 4 10 1 6 1 1 5 1 5 5 1 3 2 1 5 2 2 1 2 2输出样例2：
7 1
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
（1）利用两个树状数组分别维护min(d[i],b)、min(d[i],a)。
（2）
tr1[]维护min(d[i],b)：即针对每次add()操作，始终保持tr1[]维护的数组（设为B[]，每个d[i]对应B[i]，即B[]对应的树状数组为tr1[]，而且B[]中的数均小于等于b），即如果当d[x]小于b的时候需要判断d[x]+y以之后的值与b的大小关系：如果d[x]+y<=b，则保留该增值（即让对应d[x]的B[x]中的数的值B[x]+y）；如果d[x]+y>b，由于我们不能使维护的数组B[]中的数大于b，所以我们最多只能让其增加到b（即让B[x]增加它距离b的差值b-d[x]，也就是让他对应的维护的数组的值B[x]只增加到b）。如果此时d[x]>=b，我们不再需要对维护的数组B[X]进行增值操作，因为其对应的B[x]中的值已经达到b，无论对d[x]增加多少都不会影响B[x]。tr2[]维护min(d[i],a)，同理。
（3）问题所求即为：tr1[]在[1,p-1]的区间和+tr2[]在[p+k,n]的区间和。
2、时间复杂度
时间复杂度为O(nlogn)
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
const int N=200010;
typedef long long LL;
int d[N],tr1[N],tr2[N];
int n,k,a,b,q;
//lowbit运算
int lowbit(int x){
return x&-x;
}
//点更新，在tr[x]位置加c
void add(int tr[],int x,int c){
for(int i=x;i<=n;i+=lowbit(i)){
tr[i]+=c;
}
}
//求[1,x]前缀和
int query(int tr[],int x){
LL ans=0;
for(int i=x;i;i-=lowbit(i)){
ans+=tr[i];
}
return ans;
}
//求[i,j]区间和
int sum(int tr[],int i,int j){
return query(tr,j)-query(tr,i-1);
}
int main()
{ cin>>n>>k>>a>>b>>q;
while(q--){
int op;
cin>>op;
if(op==1){
int x,y;
cin>>x>>y;
if(d[x]<=b) add(tr1,x,d[x]+y>=b?b-d[x]:y); //维护min(d[i],b)
if(d[x]<=a) add(tr2,x,d[x]+y>=a?a-d[x]:y); //维护min(d[i],a)
d[x]+=y;
}
else{
int p;
cin>>p;
LL ans=sum(tr1,1,p-1)+sum(tr2,p+k,n); //求题目两个区间和
cout<<ans<<endl;
}
}
return 0;
}
