精准扶贫电商网站建设计划书,wordpress开发文档pdf,厦门同安区建设局网站,辽宁省工程新希望官网文章目录第一题 AcWing 4876. 完美数一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第二题 AcWing 4877. 最大价值一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第三题 AcWing 4878. 维护数组一、题目1、原…
文章目录第一题 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()
{ cinn; coutn/2520;return 0;
}第二题 AcWing 4877. 最大价值
一、题目
1、原题链接 4877. 最大价值 2、题目描述 有一个容量为 n 的背包和 m1 种物品每种物品都有无限多个。 物品种类编号为 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≤1001≤m≤2。 所有测试点满足 1≤n≤10001≤m≤101≤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 N1010;
int dp[N],w[N],v[N],l[N],h[N];
int n,m;
int main(){cinnmv[0]w[0];for(int i1;im;i) cinl[i]h[i]v[i]w[i];//完全背包处理第0件物品for(int jv[0];jn;j) dp[j]max(dp[j],dp[j-v[0]]w[0]);//多重背包处理后面物品for(int i1;im;i){for(int jn;jv[i];j--){for(int k0;k*v[i]jkl[i]/h[i];k){dp[j]max(dp[j],dp[j-k*v[i]]k*w[i]);}}}coutdp[n];return 0;
}法2
#include iostream
#include algorithm
using namespace std;
const int N1010;
int v[N],w[N],l[N],h[N];
int dp[N];
int n,m;
int main()
{ cinnmv[0]w[0];l[0]0x3f3f3f3f,h[0]1; //初始化第0件物品可以装无限个即l[0]/h[0]正无穷for(int i1;im;i){cinl[i]h[i]v[i]w[i];}//转化成多重背包问题求解for(int i0;im;i){for(int jn;j0;j--){for(int k0;kl[i]/h[i]k*v[i]j;k)dp[j]max(dp[j],dp[j-k*v[i]]k*w[i]); }}coutdp[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≤101≤q≤10。 所有测试点满足 1≤k≤n≤2×1051≤ba≤10000 1≤q≤2×1051≤x≤n1≤y≤100001≤p≤n−k1。 输入样例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]yb则保留该增值即让对应d[x]的B[x]中的数的值B[x]y如果d[x]yb由于我们不能使维护的数组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[]在[pk,n]的区间和。
2、时间复杂度
时间复杂度为O(nlogn)
3、代码详解
#include iostream
#include algorithm
using namespace std;
const int N200010;
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 ix;in;ilowbit(i)){tr[i]c;}
}
//求[1,x]前缀和
int query(int tr[],int x){LL ans0;for(int ix;i;i-lowbit(i)){anstr[i];}return ans;
}
//求[i,j]区间和
int sum(int tr[],int i,int j){return query(tr,j)-query(tr,i-1);
}
int main()
{ cinnkabq;while(q--){int op;cinop;if(op1){int x,y;cinxy;if(d[x]b) add(tr1,x,d[x]yb?b-d[x]:y); //维护min(d[i],b)if(d[x]a) add(tr2,x,d[x]ya?a-d[x]:y); //维护min(d[i],a)d[x]y;}else{int p;cinp;LL anssum(tr1,1,p-1)sum(tr2,pk,n); //求题目两个区间和coutansendl;} }return 0;
}
