一、打包
题目链接：在算法提高里面搜！
题目要求：
Lazy有N个礼物需要打成M个包裹，邮寄给M个人，这些礼物虽然很便宜，但是很重。Lazy希望每个人得到的礼物的编号都是连续的。为了避免支付高昂的超重费，他还希望让包裹的最大重量最小。
解题思路：
这是一道二分答案的题目，我们让左边等于数组里最大的值，右边等于数组总共的和，然后check一下mid，如果true 让一个答案变量等于mid 右边等于r-1，否则左边等于l+1，重点是check函数，因为求的是m个人，让礼物价值相加，如果大于mid就算一个包裹，同时更新sum，否则就接着加，如果包裹数大于人数那就不对，否则返回true。
#include<bits/stdc++.h> using namespace std; int n,m; int a[100005]; int l,r; int ans; bool check(int k) { int t=1; int sum=a[1]; for(int i=2;i<=n;i++) { if(sum+a[i]<=k) { 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; return 0; }
二、约数个数
题目链接：都是算法提高！
题目要求：
我们用D(i)表示i有多少个约数。
例如 D(1)=1 D(2)=2 D(3)=2 D(4)=3。
给定n, 求D(1)+D(2)+D(3)+...+D(n)除以1000000007(10^9+7)的余数。
解题思路：
这道题很简单，考验我们的思维，我们只需要加上所有的n/i每次都%10...7，最后在模一次就行，因为我是算了一下 4/1=4 4/2=2 4/3=1 4/4=1 加起来是8，刚好和输出一样就提交了，然后成功过了。
#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%1000000007; } cout<<sum%1000000007; return 0; }
三、寻找三位数
题目链接：提高！！！！
题目要求：
将1，2，…，9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成1：2：3的比例，试求出所有满足条件的三个三位数。
例如：三个三位数192，384，576满足以上条件。
解题思路：
一个简单的全排列，直接暴力就能过，从123开始到329（999/3并且每个数字不同）循环，每次都判断，如果有重复数字就不输出。
#include<bits/stdc++.h> using namespace std; int a[100]; int main() { int b,c,d,e,f; for(int i=123;i<=329;i++) { memset(a,0,sizeof(a)); int flag = 1; b = 2*i; c = 3*i; d = i; e = b; f = c; while(d) { a[d%10]++; a[e%10]++; a[f%10]++; d /= 10; e /= 10; f /= 10; } for(int j=1;j<=9;j++) { if(a[j]!=1) { flag = 0; break; } } if(flag) { printf("%d %d %d\n",i,b,c); } } return 0; }
四、第二点五个不高兴的小明
题目链接：啊啊啊
题目要求：
有一条长为n的走廊，小明站在走廊的一端，每次可以跳过不超过p格，每格都有一个权值wi。
小明要从一端跳到另一端，不能回跳，正好跳t次，请问他跳过的方格的权值和最大是多少？
解题思路：
闫式dp分析
状态表示：f[i][j]
集合：跳了j步到达i的集合
属性：max
状态计算：题目样例等价于求f[n+1][t] 因为1-8格权值式12 说明从0到第n+1格 这俩权值都是0
第一个子集 跳了j-1步 到达第i-k个格子f[i-k][j-1](因为k=1 所以要加上当前i的权值)+w[i],第二个子集跳了j步到第i格，两个子集的最大值
状态转移方程：f[i][j] = max(f[i-k][j-1]+w[i],f[i][j]);
#include<bits/stdc++.h> const int INF = 1e9; using namespace std; int a[1005]; long long dp[1005][1005]; int main() { int n,p,t; cin>>n>>p>>t; for(int i=1;i<=n;i++) { cin>>a[i]; } memset(dp,128,sizeof(dp));//负无穷 for(int i=1;i<=n+1&&i<=p;i++)//最多跳p格，所以1-p格跳一步到达i格的权值便是w[i]，同时防止越界 { dp[i][1]=a[i]; } for(int i=1;i<=n+1;i++) { for(int j=2;j<=t;j++)//以2-t步跳到某格 一步能跳的已经初始化了 { for(int k=1;k<=p&&k<i;k++)//跳了1-k格而到达i { dp[i][j]=max(dp[i][j],dp[i-k][j-1]+a[i]); } } } cout<<dp[n+1][t]; return 0; }
总结
今天的题目就到这里啦，都不是难题，但是考思维，大家加油！！
