算法竞赛入门【码蹄集新手村600题】（MT1401-1450）

---

@TOC

---

前言

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

---

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。

目录

1. MT1401 归并排序

（1）题目描述
输入10个整型元素，对数组进行归并排序，输出从小到大排序后的新数组。

格式

输入格式: 输入整型，空格分隔。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式: 9 8 5 0 4 2 1 5 7 1
.
输出格式: 0 1 1 2 4 5 5 7 8 9

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int a[100];
    for(int i=0;i<10;i++) cin>>a[i];
    sort(a,a+10);
    for(int i=0;i<10;i++) cout<<a[i]<<" ";
    return 0;
}

---

2. MT1402 长方体

（1）题目描述
输入10个整型元素，对数组进行归并排序，输出从小到大排序后的新数组。

格式

输入格式: 输入整型，空格分隔。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式: 9 8 5 0 4 2 1 5 7 1
.
输出格式: 0 1 1 2 4 5 5 7 8 9

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int a[100];
    for(int i=0;i<10;i++) cin>>a[i];
    sort(a,a+10);
    for(int i=0;i<10;i++) cout<<a[i]<<" ";
    return 0;
}

---

3. MT1403 后3位排序

（1）题目描述
输入10个正整数，且每个数均在1000至9999之间。要求按每个数的后3位进行升序排列，如果后三位相等，则按原4位数进行降序排列，输出排序后的结果。

格式

输入格式: 输入为整型，空格分隔。
.
输出格式: 输出为整型，空格分隔。

样例1

输入格式: 1234 1011 1214 1123 2435 1341 3453 9214 3431 1969
.
输出格式: 1011 1123 9214 1214 1234 1341 3431 2435 3453 1969

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

void ReBubbleSort(int arr[],int len){
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            if((arr[j]%1000>arr[j+1]%1000)||
            (arr[j]%1000 == arr[j+1]%1000 && arr[j]<arr[j+1]))
                swap(arr[j],arr[j+1]);
        }
    }
}

bool cmp(int a,int b){
    if((a%1000 < b%1000) || (a%1000 == b%1000 && a>b)) return true;
    return false;

}

int main( )
{
    int a[10],len=10;
    for(int i=0;i<len;i++) cin>>a[i];
    ReBubbleSort(a,len);
    for(int i=0;i<len;i++) cout<<a[i]<<" ";
    return 0;
}

---

4. MT1404 大大小小排序

（1）题目描述
输入10个整型元素和整数N，M，对数组进行小到大排序，再把下标N到M的元素从大到小排序并输出新数组。

格式

输入格式: 第一行输入整型数组，第二行输入N，M，空格分隔。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式:
9 8 5 0 4 2 1 5 7 1
2 4
.
输出格式: 0 1 4 2 1 5 5 7 8 9

备注：

0<=N<M<=9

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;
int dp[100];

bool cmp(int a,int b){
    return a>b;
}
int main( )
{
    int n,m;
    for(int i=0;i<=9;i++) cin>>dp[i];
    cin>>n>>m;
    sort(dp,dp+10);
    sort(dp+n,dp+m+1,cmp);
    for(int i=0;i<=9;i++) cout<<dp[i]<<" ";
    cout<<endl;
    return 0;
}

---

5. MT1405 大大小小排序II

（1）题目描述
输入10个整型元素和整数N，对数组进行小到大排序，再从指定位置N开始按逆序重新排列并输出新数组。

格式

输入格式: 第一行输入整型数组，第二行输入N，空格分隔。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式:
9 8 5 0 4 2 1 5 7 1
2
.
输出格式: 0 1 9 8 7 5 5 4 2 1

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;
int dp[100];

bool cmp(int a,int b){
    return a>b;
}
int main( )
{
    int n;
    for(int i=0;i<=9;i++) cin>>dp[i];
    cin>>n;
    sort(dp,dp+10);
    sort(dp+n,dp+10,cmp);
    for(int i=0;i<=9;i++) cout<<dp[i]<<" ";
    cout<<endl;
    return 0;
}

---

6. MT1406 数字重排

（1）题目描述
输入3个自然数(0~9)，把这些数字重新排列组合，组成一个三位数，按从小到大的次序排序放到数组中，最后输出所有的3位数。

格式

输入格式: 输入整型，空格分隔。
.
输出格式: 输出整型，一种组合一行

样例1

输入格式: 1 2 3
.
输出格式:
123
132
213
231
312
321

备注：

注意:输入的数字有可能相同，在输出时要进行去重

（2）参考代码

import java.util.Scanner;
import java.util.*;

class Main {

