[算法课]全面翻新计划！第二周全解

文章目录

• ​​上课内容​​

• ​​试题A: 组队​​

• ​​数据​​
• ​​详细分析​​
• ​​颜老板版本 暴力枚举​​
• ​​吐槽​​
• ​​更新版​​

• ​​思路​​
• ​​枚举版本​​
• ​​思路​​
• ​​dfs版本​​
• ​​思路​​
• ​​贪心版本​​
• ​​DP版本​​

• ​​测试数据​​

• ​​试题C: 数列求值​​

• ​​分析​​
• ​​方法1​​
• ​​颜老板版本​​
• ​​数组版本​​

• ​​报错:Compiler exceeded OUTPUT limit 内容容量：20190324*(sizeof int)/1024/1024=77M​​

• ​​颜老板版本​​
• ​​思路​​
• ​​更新版​​

• ​​作业部分​​

• ​​注意----所有人做这2个题目的时候，使用2种方法，其中一种必须用枚举书写！​​
• ​​数列求和​​

• ​​算法标签:枚举​​
• ​​题目描述​​
• ​​思路​​
• ​​AC代码​​
• ​​枚举​​
• ​​递归​​

• ​​等差数列​​

• ​​算法标签: 数论最大公约数​​
• ​​题目描述​​
• ​​思路​​
• ​​C++ 代码​​
• ​​AC代码​​

• ​​gcd​​

• ​​枚举​​
• ​​注意​​
• ​​差不多AC代码​​
• ​​枚举​​

上课内容

试题A: 组队

本题总分：5 分
【问题描述】
作为篮球队教练，你需要从以下名单中选出1 号位至5 号位各一名球员，
组成球队的首发阵容。
每位球员担任1 号位至5 号位时的评分如下表所示。请你计算首发阵容1
号位至5 号位的评分之和最大可能是多少？

编号1 号位2 号位3 号位4 号位5 号位

数据

1 97 90 0 0 0
2 92 85 96 0 0
3 0 0 0 0 93
4 0 0 0 80 86
5 89 83 97 0 0
6 82 86 0 0 0
7 0 0 0 87 90
8 0 97 96 0 0
9 0 0 89 0 0
10 95 99 0 0 0
11 0 0 96 97 0
12 0 0 0 93 98
13 94 91 0 0 0
14 0 83 87 0 0
15 0 0 98 97 98
16 0 0 0 93 86
17 98 83 99 98 81
18 93 87 92 96 98
19 0 0 0 89 92
20 0 99 96 95 81

不懂这道题。不看篮球比赛。 不看。

详细分析

1号位 2号位 3号位 4号位 5号位
控卫 分位 小前 大前 中锋
宫城 三井寿 流川枫 樱木 赤木

有人拿了省赛一等奖二等奖。

硬凑

结果还是错的！

￣□￣｜｜

首先想到的是二维数组

颜老板版本 暴力枚举

#include<stdio.h>

int main()
{
  int fen[20][5]={
          97,90,0,0,0
          ,92,85,96,0,0
          ,0,0,0,0,93
          ,0,0,0,80,86
          ,89,83,97,0,0
          ,82,86,0,0,0
          ,0,0,0,87,90
          ,0,97,96,0,0
          ,0,0,89,0,0
          ,95,99,0,0,0
          ,0,0,96,97,0
          ,0,0,0,93,98
          ,94,91,0,0,0
          ,0,83,87,0,0
          ,0,0,98,97,98
          ,0,0,0,93,86
          ,98,83,99,98,81
          ,93,87,92,96,98
          ,0,0,0,89,92
          ,0,99,96,95,81  
          };
  int s,a,b,c,d,e,result[5],max,i;
  max=0;
  for(a=0;a<=19;a++)//1号位共20位选手的遍历
  for(b=0;b<=19;b++)//2号位共20位选手的遍历
  for(c=0;c<=19;c++)//3号位共20位选手的遍历
  for(d=0;d<=19;d++)//4号位共20位选手的遍历
  for(e=0;e<=19;e++)//5号位共20位选手的遍历
  {
    s=fen[a][0]+fen[b][1]+fen[c][2]+fen[d][3]+fen[e][4];
    if(max<s)
    if(a!=b && a!=c && a!=d && a!=e)
    if(b!=c && b!=d && b!=e)
    if(c!=d && c!=e)
    if(d!=e)
    {
      max=s;
      result[0]=a+1;
      result[1]=b+1;
      result[2]=c+1;
      result[3]=d+1;
      result[4]=e+1;
    }     
  }
  
  printf("总分最高的组合分数是%d\n",max);
  for(i=0;i<=4;i++)
    printf("%d号位置是选手%d，分值是%d\n",i+1,result[i],fen[result[i]-1][i]);
  
  return 0;
}

