蓝桥杯最后一题_蓝桥杯国赛二等奖有用吗

目录

1.打包

2.约数个数

3.寻找三位数

4.第二点五个不高兴的小明

1.打包

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T2978

　Lazy有N个礼物需要打成M个包裹，邮寄给M个人，这些礼物虽然很便宜，但是很重。Lazy希望每个人得到的礼物的编号都是连续的。为了避免支付高昂的超重费，他还希望让包裹的最大重量最小。

题解思路：二分查找答案,假设所有礼物的总重量为r ,所有礼物中最重的礼物为l ,那么答案只有能可能出[l,r] 这个区间内部，因为要求最大重量最小，那么当check mid 满足时，那么就将区间右端点更新为mid，否则将左端点更新为mid+1.

#include<bits/stdc++.h> using namespace std; const int N=; int a[N]; int n,m; int l,r,ans; bool check(int x) { int t=1;//包裹数量 int sum=a[1];//重量总和 for(int i=2;i<=n;i++) { if(sum+a[i]<=x)//当前包裹还没到最大值则继续添加物品 { sum+=a[i]; } else //当前包裹到达了最大值，那么包裹数量加一，进行下一个包裹的包装 { t+=1; sum=a[i]; } } if(t<=m)return true; return false; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; l=max(l,a[i]); r+=a[i]; } while(l<=r) { int mid=(l+r)/2; if(check(mid)) { ans=mid; r=mid-1; } else l=mid+1; } cout<<ans<<endl; return 0; }

2.约数个数

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T2606

 　我们用D(i)表示i有多少个约数。
　　例如 D(1)=1 D(2)=2 D(3)=2 D(4)=3。
　　给定n, 求D(1)+D(2)+D(3)+…+D(n)除以(10^9+7)的余数。

题解思路：我们考虑每个约数的贡献，约数x对总约数个数和的贡献为n/x，
换句话说1到n含约数x的有n/x个，为什么呢？
x的倍数的约数自然含x，换句话说现在就是在求n个数含多少个x的倍数，所以用n/x就行。所以我们得到了一个O(n)的算法。

#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int sum = 0; for(int i=1;i<=n;i++) { sum += n/i%; } cout<<sum%; return 0; }

3.寻找三位数

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T2038

题目要求   

将1，2，…，9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成
　　1：2：3的比例，试求出所有满足条件的三个三位数。
　　例如：三个三位数192，384，576满足以上条件。

输出格式

　　输出每行有三个数，为满足题设三位数。各行为满足要求的不同解。

题解思路：这题就是考的一个全排列，这里我用next_permutation库函数进行解答

#include<bits/stdc++.h> using namespace std; int main() { int a[9]={1,2,3,4,5,6,7,8,9}; do { int sum1=a[0]*100+a[1]*10+a[2]; int sum2=a[3]*100+a[4]*10+a[5]; int sum3=a[6]*100+a[7]*10+a[8]; if(sum2==2*sum1 && 3*sum1==sum3 && sum2/2*3==sum3) { printf("%d %d %d\n",sum1,sum2,sum3); } }while(next_permutation(a,a+9)); return 0; } 

4.第二点五个不高兴的小明

题目链接http://lx.lanqiao.cn/problem.page?gpid=T770

题目要求：

有一条长为n的走廊，小明站在走廊的一端，每次可以跳过不超过p格，每格都有一个权值wi。
　　小明要从一端跳到另一端，不能回跳，正好跳t次，请问他跳过的方格的权值和最大是多少？

题解思路：这题考察的是dp，f【i】【j】代表的是跳j次到了第i的位置，那么状态转移方程为

 f[i][j]=max(f[i][j],f[i-k][j-1]+a[i]); 

#include<bits/stdc++.h> using namespace std; const int N=1010; int a[N]; long long f[N][N]; int main() { int n,p,t; cin>>n>>p>>t; for(int i=1;i<=n;i++) { cin>>a[i]; } memset(f,-0x3f,sizeof f); for(int i=1;i<=n+1&&i<=p;i++) { f[i][1]=a[i]; } for(int i=1;i<=n+1;i++) { for(int j=2;j<=t;j++) { for(int k=1;k<i&&k<=p;k++) { f[i][j]=max(f[i][j],f[i-k][j-1]+a[i]); } } } cout<<f[n+1][t]<<endl; return 0; }

今天的文章
蓝桥杯最后一题_蓝桥杯国赛二等奖有用吗分享到此就结束了，感谢您的阅读。