蓝桥31天|今天4道题Day5|C++

1.猴子分香蕉

#include<iostream>usingnamespace std;boolcheck(int num){if(num%5==1){
    num=(num-1)*4/5;if(num%5==2){
       num=(num-2)*4/5;if(num%5==3){
          num=(num-3)*4/5;if(num%5==4){
          num=(num-4)*4/5;if(num%5==0)returntrue;}}}}returnfalse;}intmain(){int ans=0;for(int i=17;;i++){if(check(i)){
       ans=i;break;}}printf("%d",ans);return0;}

2.等差数列

先把给出的n个数据从小到大排序，然后求出n-1个差，再把差排序。

• 如果最小的差为0，那么公差必然为0，即有n个数。
• 最小的差不为零，那就求所有差的最大公约数Gcd，（差最大，数列才最短）。最少元素数 =(a_max - a_min )/ Gcd+1

一开始直接用最小差值解的，虽然不对但是过了

#include<iostream>#include<vector>#include<algorithm>usingnamespace std;intmain(){int n;scanf("%d",&n);
  vector<int>num(n,0);for(int i=0;i<n;i++){scanf("%d",&num[i]);}sort(num.begin(),num.end());int d=1e5;for(int i=0;i+1<n;i++){
    d=min(d,num[i+1]-num[i]);}if(d!=0)printf("%d",(num[n-1]-num[0])/d+1);elseprintf("%d",n);return0;}

正确解法：

#include<iostream>#include<vector>#include<algorithm>usingnamespace std;intgcd(int a,int b){return b?gcd(b,a%b):a;}intmain(){int n;scanf("%d",&n);
  vector<int>num(n,0);for(int i=0;i<n;i++){scanf("%d",&num[i]);}sort(num.begin(),num.end());int d=num[1]-num[0];for(int i=1;i+1<n;i++){
    d=gcd(d,num[i+1]-num[i]);}if(d!=0)printf("%d",(num[n-1]-num[0])/d+1);elseprintf("%d",n);return0;}

3.平方序列

#include<iostream>#include<algorithm>#include<cmath>usingnamespace std;boolcheck(int x){int y2=(2*x*x-2019*2019);int y=sqrt(y2);if(y*y==2*x*x-2019*2019)returntrue;returnfalse;}intmain(){int x,y;for(int i=2020;;i++){if(check(i)){
       x=i;
       y=sqrt(2*x*x-2019*2019);break;}}printf("%d",x+y);return0;}

4.倍数问题

法一：无脑暴力解：超时

#include<iostream>#include<vector>#include<cmath>#include<algorithm>usingnamespace std;typedef pair<int,int>PII;intmain(){int n,K,ans;scanf("%d%d",&n,&K);
  vector<int>num(n,0);for(int i=0;i<n;i++){scanf("%d",&num[i]);}sort(num.begin(),num.end());for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){for(int k=j+1;k<n;k++){if((num[i]+num[j]+num[k])%K==0){
          ans=max(num[i]+num[j]+num[k],ans);}}}}printf("%d",ans);return0;}

参考y总解法

法二：dp
问题本质是组合问题求最优解–背包问题
1. 状态表示dp[i,j,k]

i表示前i个数
j表示已选择的个数
k表示当前总和%k余数

集合：从前i个数中选
属性：max

2. 状态计算
可以划分为为

• 不选择第i个数dp[i-1,j,k]
• 选第i个数dp[i-1,j-1,x] -(分为不变的第i个数的值+可以变化的里找最大的前i-1个树中选i-1个数最大值 (x+Ai)mod K=k x=(k-Ai)mod K 即选第i个数表示为dp[i-1,j-1,(k-Ai)mod K]

时间复杂度为三维dp每维最大值
N4K
=105 * 4 103
=4108
会超时

注意c++取模
正数取模是正的
负数取模是负的

• c++: -5mod3=-2
• 而一般计算中 -5mod 3=1

因此通常对x取模记为 x mod K + K

法三：
(a+b+c)%K==0和abc数值无关，只和abc分别对K的余数有关，余数相同时，只需要取最大的三个就行了

N=105 ----> 3000

i,j只会用到比自己小的进行递推，所以可以二维化一维
不太懂的可以参考
背包问题详解

#include<iostream>#include<vector>#include<cstring>#include<cmath>#include<algorithm>usingnamespace std;constint N=1e5+10;
vector<int>ans[N];int dp[4][N];intmain(){int n,K;scanf("%d%d",&n,&K);for(int i=0;i<n;i++){int x;scanf("%d",&x);
    ans[((x%K)+K)%K].push_back(x);}memset(dp,-0x3f,sizeof dp);
  dp[0][0]=0;for(int i=0;i<K;i++){sort(ans[i].begin(),ans[i].end());reverse(ans[i].begin(),ans[i].end());//找到mod K=i 最大的前三个数for(int u=0;u<3&&ans[i].size();u++){int x=ans[i][u];for(int j=3;j>=1;j--){for(int k=0;k<K;k++){//每个数选还是不选
           dp[j][k]=max(dp[j][k],dp[j-1][(k-x%K+K)%K]+x);}}}}printf("%d",dp[3][0]);return0;}