吐槽

1.首先固定数组没有卵用，光是手打写入就能给写死，不如直接读取
2.其次这里的枚举思路应用太狭窄了，还好只有五个位子，否则没法这么写
3.这里手写用S读取和，但是完全没有必要，大可判重之后直接进行更新
4.比较大小之后进行了存储位子，但是没必要，我们可以直接更新和，毕竟答案也不要位置
5.太长了，应用范围太狭窄了，说老实话看到选位子还是很容易想到dfs

更新版

思路

优化上述部分问题，总的来说只是但单纯的压缩了一下代码量，但是思路仍然一脉相承

枚举版本

#include<iostream>

using namespace std;

const int row = 20,col=5;
int fen[row+5][col+5];

int main()
{
    for(int i=0;i<row;i++)for(int j=0;j<col;j++)cin>>fen[i][j];
    
    int res=0;
    for(int a=0;a<20;a++)
        for(int b=0;b<20;b++)
            for(int c=0;c<20;c++)
                for(int d=0;d<20;d++)
                    for(int e=0;e<20;e++)
                        {
                            if(a!=b&&a!=c&&a!=d&&a!=e&&b!=c&&b!=d&&b!=e&&c!=d&&c!=e&&d!=e)
                            res=max(res,fen[a][0]+fen[b][1]+fen[c][2]+fen[d][3]+fen[e][4]);
                        }
    cout<<res;
    return 0;
}

思路

这类选位子的题目很明显是dfs的思路，

dfs版本

#include<iostream>

using namespace std;

const int row = 20,col=5;
int fen[row+5][col+5];
bool st[col];

void dfs(int u,int tmpS,int &sum)
{
    if(u==col){sum = max(sum,tmpS);return ;}
    
    else 
    {
        for(int i=0;i<row;i++)
        {
            if(!st[i])
            {
                st[i]=true;
                dfs(u+1,tmpS+fen[i][u],sum);
                st[i]=false;
            }
        }
    }
    
}

int main()
{
    for(int i=0;i<row;i++)for(int j=0;j<col;j++)cin>>fen[i][j];
    
    int res=0;
    dfs(0,0,res);
    
    cout<<res;
    return 0;
}

思路

这里的贪心思路很明显是直接取掉最大值，但我们仍然需要注意判重，即选取一个人之后就无法再次选取这个人

注意：
这里答案虽然对了，但是这样的做法并不正确，只是在这个数据上正确而已
因为我们a[][0]优先选择最大，并且给了判重，而你无法判定这个选择是否只有当前这个位子上最大
我们也可以理解为局部最优并非全局最优？

贪心版本

#include<iostream>
#include<algorithm>

using namespace std;

const int row = 20,col=5;
int fen[row+5][col+5];
bool st[row];//判重数组
int res;
int jIdx;//用来记录需要判重的位子，即当前选择的人是第几个人

int max(int a,int b,int idx)//自定义max函数，方便判断b>a时进行操作
{
    if(a>b){return a;}
    jIdx=idx;//记录当前位子
    return b;
}