   public static void main(String[] args) {

      Scanner input = new Scanner(System.in);
      int a = input.nextInt();
      int b = input.nextInt();
      int c = input.nextInt();
      Set<Integer> ans = new TreeSet<>(Comparator.naturalOrder());
      ans.add(a*100+b*10+c);
      ans.add(a*100+c*10+b);
      ans.add(b*100+a*10+c);
      ans.add(b*100+c*10+a);
      ans.add(c*100+b*10+a);
      ans.add(c*100+a*10+b);
      for(Integer tmp:ans){
         if(tmp>=100){
            System.out.println(tmp);
         }
      }
      input.close();
   }
}

---

7. MT1407 插入

（1）题目描述
输入10个整型元素和一个整数N，对数组进行从小到大排序，然后插入N，不改变原有的次序，输出插入后的新数组。

格式

输入格式: 第一行输入整型数组元素，空格分隔，第二行输入N。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式:
9 8 5 0 4 2 1 5 7 1
3
.
输出格式: 0 1 1 2 3 4 5 5 7 8 9

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,a[15];
    for(int i=0;i<10;i++) cin>>a[i];
    cin>>n;
    a[10]=n;
    sort(a,a+11);
    for(int i=0;i<11;i++) cout<<a[i]<<" ";
    return 0;
}

---

8. MT1408 插入

（1）题目描述
在整型有序数组中插入一个元素。

格式

输入格式: 第一行输入数组元素个数N，第二行输入元素，第三行是要插入的数，全部为整型，如样例所示。
.
输出格式: 输出为整型。

样例1

输入格式:
5
1 2 3 6 9
7
.
输出格式: 1 2 3 6 7 9

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,a[1000],m;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>m;
    a[n]=m;
    sort(a,a+n+1);
    for(int i=0;i<n+1;i++) cout<<a[i]<<" ";
    return 0;
}

---

9. MT1409 顺时针旋转数组

（1）题目描述
给定一个含有N个元素的数组，按顺时钟方向将数组旋转M次，每次旋转一个位置。输出新数组。

格式

输入格式: 第一行输入数组长度N和M，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式:
6 1
1 2 3 4 5 6
.
输出格式: 6 1 2 3 4 5

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

void xuanzhuan(int a[],int n,int m){
    int b[1000];
    for(int i=0;i<m;i++){
        //第一个和最后一个换
        b[0] = a[n-1];
        //剩下的后移
        for(int i=0;i<n-1;i++){
            b[i+1] = a[i];
        }
        for(int i=0;i<n;i++) a[i]=b[i];
    }
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
}

int main( )
{
    int n,m,a[1000];
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    xuanzhuan(a, n, m);
    return 0;
}

---

10. MT1410 逆时针旋转数组

（1）题目描述
给定一个含有N个元素的数组，按逆时钟方向将数组旋转M次，每次旋转一个位置。输出新数组。

格式

输入格式: 第一行输入数组长度N和M，第二行输入数组元素，整型，空格分隔。
.
输出格式:输出整型，空格分隔。

样例1

输入格式:
6 1
1 2 3 4 5 6
.
输出格式: 2 3 4 5 6 1

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

void xuanzhuan(int a[],int n,int m){
    int b[1000];
    for(int i=0;i<m;i++){
        //第一个和最后一个换
        b[n-1] = a[0];
        //剩下的前移
        for(int i=n-2;i>=0;i--){
            b[i] = a[i+1];
        }
        for(int i=0;i<n;i++) a[i]=b[i];
    }
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
}

int main( )
{
    int n,m,a[1000];
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    xuanzhuan(a, n, m);
    return 0;
}

---

11. MT1411 旋转数组

（1）题目描述
请编写一个简单程序，输入10个整型元素和整数N([-10,10])，比如-3，表示向左旋转数组3次，比如3，表示向右旋转数组3次，0表示不旋转，输出旋转后的数组。

格式

输入格式: 第一行输入整型元素，空格分隔，第二行输入N。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式:
9 8 5 0 4 2 1 5 7 1
3
.
输出格式: 5 7 1 9 8 5 0 4 2 1

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

void zuoxuanzhuan(int a[],int n,int m){
    int b[1000];
    for(int i=0;i<m;i++){
        //第一个和最后一个换
        b[n-1] = a[0];
        //剩下的前移
        for(int i=n-2;i>=0;i--){
            b[i] = a[i+1];
        }
        for(int i=0;i<n;i++) a[i]=b[i];
    }
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
}

void youxuanzhuan(int a[],int n,int m){
    int b[1000];
    for(int i=0;i<m;i++){
        //第一个和最后一个换
        b[0] = a[n-1];
        //剩下的后移
        for(int i=0;i<n-1;i++){
            b[i+1] = a[i];
        }
        for(int i=0;i<n;i++) a[i]=b[i];
    }
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
}

int main( )
{
    int n=10,m,a[1000];
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>m;
    if(m<0){
        m=-m;
        zuoxuanzhuan(a, n, m);
    }else if(m>0) youxuanzhuan(a,n,m);
    else if(m==0){
        for(int i=0;i<n;i++) cout<<a[i]<<" ";
    }
    return 0;
}

