算法競賽入門【碼蹄集新手村600題】（MT1401-1450）
(文章目錄)
前言
為什麼突然想學算法了？
> 用較為“官方”的語言講，是因為算法對計算機科學的所有分支都非常重要。 在絕大多數的計算機科學分支領域中，要想完成任何實質性的工作，了解算法的基礎知識并掌握與算法密切相關的資料結構知識是必不可少的。
> 但從實際而言，是因為當下快到了考研和找工作的年紀(ಥ_ಥ)，無論走哪一條路，都不免需要一些相對豐富的算法知識，是故，便産生了一個暑假速成算法的計劃，可能對于像我這種算法競賽小白而言，幾乎很難，但我仍然還是想嘗試一下，畢竟，夢想還是要有的，萬一實作了呢？～(￣▽￣～)~
為什麼選擇碼蹄集作為刷題軟體？
碼蹄集，是在全國高等學校計算機教學與産業實踐資源建設專家委員會(TIPCC) 指導下建設的，其依托全國各大名校計算機系和清華大學出版社等機關的強大資源，旨在為計算機學習愛好者提供全面和權威的計算機習題。
算法競賽入門【碼蹄集新手村600題】（MT1401-1450）算法競賽入門【碼蹄集新手村600題】（MT1401-1450）前言目錄
目錄
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
2. 旋轉數組：MT1411
3. 并交集：MT1413-1414
4. 大小相同：MT1415
5. 最長子數組：MT1416
6. 連續子序列：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;
}
小結(二)
經典例題
- 異或：MT1421
- 卡特蘭序列：MT1424
- 找規律：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;
}
小結(三)
- 矩形例題：MT1437-1453