void func()
{
    for(int i=0;i<col;i++)//当col过完之后，表示五个人都被选择完毕
    {
        jIdx=0;
        int tmp=-0x3f3f3f;
        for(int j=0;j<row;j++)
            if(!st[j])tmp = max(tmp,fen[j][i],j);//如果没选择当前这个人，更新最大值，记录这个人的位置
        
        st[jIdx]=true;//选择
        res+=tmp;//求和
        //cout<<jIdx<<" "<<i<<" "<<fen[jIdx][i]<<endl;//输出当前被选择的人员
    }
}

int main()
{
    for(int i=0;i<row;i++)for(int j=0;j<col;j++)cin>>fen[i][j];
    
    func();
    
    cout<<res;//输出答案
    return 0;
}

DP版本

暂时不会 但是我们似乎可以从多重背包问题的角度入手

测试数据

97 90 0 0 0
92 85 96 0 0
0 0 0 0 93
0 0 0 80 86
89 83 97 0 0
82 86 0 0 0
0 0 0 87 90
0 97 96 0 0
0 0 89 0 0
95 99 0 0 0
0 0 96 97 0
0 0 0 93 98
94 91 0 0 0
0 83 87 0 0
0 0 98 97 98
0 0 0 93 86
98 83 99 98 81
93 87 92 96 98
0 0 0 89 92
0 99 96 95 81

试题C: 数列求值

本题总分：10 分
【问题描述】
给定数列1, 1, 1, 3, 5, 9, 17, …，从第4 项开始，每项都是前3 项的和。求
第20190324 项的最后4 位数字。

分析

fibonacci数列！也有求前40项。

该问题所涉及到项数的结果可能非常大，计算机是不能直接表示的。就算能表示，那误差！

方法1

注意求：最后4 位数字!

1234+5678=6912

6912+7899=14811

14811+8899=23710

注意：对每次求解的结果取后4位数值，在进行运算。如果要取后4位数值，对10000取余数。

1234+5678=6912

6912+7899=4811

4811+8899=3710

颜老板版本

#include<stdio.h>

int f(int a,int b,int c)
{
  int i;
  i=3;  //已有3个数值
  while(1)
  {
    i++;
    a=(a+b+c)%10000;  //3个为一组，第4个作为新数值存放对象用a来存储
    if(i==20190324)
      return a;
    i++;
    b=(a+b+c)%10000;  //3个为一组，第5个作为新数值存放对象用b来存储
    if(i==20190324)
      return b;
    i++;
    c=(a+b+c)%10000;  //3个为一组，第6个作为新数值存放对象用c来存储
    if(i==20190324)
      return c;
  }
}

int main()
{
  int a,b,c,d;
  a=b=c=1;
  d=f(a,b,c);
  printf("%d\n",d);
  return 0;
}

注意： 上述算法最大的特点是a b c变量的重复使用。目的节约存储空间。

分析该程序中 f函数  时间复杂度是多少？ o(n)

分析该程序中 f函数  空间复杂度是多少？ o(1)
  
  判断空间复杂度的依据是？  临时变量。 int i;

数组版本

报错:Compiler exceeded OUTPUT limit 内容容量：20190324*(sizeof int)/1024/1024=77M

#include<iostream>

using namespace std;

const int N=20190324;
int a[N]={1,1,1};
int main()
{
    for(int i=3;i<=N;i++)a[i]=(a[i-1]+a[i-2]+a[i-3])%10000;
    
    cout<<a[N];
    
    return 0;
}

颜老板版本

#include<stdio.h>

int f(int a,int b,int c)
{
  int i;
  i=3;  //已有3个数值
  while(1)
  {
    i++;
    a=(a+b+c)%10000;  //3个为一组，第4个作为新数值存放对象用a来存储
    if(i==20190324)
      return a;
    i++;
    b=(a+b+c)%10000;  //3个为一组，第5个作为新数值存放对象用b来存储
    if(i==20190324)
      return b;
    i++;
    c=(a+b+c)%10000;  //3个为一组，第6个作为新数值存放对象用c来存储
    if(i==20190324)
      return c;
  }
}