---

12. MT1412 合并

（1）题目描述
编写函数将两个整型有序数组A和B，合并成一个数组C，合并后保持原有的有序性。

格式

输入格式: 第一行输入A和B数组元素个数N，M为整型，第二，三行分别输入A和B数组元素，如样例所示。
.
输出格式: 输出数组C，如样例所示。

样例1

输入格式:
4 5
1 4 6 8
0 1 1 2 3
.
输出格式: 0 1 1 1 2 3 4 6 8

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,m,a[1000],b[1000],c[2000];
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];
    for(int i=0;i<(m+n);i++){
        if(i<n) c[i]=a[i];
        else c[i] = b[i-n];
    }
    sort(c,c+m+n);
    for(int i=0;i<(m+n);i++) cout<<c[i]<<" ";
    return 0;
}

---

13. MT1413 并集

（1）题目描述
第一行输入数组长度N和M(都<100)，后两行分别输入AB数组元素，全部整型，空格分隔。

格式

输入格式: 第一行输入数组长度N和M(都<100)，后两行分别输入AB数组元素，全部整型，空格分隔。
.
输出格式: 输出整型

样例1

输入格式:
6 2
15 35 1 32 14 16
15 2
.
输出格式: 7

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,m,a[1000],b[1000],c[2000],cnt=0;
    bool flag=true;
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(b[i]==a[j]){
                flag=false;
                break;
            }
        }
        if(flag){
            c[n+cnt]=b[i];
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}

---

14. MT1414 数组的交集

（1）题目描述
给定大小分别为N和M的两个数组A和B，输入正整数N和M,输出两个数组的交集(或公共元素)的总数。(交集中相同元素只会出现一次或者重复的元素只统计—次)

格式

输入格式:
第一行输入正整数N和M(均小于100)
后两行分别输入数组A和B的元素，整型，空格分隔。
.
输出格式: 输出整型

样例1

输入格式:
6 5
1 2 3 4 5 6
3 4 7 8 9
.
输出格式: 2

（2）参考代码

import java.util.*;

class Main {

   public static void main(String[] args) {

      Scanner input = new Scanner(System.in);
      int n = input.nextInt();
      int m = input.nextInt();
      Set<Integer> a = new HashSet<>();
      Set<Integer> b = new HashSet<>();
      Set<Integer> ans = new HashSet<>();
      for(int i=0;i<n;i++){
         a.add(input.nextInt());
      }
      for(int i=0;i<m;i++){
         b.add(input.nextInt());
      }
      ans.addAll(a);
      ans.retainAll(b);
      System.out.println(ans.size());
      input.close();
   }
}

---

15. MT1415 大小相同

（1）题目描述
给定一个由N(<10)个正整数组成的数组A，生成一些最小元素和最大元素相同的子数组数（可以仅包含1个元素)，统计这些子数组的数量并输出。

注:最大元素和最小元素相同就是数组中的元素全部为同一个值。如数组(1,1)，它满足条件的子数组有三个，分别为(1) 、 (1) 、(1,1)

格式

输入格式: 第一行输入数组长度N，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型

样例1

输入格式:
3
1 1 3
.
输出格式: 4

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int a[10]={0};
    bool iscount[10] = {0};
    int n,num=0;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        if(iscount[i] == true) continue;
        int count = 1;
        for(int j=i+1;j<10;j++)
            if(a[i]==a[j]){
                count++;
                iscount[j]=true;
            }
        num += pow(2,count)-1;
    }
    cout<<num;
    return 0;
}

---

16. MT1416 最长子数组

（1）题目描述
整数数组大小为N (<100)，找出最多包含整数K个偶数元素的最长子数组(子数组为原数组的前x(0<x<=N)个元素)，输出子数组的长度。

格式

输入格式: 第一行输入数组长度N和整数K，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型

样例1

输入格式:
7 2
1 2 3 4 5 6 7
.
输出格式: 5

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

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

    int count=0;
    for(int i=0;i<N;i++){
        if(a[i]%2==0) count++;
        if(count==K+1){
            printf("%d",i);
            return 0;
        }
    }
    printf("%d",N);
    return 0;
}

---

17. MT1417 连续子序列

（1）题目描述
给定一个正数数组，数组中有N (<100）个元素，找出元素乘积小于等于给定数M的可能连续连续子序列(子数组)的数目。输出这个数。如果子数组中只有一个元素，乘积就等于这个元素。

格式

输入格式: 第一行输入数组长度N和M，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型

样例1

输入格式:
4 10
1 2 3 4
.
输出格式: 7

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,m;
    int a[100];
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d ",&a[i]);
    int num=0;
    for(int i=0; i<n; ++i){
        int product = 1;
        for(int j=i;j<n;++j){
            product *= a[j];
            if(product <=m) num++;
            else break;
        }
    }
    cout<<num;
    return 0;
}

