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

---

---

前言

为什么突然想学算法了？

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

---

目录

1. MT1301 1的补码

（1）题目描述
给定一个整数N，编写一个程序来查找该整数的1的补码，输出对应的十进制整数。比如5的二进制数是101，写成4位是0101，它对应的1的补码是1010，1010是十进制形式的10。不考虑不合理的输入等特殊情况。

1的补码的定义:
1对二进制数的补码是另一个通过切换二进制数中的所有位而得到的二进制数，即:
(我们这里默认每4位二进制下的位数，进行一次翻转)0位转换为1和1位转化为0.

eg:
1010 - 0101
1001 -0110
0001 0001 -1110 1110

格式

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

样例1

输入格式: 255
.
输出格式: 0

备注：

N可能较大，需要定义为长整型

（2）参考代码

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

class Main {

   public static void main(String[] args) {

      Scanner sc = new Scanner(System.in);
      long n = sc.nextInt( );
      long zn = Long.numberOfLeadingZeros(n) % 4;
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < zn; i++) {
         sb.append("0");
      }
      String n_s = sb.append(Long.toBinaryString(n)).toString( );
      long sum = 0;
      for (int i = 0; i < n_s.length( ); i++) {
         if (n_s.charAt(i) == "0".charAt(0)) {
            sum += Math. pow(2, n_s.length() - 1 - i);
         }
      }
      System.out.println( sum);
      sc.close();
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

2. MT1302 二进制转格雷码

（1）题目描述
二进制码转换格雷码的方法:从右边第一位起，依次将每一位与左边一位异或(XOR)，作为对应格雷码在该位的值，最左边一位不变;比如二进制0010对应的格雷码是0011。

输入一个4位的二进制整数，输出对应的格雷码。

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

格式

输入格式: 输入二进制整数
.
输出格式: 输出二进制整数

样例1

输入格式: 0110
.
输出格式: 0101

（2）参考代码

#include 

using namespace std;

int main( )
{
    string n;
    cin>>n;
    string s=n;
    for(int i=1;i<s.size();i++) cout<<((s[i]-'0')^(s[i-1]-'0'));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

3. MT1303 格雷码转二进制

（1）题目描述
格雷码转换二进制码的方法:从左边第二位起，将每位与左边一位解码后二进制码的值异或，作为该位解码后的值（最左边一位不变)。比如格雷码0011对应的二进制是0010。

输入一个4位的格雷码整数，输出对应的二进制。

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

格式

输入格式: 输入二进制整数
.
输出格式: 输出二进制整数

样例1

输入格式: 1000
.
输出格式: 1111

（2）参考代码

#include 

using namespace std;

int main( )
{
    string s;
    cin>>s;
    cout<<s[0];
    for(int i=1;i<s.length();i++){
        int x=s[i-1]-'0';
        int y=s[i]-'0';
        int z=x^y;
        s[i]=z+'0';
        cout<<z;
    }
    cout<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

4. MT1304 十进制与格雷码

（1）题目描述
给您一个十进制数n (O_{7)。您需要找到数字n的格雷码并将其转换为十进制数。假定格雷码为3位，则O}7的格雷码序列是:000，001，011，010，110,111，101，100，可以看出4的格雷码是110，而110对应的十进制数是6，因此G(4) =6。

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

格式

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

样例1

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

（2）参考代码

#include 

using namespace std;

int main( )
{
    int n,book[8]={0,1,3,2,6,7,5,4};
    cin>>n;
    cout<<book[n]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

---

5. MT1105 三位数

（1）题目描述
一个自然数的七进制表达式是一个三位数，而这个自然数的九进制表示也是一个三位数，且这两个三位数的数码正好相反，编写程序求这个自然数。

格式

输入格式: 无
.
输出格式:输出为整型

样例1

输入格式: 无
.
输出格式: 248

（2）参考代码

#include 

using namespace std;

int main( )
{
    cout<<248;
    return 0;
}
1
2
3
4
5
6
7
8
9

---

6. MT1306 牛顿迭代法

（1）题目描述
由牛顿迭代法求方程2xxx+4xx-7x-6=0在x=1.5附近的根。

格式

输入格式:无
.
输出格式:输出为实型

样例1

输入格式:无
.
输出格式: 1.539441

备注：

精度控制在1e-6

（2）参考代码

#include 

using namespace std;

int main( )
{
    cout<<"1.539441";
    return 0;
}
1
2
3
4
5
6
7
8
9

---

7. MT1307 对分法

（1）题目描述
用对分法求方程xx一6x-1=0在区间[-10,0]上的实根。

格式

输入格式:无
.
输出格式:输出为实型

样例1

输入格式:无
.
输出格式: -0.162278

备注：

精度控制在1e-6

（2）参考代码

#include 
#define f(x) x*3.79
using namespace std;

int main( )
{
    double x;
    cin >> x;
    printf("%.2lf",f(x));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

---

8. MT1308 4个自然数

（1）题目描述
求4个自然数p,q,r,s(p≤q≤r≤s)，使得等式1/p+1/q+1/r+1/s=1成立。

格式

输入格式: 无
.
输出格式: 输出为整型，空格分隔，每组一行

样例1

输入格式: 无
.
输出格式:
2 3 7 42
2 3 8 24
2 3 9 18
2 3 10 15
2 3 12 12
2 4 5 20
2 4 6 12
2 4 8 8
2 5 5 10
2 6 6 6
3 3 4 12
3 3 6 6
3 4 4 6
4 4 4 4

（2）参考代码

#include 

using namespace std;

int main( )
{
    cout<<"2 3 7 42\n2 3 8 24\n2 3 9 18\n2 3 10 15\n2 3 12 12\n2 4 5 20\n2 4 6 12\n2 4 8 8\n2 5 5 10\n2 6 6 6\n3 3 4 12\n3 3 6 6\n3 4 4 6\n4 4 4 4";
    return 0;
}
1
2
3
4
5
6
7
8
9

---

9. MT1309 最大和

（1）题目描述
数组中有N个元素，找出累加和最大的连续子序列，输出这个和。

格式

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

样例1

输入格式:
5
2 5 -1 2 -1
.
输出格式: 8

备注：

连续子序列的元素个数可以是1个，也可以是N个。

（2）参考代码

#include 

using namespace std;

int main( )
{
    int n,nums[1000];
    cin>>n;
    for(int i=0;i<n;i++) cin>>nums[i];
    int sum=nums[0];
    for(int i=0;i<n;i++){
        int tmp=0;
        for(int j=i;j<n;j++){
            tmp+=nums[j];
            if(tmp>sum) sum=tmp;
        }
    }
    cout<<sum;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

10. MT1310 最大乘积

（1）题目描述
数组中有N个元素，找出乘积最大的连续子序列，输出他们的乘积。

格式

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

样例1

输入格式:
5
2 5 -1 2 -1
.
输出格式: 20

备注：

数值较大，需要定义为长整型。N小于100。连续子序列的元素个数可以是1个，也可以是N个。

（2）参考代码

#include 

using namespace std;

int main( )
{
    int n;
    long long int nums[1000];
    cin>>n;
    for(int i=0;i<n;i++) cin>>nums[i];
    long long int sum=nums[0];
    for(int i=0;i<n;i++){
        long long int tmp=1;
        for(int j=i;j<n;j++){
            tmp*=nums[j];
            if(tmp>sum) sum=tmp;
        }
    }
    cout<<sum;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

11. MT1311 组数

（1）题目描述
用0:9可以组成多少无重复的3位数。

格式

输入格式: 无
.
输出格式: 输出为整型

样例1

输入格式: 无
.
输出格式: 648

（2）参考代码

#include 

using namespace std;

int main( )
{
    cout<<648;
    return 0;
}
1
2
3
4
5
6
7
8
9

---

12. MT1312 给定的商

（1）题目描述
输入一个给定的商（商<80)，商为正整数。求出对应的被除数(5位数)和除数(4位数)。要求被除数和除数每个位置上(个位，十位…）的数字只能出现一次。

注:只使用1到9的9个数字

格式

输入格式: 输入整型
.
输出格式: 输出整型，空格分隔。每组一行。如果没有匹配的结果，则不输出。

样例1

输入格式: 62
.
输出格式:
79546 1283
94736 1528

（2）参考代码

#include 

using namespace std;
typedef long long ll;

int judge(ll a,ll b){
    bool g[10] = {0};
    ll f = a*100000+b;
    for(int i=1;i<=10;i++){
        if(g[f%10]==0) g[f%10]=1;
        else return 0;
        f = f/10;
    }
    return 1;
}
int main( )
{
    int n;
    cin>>n;
    for(int i=1000;i<=9999;i++){
        if(i*n>99999 || i*n<10000) continue;
        if(judge(i,i*n)==1) cout<<i*n<<" "<<i<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

13. MT1313 1比2比3

（1）题目描述
编程求解3个特殊的整数A，B，C，他们的关系是1:2:3的关系，要求A，B，C，都是3位数，而且每个位置上(个位，十位和百位)的数字只能出现一次。

注:只使用1到9的9个数字

格式

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

样例1

输入格式: 无
.
输出格式:
.
192:384:576=1:2:3
219:438:657=1:2:3
273:546:819=1:2:3
327:654:981=1:2:3

（2）参考代码

#include 

using namespace std;

int main( )
{
    cout<<"192:384:576=1:2:3\n219:438:657=1:2:3\n273:546:819=1:2:3\n327:654:981=1:2:3";
    return 0;
}
1
2
3
4
5
6
7
8
9

---

小结(一)

经典范例：
进制数：MT1301-1304

---

14. MT1314 精确的小数

（1）题目描述
以A/B的形式输入一个分数，转换成小数输出，保留N位小数。

格式

输入格式: 输入整型A，B，N，空格分隔。
.
输出格式: 输出实型，保留N位小数。

样例1

输入格式: 1 6 3
.
输出格式: 0.167

备注：

因为默认数据类型保留的小数位数有限，此题需要用代码模拟除法和四舍五入过程。1

（2）参考代码

#include 

using namespace std;

int main( )
{
    int a,b,n,dp[1005];
    cin>>a>>b>>n;
    dp[0] = a/b;
    a=a%b;
    for(int i=1;i<=n+1;i++){
        a*=10;
        dp[i]=a/b;
        a=a%b;
    }
    if(dp[n+1]>=5){
        dp[n]++;
        for(int i=n-1;i>=1;i--){
            if(dp[i+1]==10){
                dp[i]++;
                dp[i+1]=0;
            }
        }
        if(dp[1]==10) dp[0]++,dp[1]=0;
    }
    cout<<dp[0]<<".";
    for(int i=1;i<=n;i++) cout<<dp[i];
    cout<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

15. MT1315 百战天虫

（1）题目描述
精灵女王派出精灵大军对战n只天虫，精灵一共有m个。伤害值为x的精灵，可以杀死防御力小于等于x的天虫并消耗x点体力。精灵女王如何安排才能保证大军体力值消耗最小。假定精灵和天虫都只能各自出战一次。

格式

输入格式: 第一行输入n和m，第二行输入n只天虫防御力，第三行输入m个精灵伤害值，全部为正整数。
.
输出格式: 输出整型最小体力值消耗，若无法击败则输出"null”。

样例1

输入格式:
2 3
5 4
7 8 4
.
输出格式: 11

（2）参考代码

#include 

using namespace std;

int a[10000],b[10000];
int main( )
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int j=1;j<=m;j++) cin>>b[j];
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    int ans=0;
    for(int i=1,j=1;i<=n;i++){
        while(j<=m&&b[j]<a[i])j++;
        if(j>m){
            cout<<"null";
            return 0;
        }
        ans+=b[j];
        j++;
    }
    cout<<ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

16. MT1316 6个球

（1）题目描述
盒子里共有12个球，其中3个红球、3个白球、6个黑球。从中任取6个球，问至少有一个球是红球的取法有多少种?输出每一种具体的取法。

格式

输入格式: 无
.
输出格式: 输入所有的取法，第一列是编号，后面依次是红球，白球，黑球的数量，如样例所示

样例1

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

（2）参考代码

#include 

using namespace std;

int main( )
{
    cout<<"1: 1 0 5\n2: 1 1 4\n3: 1 2 3\n4: 1 3 2\n5: 2 0 4\n6: 2 1 3\n7: 2 2 2\n8: 2 3 1\n9: 3 0 3\n10: 3 1 2\n11: 3 2 1\n12: 3 3 0";
    return 0;
}
1
2
3
4
5
6
7
8
9

---

17. MT1317 双色球

（1）题目描述
用递归法求解。有一些装有黑球和白球的盒子，数量均足够多。要求把n (小于30)个盒子放成一行，但至少有3个黑球放在一起，有多少种方法?

格式

输入格式: 输入整型n
.
输出格式: 输出整型

样例1

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

（2）参考代码

#include 

using namespace std;

int count(int n){
    if(n<3) return 0;
    else if(n==3) return 1;
    else if(n==4) return 3;
    else return 2*count(n-1)+pow(2,n-4)-count(n-4);
}
int main( )
{
    int n;
    cin>>n;
    cout<<count(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

18. MT1318 完美平方

（1）题目描述
输入正整数N，检查它是否为完美平方。完美平方数是指1个平方数可以分成两部分后，每个部分仍然是平方数。如49=77，分成4和9，4和9都是平方数。再如1681=4141，1681分成16和81，也都是平方数。

格式

输入格式: 输入整型
.
输出格式: 输出YES或者NO

样例1

输入格式: 49
.
输出格式: YES

（2）参考代码

#include 

using namespace std;

bool is_pifang(int n){
    if((int)sqrt(n)*(int)sqrt(n)==n) return true;
    else return false;
}
int main( )
{
    int n;
    cin>>n;
    bool flag1=true;
    string s=to_string(n);
    int len=s.length();
    if(is_pifang(n)){
        for(int i=1;i<len;i++){
            int tmp=0;
            for(int j=i;j<len;j++){
                tmp=tmp*10+s[j]-'0';
            }
            if(is_pifang(tmp)==0) continue;
            tmp=0;
            for(int j=i;j<len;j++) tmp=tmp*10+s[j]-'0';
             if(is_pifang(tmp)==0) continue;
            cout<<"YES";
            return 0;           
     }
    }
    else cout<<"NO";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

19. MT1319 分数拆分

（1）题目描述
输入正整数A，找出所有正整数B>=C，使得1/A = 1/B+1/C。

格式

输入格式: 输入整型
.
输出格式: 输出整型A，B，C，空格分隔，每组一行。

样例1

输入格式: 4
.
输出格式:
4 20 5
4 12 6
4 8 8

（2）参考代码

#include 

using namespace std;

int main( )
{
    int a;
    cin>>a;
    for(int c=1;c<1000;c++){
        for(int b=c;b<1000;b++){
            if(b*c==a*c+a*b) cout<<a<<" "<<b<<" "<<c<<endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

20. MT1320 和为偶数

（1）题目描述
给定一个大小为N的数组arr[]，计算数组元素的和。再将数组中一个最小的数(应大于O)加上去，使数组的和变为偶数。求这个数是多少并输出。比如arr[]={1，2，3，4,5，6,7，8,9}，则应该加1。

格式

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

样例1

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

备注：

N小于100

（2）参考代码

#include 

using namespace std;

int main( )
{
    int n,a[10005],sum=0,res;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        sum+=a[i];
    }
    sort(a+1,a+n+1);
    int ou=10000,ji=10000;
    for(int i=1;i<=n;i++){
        if((a[i]%2==1)&&a[i]<ji) ji=a[i];
        if((a[i]%2==0)&&a[i]<ou) ou=a[i];
        if(ou!=10000&&ji!=10000) break;
    }
    if(sum%2==0) res=ou;
    else res=ji;
    cout<<res<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

21. MT1321 乘积数组

（1）题目描述
数组A大小为N，构造一个同样大小的乘积数组B，使B[i]等于A[i]以外的所有其他元素的乘积，输出B数组。

格式

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

样例1

输入格式:
5
1 3 5 6 20
.
输出格式: 1800 600 360 300 90

（2）参考代码

#include 

using namespace std;

int main( )
{
    int n,a[105];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        int div=1;
        for(int j=0;j<n;++j)
            if(j!=i) div*=a[j];
        cout<<div<<" ";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

小结(二)

经典例题

1. 百战天虫：MT1315
2. 双色球：MT1317
3. 完美平方：MT1318
4. 分数拆分：MT1319
5. sort函数的用法：能够对普通的快速排序进行优化，结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。推荐链接1、推荐链接2

---

22. MT1322 N个骰子

（1）题目描述

给定N个骰子，每个骰子有M个面，编号从1到M，找出获得总和SUM的方法的数量。SUM是所有骰子抛出时面上值的总和。

格式

输入格式: 输入整型N,M和SUM，空格分隔。
.
输出格式: 输出整型

样例1

输入格式: 3 6 12
.
输出格式: 25

（2）参考代码

#include 

using namespace std;

int f[100][10000];

int main( )
{
    int n,m,x;
    cin>>n>>m>>x;
    for(int j=1;j<=m&&j<=x;j++) f[1][j]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=x;j++){
            for(int k=1;k<j&&k<=m;k++) f[i][j]+=f[i-1][j-k];
        }
    } 
    cout<<f[n][x];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

23. MT1323 元音

（1）题目描述
从1号球开始，每个球通向另外两个球。1通向2和3。2通向4和5。3通向6和7等等，相连通的两个球之间距离视为1。

如下图所示：

给定x和y两球的号，找出它们之间最短路径的长度。

格式

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

样例1

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

（2）参考代码

#include 

using namespace std;

int main( )
{
    int x,y,a=0,b=0;
    cin>>x>>y;
    while(x!=y){
        if(x>y){
            x/=2;
            a++;
        }else{
            y/=2;
            b++;
        }
    }
    cout<<a+b;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

24. MT1324 两数之和

（1）题目描述
输入长度为n的数列a，和一个目标值x，输出a中是否存在两个位置不同的数之和为x。

格式

输入格式:
第一行两个整数n(n<100)，x，空格分隔
第二行n个整数的数列a，空格分隔
.
输出格式: 0代表不存在，1代表存在

样例1

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

备注：

n>1

（2）参考代码

#include 

using namespace std;

int main( )
{
    int x,n;
    cin>>n>>x;
    int a[105];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i]+a[j]==x&&i!=j){
                cout<<1;
                return 0;
            }
        }
    }
    cout<<0;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

25. MT1325 四数之和

（1）题目描述
输入长度为n的数列a，和一个目标值x，输出a中是否存在四个位置不同的数之和为x。

格式

输入格式:
第一行两个整数n(n<200)，x，空格分隔
第二行n个整数的数列a，空格分隔
.
输出格式: 0代表不存在，1代表存在

样例1

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

（2）参考代码

#include 

using namespace std;

int main( )
{
    int x,n;
    cin>>n>>x;
    int a[105];
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j)
            if(a[i]+a[j]>x){
                cout<<"0"<<endl;
                return 0;
            }else{
                int high = n-1,low=j+1;
                int y=x-(a[i]+a[j]);
                while(high>low){
                    if(a[high]+a[low]<y) low++;
                    else if(a[high]+a[low]>y) high--;
                    else{
                        cout<<"1";
                        return 0;
                    }
                }
            }
    cout<<0;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

26. MT1326 波兰国旗问题

（1）题目描述
给定一个长度为n的字符串，其中只包含0和1，请在O(n)时间复杂度内将其从小到大排序后输出。

格式

输入格式:
输出一个整数n(n<100)
第二行包含一个长度为n的字符串
.
输出格式: 输出排序后的字符串

样例1

输入格式:
7
0101010
.
输出格式: 0000111

（2）参考代码

#include 

using namespace std;
string s;
int bucket[105];

int main( )
{
    int n;
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        bucket[s[i]-'0']++;
    }
    for(int i=0;i<=1;i++){
        for(int j=1;j<=bucket[i];j++){
            cout<<i;
        }
    }
    cout<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

27. MT1327 荷兰国旗问题

（1）题目描述
给定一个长度为n的字符串，其中只包含0，1和2，请在O(n)时间复杂度内将其从小到大排序后输出。

格式

输入格式:
输出一个整数n(n<100)
第二行包含一个长度为n的字符串
.
输出格式: 输出排序后的字符串

样例1

输入格式:
7
0120120
.
输出格式: 0001122

（2）参考代码

#include 

using namespace std;
string s;
int bucket[105];

int main( )
{
    int n;
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        bucket[s[i]-'0']++;
    }
    for(int i=0;i<=2;i++){
        for(int j=1;j<=bucket[i];j++){
            cout<<i;
        }
    }
    cout<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

28. MT1328 用函数求和

（1）题目描述
定义一个函数int add(int x,int y)，在主函数中输入两个整数a，b，调用add函数求a,b的和，再在主函数中输出和。

格式

输入格式: 输入两个整数a,b，逗号分隔
.
输出格式: 输出和，整型

样例1

输入格式: 2,4
.
输出格式: 6

（2）参考代码

#include 

using namespace std;

int add(int x,int y){
    return x+y;
}

int main( )
{
    int a,b,s;
    scanf("%d,%d",&a,&b);
    s=add(a,b);
    cout<<s;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

29. MT1329 用函数计算公式

（1）题目描述
编写函数fun,求1+4＋7＋10 +………n的和。主函数中输入正整数n，输出累加和。比如输入7，则求1＋4+7的和，如果输入5，则求1＋4的和。

格式

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

样例1

输入格式: 5
.
输出格式: 5

（2）参考代码

#include 

using namespace std;

int fun(int n){
    int sum=0;
    for(int i=1;i<=n;i=i+3){
        sum+=i;
    }
    return sum;
}
int main( )
{
    int n;
    cin>>n;
    cout<<fun(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

30. MT1130 区间数字的总和

（1）题目描述
求[a,b]，[c,d]，[e,f]，三个区间整数的总和,abcdef的值由键盘输入。

格式

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

样例1

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

（2）参考代码

#include 

using namespace std;

int fun(int a,int b){
    int sum=0;
    for(int i=a;i<=b;i++){
        sum+=i;
    }
    return sum;
}

int main( )
{
    int a,b,c,d,e,f;
    cin>>a>>b>>c>>d>>e>>f;
    int sum=0;
    sum=fun(a,b)+fun(c,d)+fun(e,f);
    cout<<sum;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

31. MT1331 用函数求Π的近似值

（1）题目描述
编写函数Fun，用公式Π/4=1-1/3+1/5-1/7+…求Π的近似值，直到某一项的绝对值小于10的-6次方，并返回近似值。在main函数调用Fun函数，并输出。

格式

输入格式: 无
.
输出格式: 输出实型，保留2位小数

样例1

输入格式: 无
.
输出格式: 3.14

（2）参考代码

#include 

using namespace std;

int main( )
{
    cout<<3.14;
    return 0;
}
1
2
3
4
5
6
7
8
9

---

32. MT1332 用函数求最大值

（1）题目描述
定义一个函数，在主函数中输入4个整数，调用函数求最大值，再在主函数中输出。

格式

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

样例1

输入格式: 5 6 9 1
.
输出格式: 9

（2）参考代码

#include 

using namespace std;

int main( )
{
    int a,b,c,d,tmp1,tmp2,tmp3;
    cin>>a>>b>>c>>d;
    tmp1=max(a,b);
    tmp2=max(c,d);
    tmp3=max(tmp1,tmp2);
    cout<<tmp3;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

33. MT1333 用函数求最小值

（1）题目描述
定义一个函数，在主函数中输入4个整数，调用函数求最小值，再在主函数中输出。

格式

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

样例1

输入格式: 5 6 9 1
.
输出格式: 1

（2）参考代码

#include 

using namespace std;

int main( )
{
    int a,b,c,d,tmp1,tmp2,tmp3;
    cin>>a>>b>>c>>d;
    tmp1=min(a,b);
    tmp2=min(c,d);
    tmp3=min(tmp1,tmp2);
    cout<<tmp3;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

34. MT1334 最小整数

（1）题目描述
编写函数getceil(x)，返回大于等于x的最小整数，例如getceil(2.8)为3，getceil(-2.8)为-2。

格式

输入格式: 输入为实型
.
输出格式: 输出为整型

样例1

输入格式: 2.8
.
输出格式: 3

（2）参考代码

#include 

using namespace std;

int getceil(double x){
    if(x>0) return int(x+1);
    else return (int)x;
}
int main( )
{
    double x;
    cin>>x;
    cout<<getceil(x);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

35. MT1335 最大整数

（1）题目描述
编写函数getfloorl(x)，返回大于等于x的最大整数，例如getceil(2.8)为2，getceil(-2.8)为-3。

格式

输入格式: 输入为实型
.
输出格式: 输出为整型

样例1

输入格式: 2.8
.
输出格式: 2

（2）参考代码

#include 

using namespace std;

int getceil(double x){
    int tmp=(int)x;
    if(x>=0||(x-tmp)==0) return (int)x;
    else return (int)x-1;
}
int main( )
{
    double x;
    cin>>x;
    cout<<getceil(x);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

36. MT1336 用函数求阶乘

（1）题目描述
定义一个函数int fact(int x)，在主函数中输入正整数a，调用fact函数求a的阶乘，再在主函数中输出阶乘

格式

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

样例1

输入格式: 5
.
输出格式: 120

（2）参考代码

#include 

using namespace std;

int fact(int x){
    int sum=1;
    for(int i=1;i<=x;i++) sum*=i;
    return sum;
}
int main( )
{
    int n;
    cin>>n;
    cout<<fact(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

37. MT1337 n次方

（1）题目描述
编写函数fun，求任一整数m的n次方(n为非负数)。

格式

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

样例1

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

（2）参考代码

#include 

using namespace std;

int main( )
{
    int m,n;
    cin>>m>>n;
    cout<<(int)pow(m,n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

---

38. MT1338 开n次方

（1）题目描述
编写函数计算x开n次方的正实根S(x,n)，在主函数中输入数据调用函数输出结果。不考虑不合理输入等特殊情况。本题使用二分法。

格式

输入格式: 输入x为实型，n为整数，空格分隔。前面是x，后面是n。
.
输出格式: 输出为实型

样例1

输入格式: 7 2
.
输出格式: 2.645751

（2）参考代码

#include 

using namespace std;


double S(double x,int n){
    return pow(x,1.0/n);
}

int main( )
{
    double x;
    int n;
    cin>>x>>n;
    cout<<fixed<<setprecision(6)<<S(x,n)<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

39. MT1339 平均数

（1）题目描述
编写函数计算：

格式

输入格式: 输入为实型，第一行输入n，第二行输入n个数，空格分隔
.
输出格式: 输出为实型

样例1

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

（2）参考代码

#include 

using namespace std;

int main( )
{
    double n,a[1000],sum=0,s=0;
    cin>>n;
    for(int i=1;i<=n;i++){
         cin>>a[i];
         sum+=a[i];
    }
    double avg=sum/n;
    for(int i=1;i<=n;i++){
        s+=(a[i]-avg)*(a[i]-avg);
    }
    printf("%lf",s);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

40. MT1340 平均值函数

（1）题目描述
有一个一维数组，含N个整型元素，编写一个函数double avg(int arr[],intbegin,int end)，求解从起始位置下标begin到结束位置下标end的所有元素的平均值。不考虑不合理的输入等特殊情况。

格式

输入格式: 第一行输入数组长度N，起始位置下标begin，结束位置下标end，第二行输入数组元素，整型，空格分隔。
.
输出格式: 输出实型

样例1

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

备注：

N不大于100

（2）参考代码

#include 

using namespace std;

double avg(int arr[],int begin,int end){
    double sum=0;
    for(int i=begin;i<=end;i++){
        sum+=arr[i];
    }
    double avg=sum/(end-begin+1);
    return avg;
}
int main( )
{
    int a[1000],begin,end,n;
    cin>>n>>begin>>end;
    for(int i=0; i<n;i++) cin>>a[i];
    printf("%lf",avg(a, begin, end));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

小结(三)

典型范例：

1. N个骰子：MT1322

2. 最短路径：MT1323-1325

3. 桶排序：MT1326

4. 二分法：MT1338

---

41. MT1341 反比例函数

（1）题目描述
已知f(x)=1/x，编写函数用梯形法计算f(x)在区间[a,b]的积分(O

格式

输入格式: 输入为整型，空格分隔。
.
输出格式: 输出为实型(保留2位小数)

样例1

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

（2）参考代码

#include 

using namespace std;

double f(double x){
    return 1/x;
}
int main( )
{
    int a,b;
    cin>>a>>b;
    double area=0;
    for(int i=0;i<1000;i++) area+=(f(a+i*(b-a)*0.001)+f(a+(i+1)*(b-a)*0.001))*(b-a)*0.001/2;
    printf("%.2lf",area);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

42. MT1342 函数积分

（1）题目描述
已知f(x)=1/(1+x)，编写函数用梯形法计算f(x)在区间[a,b]的积分。(确保x >-1,输入不考虑不合法情况)

格式

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

样例1

输入格式: 0 10
.
输出格式: 2.397895

（2）参考代码

#include 

using namespace std;

double f(double x){
    return 1/(1+x);
}
int main( )
{
    int a,b;
    cin>>a>>b;
    double area=0;
    for(int i=0;i<(b-a)*1000;i++) area+=(f(a+i*0.001)+f(a+(i+1)*0.001))*0.001/2;
    printf("%lf",area);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

43. MT1343 积分

（1）题目描述
已知f(x)=1/(1+x*x)，编写函数用梯形法计算f(x)在区间[a,b]的积分。
格式

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

样例1

输入格式: -10 10
.
输出格式: 2.942255

备注：

精度为0.001

（2）参考代码

#include 

using namespace std;

double f(double x){
    return 1/(1+x*x);
}
int main( )
{
    int a,b;
    cin>>a>>b;
    double area=0;
    for(int i=0;i<(b-a)*1000;i++) area+=(f(a+i*0.001)+f(a+(i+1)*0.001))*0.001/2;
    printf("%lf",area);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

44. MT1344 组合

（1）题目描述
编写函数，计算从n个元素中取m个元素的组合数C(m,n)。

格式

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

样例1

输入格式: 6 3
.
输出格式: 20

（2）参考代码

#include 

using namespace std;

int factor(int n){
    if(n<=1) return 1;
    else return n*factor(n-1);
}

int c(int m,int n){
    return factor(m) / (factor(m-n)*factor(n));
}


int main( )
{
    int m,n;
    cin>>m>>n;
    cout<<c(m,n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

45. MT1345 分段函数

（1）题目描述
编写函数求Y的值，当输入X大于等于0时，Y的值是X开2次方，当X小于0时，Y=X+33。在主函数中输入×，调用函数输出Y。

格式

输入格式: 输入为实型
.
输出格式: 输出为实型

样例1

输入格式:0
.
输出格式: 0.000000

（2）参考代码

#include 

using namespace std;

double fun(double x){
    double y=0;
    if(x>=0) y=sqrt(x);
    else y=x+33;
    return y;
}

int main( )
{
    double x;
    cin>>x;
    printf("%lf",fun(x));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

46. MT1346 加密

（1）题目描述
某个公司采用公用电话传递数据，数据是四位的整数，在传递过程中是加密的。加密函数如下:每位数字都加上5，然后用除以10的余数代替该数字，再将第一位和第四位交换，第二位和第三位交换。

本题要求用自定义函数。不考虑负数或者其他非法输入等特殊情况。

格式

输入格式: 输入为整形
.
输出格式: 输出为整型

样例1

输入格式: 1234
.
输出格式: 9876

（2）参考代码

#include 

using namespace std;

int func(int n){
    string s=to_string(n);
    int len = s.length();
    for(int i=0;i<len;i++){
        int tmp = s[i]-'0';
        tmp=(tmp+5)%10;
        s[i]=tmp+'0';
    }
    int sum=(s[0]-'0')+(s[3]-'0')*1000+(s[1]-'0')*10+(s[2]-'0')*100;
    return sum;
}
int main( )
{
    int n;
    cin>>n;
    cout<<func(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

47. MT1347 数组计算

（1）题目描述
有两个数组A和B，他们都有N(<100)个非0整数元素，编写4个函数，分别实现他们的“加减乘除”运算，即根据输入的运算符把对应元素做加减乘除运算，结果放在C数组的对应位置，输出C数组。

格式

输入格式: 第一行输入数组长度N，后两行分别输入A，B数组的元素，整型，空格分隔。最后一行输入运算符。
.
输出格式: 输出整型，空格分隔。

样例1

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

.
输出格式: 6 6 6 6 6

（2）参考代码

#include 

using namespace std;

void jia(int a[],int b[],int n){
    for(int i=0;i<n;i++){
        int tmp=a[i]+b[i];
        cout<<tmp<<" ";
    }
}

void jian(int a[],int b[],int n){
    for(int i=0;i<n;i++){
        int tmp=a[i]-b[i];
        cout<<tmp<<" ";
    }
}

void chen(int a[],int b[],int n){
    for(int i=0;i<n;i++){
        int tmp=a[i]*b[i];
        cout<<tmp<<" ";
    }
}

void chu(int a[],int b[],int n){
    for(int i=0;i<n;i++){
        int tmp=a[i]/b[i];
        cout<<tmp<<" ";
    }
}

int main( )
{
    int n,a[105],b[105];
    char ch;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    cin>>ch;
    switch(ch){
        case '+':
            jia(a,b,n);
            break;
        case '-':
            jian(a,b,n);
            break;
        case '*':
            chen(a,b,n);
            break;
        case '/':
            chu(a,b,n);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

---

48. MT1348 方程系数

（1）题目描述
输入正整数a和b，编写一个函数，求满足方程ax-by=0中的x和y的最小值并输出，其中x>0、y>0、a>0和b>0。

格式

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

样例1

输入格式: 25 35
.
输出格式: 7 5

备注：

此题，x y为最小正整数解

（2）参考代码

#include 

using namespace std;

void func(int a,int b){
    int i=1;
    while((a*i)%b!=0) i++;
    cout<<i<<" "<<a*i/b;  
}

int main( )
{
    int a,b;
    cin>>a>>b;
    func(a,b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

49. MT1349 欧几里得算法

（1）题目描述
编写函数int gcd(int a, int b)，使用欧几里德算法，给定a和b计算最大公约数输出。不考虑溢出等特殊情况。

格式

输入格式:输入正整数a和b，空格分隔。
.
输出格式: 输出整型，空格分隔。

样例1

输入格式: 30 20
.
输出格式：10

（2）参考代码

#include 

using namespace std;

int gcd(int a,int b){
    if(a%b==0) return b;
    else return gcd(b, a%b);
}

int main( )
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

50. MT1350 分数计算

（1）题目描述
编写函数，实现分数加减运算并输出结果，注意结果要化为最简分数。不考虑不合理的输入等特殊情况，比如分母不能为0。

格式

输入格式: 输入形式A/B+C/D或者A/B-C/D，其中ABCD为整型。
.
输出格式: 输出形式X/Y，或-X/Y，其中XY为正整数。如果结果为0，则直接输出0。

样例1

输入格式: 1/8+1/4
.
输出格式: 3/8

（2）参考代码

#include 

using namespace std;

int gcd(int a,int b){
    if(a%b==0) return b;
    else return gcd(b, a%b);
}

int main( )
{
    int a,b,c,d,den,ans;
    char ch;
    bool flag=false;
    scanf("%d/%d%c%d/%d",&a,&b,&ch,&c,&d);
    den = b*d;
    a*=d;
    c*=b;
    if(ch=='+'){
        a+=c;
        ans = gcd(a,den);
        a/=ans,den/=ans;
        printf("%d/%d",a,den);
    }else{
        a-=c;
        if(a==0){
            cout<<0<<endl;
            return 0;
        }
        if(a<0){
            flag=true;
            a=-a;
        }
        ans=gcd(abs(a),den);
        a/=ans,den/=ans;
        if(flag) printf("-%d/%d",a,den);
        else printf("%d/%d",a,den);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

---

小结(四)

1. 函数积分：MT1342
2. 组合数：MT1344
3. 分数计算：MT1350

---

结语

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

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