int main()
{
  int a,b,c,d;
  a=b=c=1;
  d=f(a,b,c);
  printf("%d\n",d);
  return 0;
}

思路

数组无法开的过大，因此话不多说我们需要减少数组的量
我们可以直接用四个数组，然后模拟每次循环++时候数组滚动的变化即可

更新版

#include<iostream>

using namespace std;

const int n = 20190324,len=1e4;
int arr[]={0,1,1,1};

int main()
{
    for(int i=4;i<=n;i++)
    {
        arr[4]=(arr[3]+arr[2]+arr[1])%len;
        for(int j=1;j<=3;j++)arr[j]=arr[j+1];//模拟数组滚动变化
    }
    
    cout<<arr[4];
    
    return 0;
}

作业部分

注意----所有人做这2个题目的时候，使用2种方法，其中一种必须用枚举书写！

试题F: 特别数的和
时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分
【问题描述】
小明对数位中含有2、0、1、9 的数字很感兴趣（不包括前导0），在1 到
40 中这样的数包括1、2、9、10 至32、39 和40，共28 个，他们的和是574。
请问，在1 到n 中，所有这样的数的和是多少？

数列求和

时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分
【问题描述】
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一
部分的数列，只记得其中N 个整数。
现在给出这N 个整数，小明想知道包含这N 个整数的最短的等差数列有
几项？
【输入格式】
输入的第一行包含一个整数N。
第二行包含N 个整数A1; A2; ; AN。(注意A1 AN 并不一定是按等差数
列中的顺序给出)
【输出格式】
输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】
10
【样例说明】
包含2、6、4、10、20 的最短的等差数列是2、4、6、8、10、12、14、16、
18、20。

算法标签:枚举

题目描述

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

输入格式

共一行，包含一个整数 n。

输出格式
共一行，包含一个整数，表示满足条件的数的和。

数据范围

1≤n≤10000

输入样例：

40

输出样例：

574

思路

我们现在求得是​​在 1 到 n 中，所有这样的数的和是多少​​ 由于数据小，我们只需要暴力枚举，然后每个数递归判断就可以了。

AC代码

枚举

#include<iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    
    int res=0,x=0;
    for(int i=1;i<=n;i++)
        {
            x=i;
            while(x)
                {
                    int t=x%10;
                    if(t==2||t==0||t==9||t==1)//一个数满足就计算一次
                        {
                            res+=i;
                            break;
                        }
                    x/=10;
                }
        }
    cout<<res;
    return 0;
}

递归

#include<iostream>

int n,res;
void check(int x,int u)
{
    if(!x)return ;
    if(x%10==2||x%10==0||x%10==9||x%10==1){res+=u;return;}
    check(x/10,u);
}
int main()
{
    while(std::cin>>n,n){int k=n;check(n--,k);}
    std::cout<<res;
    return 0;
}

等差数列

算法标签: 数论最大公约数

题目描述

数学老师给小明出了一道等差数列求和的题目。

但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入格式
输入的第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1∼AN 并不一定是按等差数
列中的顺序给出)

输出格式
输出一个整数表示答案。

数据范围

2≤N≤100000,
0≤Ai≤109

输入样例：

5
2 6 4 10 20

输出样例：

10

样例解释
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。

思路

已知​​给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项​​​ 该数列为等差数列，求等差数列最短。
我们已知等差数列求N公式为​​(a(n)-a(0))/d+1​​，即等差数列 队尾减队头的差 除以 公差 +1；
由此我们知道，本题根本不需要其余的队列数字，现在的问题转为，如何使得队伍从小到大排序
以及为​​(a(n)-a(0))/d+1​​如何才能最短。

我们可以轻松的通过sort函数排序。
而使得 ​​​(a(n)-a(0))/d+1​​最小则需要使得 公差最大。

由此，最后一步，我们只需要通过辗转相除法求得最大d，即可通过等差公式求得答案。

C++ 代码

AC代码

gcd

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1e5+10;
int a[N];