---

小结(一)

经典范例：
1.排序算法系列：MT1400-1407

1. 旋转数组：MT1411
2. 并交集：MT1413-1414
3. 大小相同：MT1415
4. 最长子数组：MT1416
5. 连续子序列：MT1417

---

18. MT1418 元素和

（1）题目描述
定义一个长度为n的整型数组，输入n个数组元素的值，然后输出数组元素和。

格式

输入格式: 输入整型,分2行输入。第一行输入n，第二行输入n个数组元素的值，空格分隔
.
输出格式: 输出整型

样例1

输入格式:
10
1 2 3 4 5 6 7 8 9 10
.
输出格式: 55

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,sum=0;;
    cin>>n;
    int a[1000];
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    cout<<sum;
    return 0;
}

---

19. MT1419 数组最值

（1）题目描述
定义一个长度为n的整型数组，输入n个数组元素的值，然后输出数组最大值和最小值。

格式

输入格式: 输入整型，分2行输入。第一行输入n，第二行输入n个数组元素的值，空格分隔
.
输出格式: 输出整型，空格分隔

样例1

输入格式:
10
1 2 3 4 5 6 7 8 9 10
.
输出格式: 10 1

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,max1=0,min1;
    cin>>n;
    int a[1000];
    for(int i=0;i<n;i++){
        cin>>a[i];       
    }
    min1=a[0];
    for(int i=0;i<n;i++){
        max1=max(a[i],max1);
        min1=min(a[i],min1);
    }
    cout<<max1<<" "<<min1;
    return 0;
}

---

20. MT1420 中值

（1）题目描述
给定由N个整数组成的数组A，计算中值并输出。注意，中值不是平均值。如果有奇数个元素，那么中值是按从小到大排列后中间的那个元素的值，如果有偶数个元素，中值是按从小到大排列后中间的那两个元素的平均值(向下取整)。

格式

输入格式: 第一行输入数组长度N(<100)，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型

样例1

输入格式:
4
53 70 33 89
.
输出格式: 61

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,a[105];
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int avg;
    if(n%2==1) avg=a[(n+1)/2];
    else avg=floor((a[n/2]+a[n/2+1])/2);
    cout<<avg;
    return 0;
}

---

21. MT1421 异或

（1）题目描述
给定一个由N(<1000)个整数组成的数组，把数组元素任意两两进行异或，统计数组中异或的结果为奇数的元素有几对，输出对数。

格式

输入格式: 第一行输入数组长度N，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型

样例1

输入格式:
3
1 2 3
.
输出格式: 2

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,number[1000];
    cin>>n;
    for(int i=0;i<n;i++) cin>>number[i];
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if((number[i]^number[j])%2!=0) ans++;
        }
    }
    cout<<ans;
    return 0;
}

---

22. MT1422 总位数

（1）题目描述

计算数组中N个元素所有数字的总位数。所有元素均为非负数。

格式

输入格式: 第一行输入数组长度N (<100)，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型

样例1

输入格式:
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14
.
输出格式: 19

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,a[1005],len,cnt=0;
    string s;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        s = to_string(a[i]);
        len = s.size();
        cnt+=len;
    }
    cout<<cnt<<endl; 
    return 0;
}

---

23. MT1423 被3整除

（1）题目描述
给定一个长度为N的整数数组，找出是否有可能使用这些数字的所有数字构造一个整数，使其可以被3整除。如果可能则输出YES否则输出NO。比如数组arr ={40，50,90}，则可以构造405090，可以被3整除。但如果arr = {1，4}，则只能构造14或者41，都不能被3整除。

不考虑负数或者其他特殊情况。

格式

输入格式: 输入为整型，第一行是N(<100)，第二行是数组元素。
.
输出格式: 能则输出YES否则输出NO

样例1

输入格式:
3
40 50 90
.
输出格式: YES

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    cin>>n;
    int a[1005],x=0;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        while(a[i]){
            x += a[i]%10;
            a[i] /= 10;
        }
    }
    if(x%3==0) printf("YES\n");
    else cout<<"NO"<<endl;
    return 0;
}

---

24. MT1424 卡特兰数序列

（1）题目描述
卡特兰数序列是1，1，2，5，14，42，132，429，1430，4862...输入正整数N(<20)，输出第N个卡特兰数字。注:N从O开始计数。

格式

输入格式: 输入正整数N
.
输出格式: 输出整型

样例1

输入格式: 7
.
输出格式: 429

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    cin>>n;
    int a[20];
    a[0] = 1;
    for(int i=1;i<20;i++) a[i] = (4*i-2)*a[i-1]/(i+1);
    cout<<a[n];
    return 0;
}

---

25. MT1425 小码哥的序列

（1）题目描述
小码哥正在学习序列，这个系列是1，2，5，8，15，28，51...给他一个数字N,他必须找到该级数的N项。

格式

输入格式: 输入正整数N
.
输出格式: 输出整型

样例1

输入格式: 8
.
输出格式: 94

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,rec[1005];
    cin>>n;
    rec[1]=1,rec[2]=2,rec[3]=5,rec[4]=8;
    for(int i=5;i<=n;i++) 
        rec[i] = 2*rec[i-1]-rec[i-4];
    cout<<rec[n];
    return 0;
}

---

26. MT1426 普洛尼克数

（1）题目描述
普洛尼克数是两个连续非负整数积，即n(n+1)，输入正整数N输出所有小于或等于N的普洛尼克数。

格式

输入格式: 输入正整数N
.
输出格式: 输出整型，空格分隔

样例1

输入格式: 30
.
输出格式: 0 2 6 12 20 30

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,div=0,i=0;
    cin>>n;
    while(1){
        div=i*(i+1);
        if(div>n){
            break;
        }
        cout<<div<<" ";
        i++;
    }
    return 0;
}

---

27. MT1427 素数序列

（1）题目描述
输入正整数N(<10000)，找到这个序列的第N个数:2，3，5，7，22，23，...等等这个序列的数字，其每位数字都是素数，即2、3、5、7。

格式

输入格式: 输入正整数N
.
输出格式: 输出整型

样例1

输入格式: 21
.
输出格式: 222

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

bool bitPrime(int n){
    while(n){
        int i=n%10;
        if(i!=2&&i!=3&&i!=5&&i!=7) return false;
        n/=10;
    }
    return true;
}
int main( )
{
    int n;
    cin>>n;
    int a[10000],count=0;
    for(int i=2;count<n;i++)
        if(bitPrime(i)) a[count++]=i;
    cout<<a[count-1]<<endl;
    return 0;
}

---

28. MT1428 最小素数因子

（1）题目描述
给定一个含有N(<1000)个元素的数组，他们依次为1，2，3...N，输出所有元素的最小素数因子。整数N的最小素数因子是它的因子中最小的素数。注:所有偶数的最小素数因子为2，素数是它自己的最小素数因子，1的为1。

格式

输入格式: 输入正整数N
.
输出格式: 输出整型，空格分隔

样例1

输入格式: 6
.
输出格式: 1 2 3 2 5 2

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int miniP(int n){
    if(n==1) return 1;
    for(int i=2;i<=n;i++){
        if(n%i==0) return i;
    }
}

int main( )
{
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++) 
        printf("%d ",miniP(i));
    return 0;
}

---

29. MT1429 最小正整数

（1）题目描述
给定一个N个数的数组。找到一个特殊的最小正整数K，用K构成一个新数组，新数组中所有的元素都是K，要求:这个新数组的所有元素的乘积大于初始数组的所有元素的乘积。输出K。

格式

输入格式: 第一行输入数组长度N (<100)，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型

样例1

输入格式:
5
4 2 1 10 6
.
输出格式: 4

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int N,a[100]={0};
    scanf("%d",&N);
    int product=1;
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
        product *= a[i];
    }

    for(int i=1;;i++){
        int j=pow(i,N);
        if(j>product){
            printf("%d",i);
            return 0;
        }
    }
    return 0;
}

---

30. MT1430 回文数组

（1）题目描述
有一个长度为N(<100）的数组，数组元素依次为1，2，3...N，统计数组中所有小于N的回文数，输出总数。回文数是指正序(从左向右)和倒序(从右向左)读都是—样的整数。注意，所有的个位数都可以看成回文数。

格式

输入格式: 输入正整型N
.
输出格式: 输出整型

样例1

输入格式: 104
.
输出格式: 19

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

bool isHuiwen(int n){
    int temp=n,newn=0;
    while(temp>0){
        newn = newn*10 + temp%10;
        temp /=10;
    }
    if(newn == n) return true;
    else return false;
}

int main( )
{
    int n;
    cin>>n;
    int count=0;
    for(int i=1;i<n;i++)
        if(isHuiwen(i)) count++;
    cout<<count;
    return 0;
}

---

31. MT1431 和数组

（1）题目描述
给定一个大小为N的数组A，构造一个大小相同的数组B，使B[i]等于A中除A[i]之外的所有元素的和。输出B。

格式

输入格式: 第一行输入数组长度N，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式:
5
3 6 4 8 9
.
输出格式: 27 24 26 22 21

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int A[100],B[100],N,sum=0;
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&A[i]);
        sum+=A[i];
    }
    for(int i=0;i<N;i++){
        B[i] = sum - A[i];
        printf("%d ",B[i]);
    }
    return 0;
}

---

32. MT1432 数组赋值

（1）题目描述
有两个含N个整型元素的数组，从键盘输入A数组所有元素，将其——“赋值”给B数组对应的元素，最后输出A数组下标为奇数的元素和B数组下标为偶数的元素。