int gcd(int a,int b)//辗转相除法 在两个数中求得最大公约数，当一方为0时，返回另一方。
{
    return b?gcd(b,a%b):a;
}

int main()  
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    
    sort(a,a+n);//回复等差数列正常排序
    
    int d=0;
    for(int i=1;i<n;i++)d=gcd(d,a[i]-a[0]);//求得数列中的最大公约数，又因为辗转相除，所以gcd(a,b)中a,b任意一个为零时，可以返回另一个数，再和下一个数求最大公约数。
    
    if(d)cout<<(a[n-1]-a[0])/d+1;//特判d为0！即有常数个，否则出现K/d时d==0逻辑错误Float Point Exception   
    else cout<<n;
    
    return 0;
}

枚举

注意

数据过到如下大小出现TML，且存在​​4 2 5 7 10​​出问题的情况，但是骗分差不多够了。

100000 510735260 430427260 325696180 181874000 301759672 306932452 305279052 55941608 280950452 184132072 751002624 577721580 334194656 113777540 379200204 242109724 150227924 199239424 11427356 855625052 575553264 979653672 782662872 138044728 533084504 320962732 196466436 253485116 129664352 138531300 32973520 535413436 885268152 699714156 697300192 801516356 880152060 685844492 630937440 146949468 268181480 811805228 629737544 123986104 599182712 301155000 515785216 565835996 917249632 924118328 676542936 998393780 374343932 282995944 395190944 862531540 346344784 241046824 209518848 849805084 5361740 708467728 666391060 563143316 316559964 210354996 935659060 8961428 828556532 836289720 103290260 269159348 37900652 666669776 660226240 97772628 679939492 518728268 243286000 552372596 587448296 377414532 196041276 148276912 337147156 607572536 386980632 778921464 893185576 106644300 310853372 656413972 247121888 790414956 321907532 985209096 798653612 740647616 285154812 45785008 336202356 884724892 344034748 718874700 183749428 499879508 583659648 883340760 7260788 339835112 18168504 606537980 210047936 996428596 649540552 550752264 811980016 365954108 17426836 114977436 164347960 816661500 965680080 816637880 87190868 924226980 421461108 263929880 215234888 245161428 867515360 806519072 319526636 617837788 261511192 335318968 405843564 863792848 143226956 955452620 526173292 301443164 686321616 915256104 398837872 664543976 60396340 328105420 515114408 90039440 410175472 551021532 177041348 23742824 705557744 690752728 546798276 86789328 501471496 491995152 46044828 261171064 466792612 865895028 586045268 234839488 628428996 401757304 97744284 187429424 476396504 577315316 574173856 332470396 59016932 989125292 482594392 525681996 991005444 399447268 228759700 570512756 761286772 934600884 355065288 906134060 560625424 725252100 260396328 433790748 503356372 726244140 495188576 769426224 948848468 445525164 819656516 831749956 600401504 990755072 884762684 16...

如果我们要保证正确性，则需要加check，但明显复杂度上天。
如果我们要压缩时间而不用gcd，应该还是数论的方向走。
本次仅为班级作业而言，我就不做过多强求。

差不多AC代码

枚举

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int cnt; int n;
int stepNum;

void check(int k)
{
    int step = 0, num = a[0];
    while (num < a[n - 1])//小于等差数列最大值
        step++, num += k;//项+1，数量加等差

    if (num == a[n - 1])b[cnt++] = step, stepNum++;//如果最后一项相等，则表明正确
}

int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++)scanf("%d",&a[i]);
    sort(a, a + n);
    

    int min_a_d=a[1]-a[0];
    for(int i=2;i<n;i++)
        min_a_d=min(min_a_d,a[i]-a[i-1]);//找最小公差
    
    for (int i = 1; i <= min_a_d; i++)check(i);//判断是否存在比最小公差小但是符合条件的情况

    sort(b, b + stepNum);
    
    printf("%d",b[0]+1);//输出多个情况中项最少的那一类
    return 0;
}