格式

输入格式: 第一行输入数组长度N，第二行输入数组元素，整型，空格分隔。
.
输出格式: 第一行输出A数组指定元素，第二行输出B数组指定元素。

样例1

输入格式:
5
1 2 3 4 5
.
输出格式:
2 4
1 3 5

备注：

N>0
当N=1时，直接输出唯一元素。

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int A[100]={0},B[100]={0},N;
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&A[i]);
    }
    for(int i=0;i<N;i++){
        B[i] = A[i];
    }

    if(N==1){
        printf("%d ",B[0]);
        return 0;
    }

    for(int i=1;i<N;i=i+2) printf("%d ",A[i]);
    printf("\n");
    for(int i=0;i<N;i=i+2) printf("%d ",B[i]);
    return 0;
}

---

33. MT1433 小码哥打车

（1）题目描述
给定一个大小为N的数组arr[]，其中每个元素都在0到N-1的范围内。重新排列给定数组，使arr[i]变为arr[arr[i]]。比如arr[]= {4,0,2,1,3}，则arr[arr[0]] = arr[4]= 3, arr[arr[1]] = arr[0] = 4。输出新数组。

不考虑不合理的输入等特殊情况。

格式

输入格式: 第一行输入数组长度N，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式:
5
4 0 2 1 3
.
输出格式: 3 4 2 0 1

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,arr[10005];
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<n;i++) cout<<arr[arr[i]]<<" ";
    cout<<endl;
    return 0;
}

---

34. MT1434 找数字

（1）题目描述
输入一个字符串(包含26个英文字母大小写及﹒空格，不含其他字符)，把其中连续的数字作为一个整数，依次存放到一个数组中，输出这些整数的和。

格式

输入格式: 输入字符串
.
输出格式: 输出整型

样例1

输入格式: a123.456 jmk32kk
.
输出格式: 611

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    string s;
    getline(cin,s);
    int tmp=0,sum=0;
    for(int i=0;i<s.length();i++){
        if(s[i]<='9'&& s[i]>='0'){
            int t=s[i]-'0';
            tmp=tmp*10+t;
        }else{
            sum+=tmp;
            tmp=0;
        }
    }
    sum+=tmp;
    cout<<sum;
    return 0;
}

---

## 小结(二)
经典例题

1. 异或：MT1421
2. 卡特兰序列：MT1424
3. 找规律：MT1425-1432

---

35. MT1435 分玩具

（1）题目描述
有N个盒子，里面装着数量不等的玩具，分给N个宝宝，确保第i个宝宝分到i个玩具，这样宝贝们才不会哭闹。判断玩具是否足够且刚好分配，输出YES或者NO。

格式

输入格式: 第一行输入数组长度N(<100)，第二行依次输入每个盒子的玩具数量，整型，空格分隔。
.
输出格式: 输出YES或者NO

样例1

输入格式:
5
7 4 1 1 2
.
输出格式: YES

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,a[105],sum=0,res=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) sum+=i;
    for(int i=1;i<=n;i++) res+=a[i];
    if(sum==res) cout<<"YES";
    else cout<<"NO";
    return 0;
}

---

36. MT1436 不给糖就捣蛋

（1）题目描述
万圣节到了，缅因大街上每一家都给孩子们准备了糖果。小码哥去街上讨糖。小码哥是个有个性有原则的孩子，他从不拿相邻两家人的糖果，比如他从第一家取了糖果，他就会跳过第二家，去第3家或者更后面的人家去取糖果。

请问，小码哥一晚上最多可以获得多少糖果。依次输入每一家的糖果数量，输出最多获得的糖果。不考虑负数或者其他特殊情况。(假定房子数量和每家糖果数量都不超过100)

格式

输入格式: 输入为非负整数，空格分隔，假设这条街至多100家店。
.
输出格式: 输出为整型

样例1

输入格式: 1 2 3 1
.
输出格式: 4

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int d[100];
    int t,n=0;
    while(cin>>t) d[n++]=t;
    int s[100];
    s[0]=d[0];
    s[1]=d[1];
    for(int i=2;i<n;i++) s[i]=max(s[i-2]+d[i],s[i-1]);
    cout<<s[n-1];
    return 0;
}

---

37. MT1437 对角线

（1）题目描述
编写程序遍历n (< 100）阶方阵主对角线的元素。

格式

输入格式: 第一行输入n为整型，后n行输入元素，如样例所示。
.
输出格式: 输出为整型，空格分隔。

样例1

输入格式:
3
1 1 1
1 2 1
1 1 1
.
输出格式: 1 2 1

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    cin>>n;
    int a[100][100];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    for(int i=0;i<n;i++) cout<<a[i][i]<<" ";
    return 0;
}

---

38. MT1438 次对角线

（1）题目描述
编写程序遍历n (<100)阶方阵次对角线的元素。

格式

输入格式: 第一行输入n为整型，后n行输入元素，如样例所示。
.
输出格式: 输出为整型，空格分隔。

样例1

输入格式:
3
1 1 1
1 2 1
3 1 1
.
输出格式: 1 2 3

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    cin>>n;
    int a[100][100];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    int j=0;
    for(int i=0;i<n;i++){
        for(j=n-i-1;j>=0;j--){
            cout<<a[i][j]<<" ";
            break;
        }
    }
    return 0;
}

---

39. MT1439 对角线差

（1）题目描述
编写程序遍历n (<100)阶方阵对角线的元素，分别计算主对角线元素和与次对角线元素和，再输出两者的差值。

格式

输入格式: 第一行输入n为整型，后n行输入元素，如样例所示。
.
输出格式: 输出为整型

样例1

输入格式:
3
1 1 2
1 2 1
3 1 1
.
输出格式: -3

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    cin>>n;
    int a[100][100];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    //主对角线
    int sum1=0;
    for(int i=0;i<n;i++){
        sum1+=a[i][i];
    }

    //此对角线
    int sum2=0;
    int j=0;
    for(int i=0;i<n;i++){
        for(j=n-i-1;j>=0;j--){
            sum2+=a[i][j];
            break;
        }
    }
    cout<<sum1-sum2;
    return 0;
}

---

40. MT1440 右上角

（1）题目描述
输入3X3整型数组，所有元素在0到9之间，然后输出右上角所有元素。

格式

输入格式: 输入整型，如样例所示。
.
输出格式: 输出整型，如样例所示。

样例1

输入格式:
1 2 3
4 5 6
7 8 9
.
输出格式:
1 2 3
5 6

9

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n=3;
    int a[100][100];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    //右上角
    for(int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           if(j>=i) cout<<a[i][j]<<" ";
           else cout<<" "<<" ";
       }
       cout<<endl;
    }
    return 0;
}

---

41. MT1441 右下角

（1）题目描述
输入3X3整型数组，所有元素在0到9之间，然后输出右下角所有元素。
格式

输入格式: 输入整型，如样例所示。
.
输出格式: 输出整型，如样例所示。

样例1

输入格式:
1 2 3
4 5 6
7 8 9
.
输出格式:
3
5 6
7 8 9

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n=3;
    int a[100][100];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    //右下角
    for(int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           if((j<=1&&i<1)||(j<1&&i<=1)) cout<<" "<<" ";
           else cout<<a[i][j]<<" ";
       }
       cout<<endl;
    }
    return 0;
}

---

42. MT1442 左上角

（1）题目描述
输入3X3的整型数组，输出左上角。

格式

输入格式: 输入数组，元素在0到9之间，空格分隔。
.
输出格式:输出数组，空格分隔。

样例1

输入格式: 1 2 3 4 5 6 7 8 9
.
输出格式:
1 2 3
4 5
7

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n=3;
    int a[100][100];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    //右下角
    for(int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           if((j==2&&i>=1)||(j>=1&&i==2)) cout<<" "<<" ";
           else cout<<a[i][j]<<" ";
       }
       cout<<endl;
    }
    return 0;
}

---

43. MT1443 行最值

（1）题目描述
N (<100）阶方阵中，每行都有最大的数，求这N个最大数中最小的一个。

格式

输入格式: 第一行输入N为整型，第二行输入元素，如样例所示。
.
输出格式: 输出为整型

样例1

输入格式:
3
1 1 1
1 2 1
3 1 1
.
输出格式: 1

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int a[100][100],n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) 
            scanf("%d",&a[i][j]);
    }
    int temp[100];
    for(int i=0;i<n;i++){
        temp[i]=a[i][0];
        for(int j=1;j<n;j++)
            temp[i]=max(temp[i],a[i][j]);
    }

    int temp2 = temp[0];
    for(int i=1;i<n;i++) temp2 = min(temp2,temp[i]);
    cout<<temp2;
    return 0;
}

---

44. MT1444 列最值

（1）题目描述
N (<100)阶方阵中，每列都有最小的数，求这N个最小数中最大的一个。

格式

输入格式: 第一行输入N为整型，第二行输入元素，如样例所示。
.
输出格式: 输出为整型。

样例1

输入格式:
3
1 1 1
1 2 1
3 1 1
.
输出格式: 1

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int a[100][100],n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) 
            scanf("%d",&a[i][j]);
    }
    int temp[100];
    for(int i=0;i<n;i++){
        temp[i]=a[0][i];
        for(int j=1;j<n;j++)
            temp[i]=min(temp[i],a[j][i]);
    }

    int temp2 = temp[0];
    for(int i=1;i<n;i++) temp2 = max(temp2,temp[i]);
    cout<<temp2;
    return 0;
}

---

45. MT1445 奇偶差

（1）题目描述
输入一个M×N的正整数数组，统计奇数和偶数的个数，输出他们的差值。不考虑非法输入等特殊情况。

格式

输入格式: 第一行输入M和N(都<100)，第二行输入数组元素，空格分隔。
.
输出格式: 输出奇数总数减去偶数总数的差，整型，如样例所示。

样例1

输入格式:
3 2
8 9 5 4 1 7
.
输出格式: 4-2=2

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int m,n,a[100][100],odd=0;
    scanf("%d%d",&m,&n);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a[i][j]);
            if(a[i][j]%2) odd++;
        }
    }
    printf("%d-%d=%d",odd,m*n-odd,odd-(m*n-odd));
    return 0;
}

---

46. MT1446 和与积

（1）题目描述
输入一个M ×N的正整数数组，计算每一行的元素累加和，输出和的乘积。不考虑非法输入或者溢出等特殊情况。

格式

输入格式: 第一行输入正整数M和N(均小于100)，其后M行每行输入N个元素。
.
输出格式: 输出整型

样例1

输入格式:
3 2
8 9
5 4
1 7
.
输出格式:1224

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int m,n,a[100][100];
    scanf("%d%d",&m,&n);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++) scanf("%d",&a[i][j]);
    }
    int product=1;
    for(int i=0;i<m;i++){
        int sum=0;
        for(int j=0;j<n;j++){
            sum+=a[i][j];
        }
        product *= sum;
    }
    cout<<product;
    return 0;
}

---

47. MT1447 行列和

（1）题目描述
输入一个M×N的正整数数组，计算每一行的元素累加和，再计算每一列的元素累加和，输出他们。不考虑非法输入或者溢出等特殊情况。

格式

输入格式: 第一行输入M和N(均小于100)，其后M行每行输入N个元素(N个元素之间空格分隔)。
.
输出格式: 第一行依次输出每一行的元素累加和，第二行输出每一列的元素累加和，空格分隔。

样例1

输入格式:
3 2
8 9
5 4
1 7
.
输出格式:
17 9 8
14 20

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

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

    for(int i=0;i<m;i++){
        int sum=0;
        for(int j=0;j<n;j++) sum+=a[i][j];
        printf("%d ",sum);
    }

    printf("\n");

    for(int i=0; i<n; i++){
        int sum=0;
        for(int j=0;j<m;j++) sum+=a[j][i];
        printf("%d ",sum);
    }
    return 0;
}

---

48. MT1448 周边元素之和

（1）题目描述
编写函数计算m行n列 (m和n小于100)矩阵周边元素之和。

格式

输入格式: 第一行输入m和n为整型，空格分隔。第二行输入元素，如样例所示。
.
输出格式: 输出为整型

样例1

输入格式:
3 3
1 1 1
1 1 1
1 1 1
.
输出格式: 8

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

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

    int sum=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++)
            if(i==0 || i==m-1 || j==0 || j==n-1) sum+=a[i][j];
    }
    cout<<sum;
    return 0;
}

---

49. MT1449 边沿和内芯

（1）题目描述
有一个Nx N的矩阵，求矩阵四周一圈元素的和，以及内芯(除外圈之外的部分)所有元素的和，输出他们。

格式

输入格式:第一行输入N，第二行到第N+1行输入数组元素，整型，空格分隔。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式:
3
1 1 1
1 2 1
1 1 1
.
输出格式: 8 2

备注：

当N为1,2时，内芯没有元素，认为内芯元素之和为0。

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int m,a[100][100];
    scanf("%d",&m);

    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&a[i][j]);
    
    int outSum=0,inSum=0;
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            if(i==0 || i==m-1 || j==0 || j==m-1)
                outSum += a[i][j];
            else inSum += a[i][j];
    printf("%d %d",outSum,inSum);
    return 0;
}

---

50. MT1450 对称矩阵

（1）题目描述
判断N(<100）阶方阵A是否为对称矩阵，对称矩阵是以对角线为对称轴对应元素相等。

格式

输入格式:第一行输入N为整型，第二行输入元素，如样例所示。
.
输出格式: 输出YES或者NO。

样例1

输入格式:
3
1 1 1
1 2 1
3 1 1
.
输出格式: NO

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    bool flag=true;
    int m,a[1000][1000];
    cin>>m;

    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            if(i==j) continue;
            if(a[i][j] != a[j][i]){
                flag = false;
                break;
            }
        }   
    }
   if(flag) cout<<"YES"<<endl;
   else cout<<"NO"<<endl;
    return 0;
}

---

小结(三)

典型范例：

1. 矩形例题：MT1437-1453

---

结语

近期会逐步将码题集题库中的新手村600题刷完，预计每天会更新50题，之后会逐步跟进黄金，钻石，星耀，王者的题，尽请期待！！！
同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~

愿你的结局，配得上你一路的颠沛流离。