算法竞赛入门【码蹄集新手村600题】(MT1151-1200）

前言

在这里插入图片描述

为什么突然想学算法了？

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

在这里插入图片描述

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

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

（1）题目描述
韩信点兵(大于10人)，三个三个一排少1个人，五个五个一排又少1个人，七个七个一排还少1个人。韩信生气了，从别的队伍里调来一个人!这样不管是三个一排五个一排还是七个一排都完美了。问原本最少应该有多少人。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    printf("104");
    return 0;
}

3. MT1153 真因子

（1）题目描述
输入正整数N，计算其所有真因子之和。自然数的真因子是严格小于该数的除数。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,ans=0;
    cin >> n;
    for(int i=1;i<=n/2+1;i++){
        if(n%i==0) ans+=i;
    }
    cout<<ans<<endl;
    return 0;
}

4. MT1154 缺数

（1）题目描述
若一个自然数的所有真因数之和比这个数小，此数就叫做缺数。输入正整数N，找出该数字是否为缺数输出YES或者NO。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,ans=0;
    cin >> n;
    for(int i=1;i<=n/2+1;i++){
        if(n%i==0) ans+=i;
    }
    if(ans<n) cout<<"YES";
    else cout<<"NO";
    return 0;
}

5. MT1155 单位矩阵

（1）题目描述
输入3X3的整型矩阵A，判断是否为单位矩阵，输出YES或者NO。

格式

输入格式: 输入矩阵，空格分隔
.
输出格式:输出YES或者NO

样例1

输入格式: 1 0 0 0 1 0 0 0 1
.
输出格式: YES

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int a[4][4],cnt=0;
    bool flag=false;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin >> a[i][j];
            if(a[i][j]) cnt++;
        } 
    } 
    if(a[1][1]&&a[2][2]&&a[3][3]&&cnt==3) flag=true;
    if(a[1][3]&&a[2][2]&&a[3][1]&&cnt==3) flag=true;

    if(flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

6. MT1156 稀疏矩阵

（1）题目描述
输入3X3的整型矩阵A，判断是否为稀疏矩阵，输出YES或者NO。若矩阵中数值为0的元素数目多于非0元素的数目就叫做稀疏矩阵。

格式

输入格式: 输入矩阵，空格分隔
.
输出格式: 输出YES或者NO

样例1

输入格式: 4 0 0 0 5 0 0 0 6
.
输出格式: YES

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int a[4][4],cnt=0,num=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin >> a[i][j];
            if(a[i][j]==0) cnt++;
            else num++;
        } 
    } 

    if(cnt>num) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

7. MT1157 矩阵相等

（1）题目描述
输入4X4的整型矩阵A和B，判断是否为相等，输出YES或者NO。

格式

输入格式: 输入矩阵，空格分隔。
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int a[5][5],b[5][5];
    bool flag=false;
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            cin >> a[i][j];
        } 
    } 
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            cin >> b[i][j];
            if(a[i][j]!=b[i][j]){
                cout<<"NO"<<endl;
                return 0;
            }
        } 
    }
    cout<<"YES"<<endl;
    return 0;
}

8. MT1158 分解

（1）题目描述
输入正整数N和M，判断N是否可以分解成M个不同的正整数的和，输出YES或者NO。

格式

输入格式: 输入正整数N和M，空格分隔
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

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

9. MT1159 指定集合

（1）题目描述
某数组含有N个元素，输出那些数字来自集合{4,5,6}的元素，按原序。没有就输出-1。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,m;
    bool flag=false;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> m;
        if(m==4 || m==5 || m==6){
            flag=true;
            cout << m<<" ";
        }
    }
    if(!flag) cout << -1 <<endl;
    return 0;
}

10. MT1160 尾数为零

（1）题目描述
输入正整数N，请在1!，2! ， 3! ...N!中查找尾数为零的数，统计这样的数字的个数并输出。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,num=1,ans=0;
    cin >>n;
    for(int i=1;i<=n;i++){
        num*=i;
        if(num%10==0) ans++;
    }
    cout<<ans;
    return 0;
}

11. MT1161 N的零

（1）题目描述
输入正整数N，将N的所有零转换为5。没有0就原样输出。不考虑不合理的输入等特殊情况。

格式

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

样例1

输入格式: 5002
.
输出格式: 5552

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    string s;
    int len;
    cin >> s;
    len = s.size();
    for(int i=0;i<len;i++){
        if(s[i]=='0') s[i]='5';
    }
    cout << s <<endl;
    return 0;
}

12. MT1162 数组最大公约数

（1）题目描述
给定一个由N个正整数组成的数组，求所有数组元素的最大公约数。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int getGCD(int a,int b){
    if(a%b==0) return b;
    else return getGCD(b, a%b);
}
int main( )
{
    int nums[100],n,ans=0;
    cin >> n;
    for(int i=0;i<n;i++) cin >> nums[i];
    sort(nums,nums+n);
    ans = getGCD(nums[n-1],nums[n-2]);
    for(int i=n-3;i>=2;i--) ans = getGCD(ans, nums[i]);
    cout<<ans;
    return 0;
}

13. MT1163 孪生质数

（1）题目描述
在质数中，若两个质数之差为2,我们称之为孪生质数,例如(3、5)(5、7)，输入2个正整数，判断他是不是孪生质数，输出YES或者NO。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

bool zhi(int n){
    if(n==1) return false;
    for(int i=2;i<=n/2;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
int main( )
{
    int a,b;
    cin >> a >>b;
    if(zhi(a)&&zhi(b)&&b-a==2||a-b==2) cout<<"YES";
    else cout<<"NO";
    return 0;
}

小结(一)

经典范例：
MT1153(真因子)、MT1155、MT1156、MT1157、MT1159
MT1160、MT1161、MT1162、MT1163(判断质数)

14. MT1164 最大数字

（1）题目描述
输入正整数N，找到小于或等于它的最大数字，并且其数字从高位到低位是非递减的顺序。

格式

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

样例1

输入格式: 200
.
输出格式: 199

备注：

若N为个位数，则所求为它本身

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

bool cmp(int x,int y){
    if(x>y) return false;
    return true;
}
int main( )
{
    string s;
    int n,len;
    double res;
    cin >> n;
    for(int i=n;i>=0;i--){
        s = to_string(i);
        len = s.size();
        bool flag = true;
        for(int j=0;j<len-1;j++){
            flag = cmp(s[j]-'0',s[j+1]-'0');
            if(!flag) break;
        }
        if(flag){
            res=i;
            break;
        }
    }
    if(n<10) res=n;
    cout << res <<endl;
    return 0;
}

15. MT1165 卡罗尔数

（1）题目描述
卡罗尔数是其值满足4n-2 (n+1) -1的整数(n为正整数)。输入正整数N判断它是不是卡罗尔数，输出YES或者NO。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    bool flag=false;
    cin >> n;
    for(int i=0;(2*i-3)<=n;i++){
        if(n==2*i-3) flag=true;
    }
    if(flag) cout<<"YES";
    else cout<<"NO";
    return 0;
}

16. MT1166 自守数

（1）题目描述
输入正整数N (N<10)，判断该数是否为自守数输出YES或者NO。当且仅当一个数的平方以与该数相同的数字结尾时，该数称为自守数。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    cin >> n;
    if(n*n%10==n) cout<<"YES";
    else cout<<"NO";
    return 0;
}

17. MT1167 自守数II

（1）题目描述
输入正整数N，检查该数是否为自守数输出YES或者NO。当且仅当一个数的平方以与该数相同的数字结尾时，该数称为自守数。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,l,m=1;
    cin >> n;
    l=n;
    while(l>0){
        m*=10;
        l=l/10;
    }
    int k=n*n-n;
    if(k%m==0) cout<<"YES";
    else cout<<"NO";
    return 0;
}

18. MT1168 阶乘数

（1）题目描述
输入正整数N，找出它是否是一个等于其他数的阶乘值的数，输出YES或者NO。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,sum=1;
    bool flag=false;
    cin >> n;
    for(int i=1;i<=n;i++){
        sum*=i;
        if(n==sum) flag=true;
    }
    if(flag) cout<<"YES";
    else cout<<"NO";
    return 0;
}

19. MT1169 平衡数

（1）题目描述
输入一个正整数，它有N位数，N是大于1的奇数，判断它是不是平衡数。如果左侧的所有数字和等于右侧的所有数字之和，则称为平衡数。不考虑不合理的输入等特殊情况。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    string s;
    int len,sum=0;
    cin >> s;
    len=s.size();
    for(int i=0;i<len;i++){
        if(i<len/2) sum+=s[i];
        if(i>len/2) sum-=s[i];
    }
    if(sum==0) cout<<"YES";
    else cout<<"NO";
    return 0;
}

20. MT1170 四叶玫瑰数

（1）题目描述
输入正整数N，判断它是不是一个四叶玫瑰数，输出YES或者NO。四位玫瑰数是4位数的自幂数，它的每个位上的数字的4次幂之和等于它本身。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,len,ans;
    bool flag;
    string s;
    cin >> n;
    s = to_string(n);
    len = s.size();
    for(int i=0;i<len;i++){
        ans+=pow(s[i]-'0',4);
    }
    if(ans == n) flag=true;
    if(len != 4) flag = false;

    if(flag) cout <<"YES"<<endl;
    else cout <<"NO"<<endl;
   
    return 0;
}

21. MT1171 幻数

（1）题目描述
一个数字，把他的各位数累加会得到一个新的数字，再把这个新数字的每一位加起来，重复这个过程，直到只剩下一位数字，如果最后剩下的数字是1，就称原数为一个幻数。输入正整数N，检查它是否是一个幻数，输出YES或者NO。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

string s;
int ans,len,n;
bool flag;

int circleAdd(int n){
    s = to_string(n);
    len = s.size();
    ans = 0;
    for(int i = 0;i<len;i++){
        ans+=s[i]-'0';
    }
    return ans;
}

int main( )
{
    cin >> n;
    int tmp = n;
    while(1){
        tmp = circleAdd(tmp);
        if(tmp == 1){
            flag = true;
            break;
        }else if(tmp<10) break;
    }
    if(flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

小结(二)

经典例题
MT1164、MT1166、MT1167、MT1169、MT1170
MT1171(幻数)

22. MT1172 完美数字

（1）题目描述

输入正整数N，检查它是否完美输出YES或者NO。把一个数字的每一位拆分开，计算他们的阶乘再累加，如果和等于原数字，则该数字是完美的。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

string s;
int ans,len,n;
bool flag;

int factorial(int n){
    int tmp=1;
    for(int i=n;i>=1;i--){
        tmp*=i;
    }
    return tmp;
}

int main( )
{
    cin >> n;
    s = to_string(n);
    len = s.size();
    for(int i=0;i<len;i++) ans+=factorial(s[i]-'0');
    if(ans==n) flag=true; 
    if(flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

23. MT1173 魔数

（1）题目描述
一个数字，把他乘以二，会得到一个新的数字，如果这个新数字依然由原数中那些数字组成，就称原数为一个魔数。输入正整数N，检查它是否是一个魔数，输出YES或者NO。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;
typedef long long ll;

double pi=3.1415926;
double res;
int ans,n,m,t,len,cnt=0,minn=10000,maxx=0;
string s;
char ch;
bool flag = true;
int dp[1000] = {0},bucket1[1000]={0},bucket2[1000]={0};

int main( )
{
    cin>>n;
    s=to_string(n);
    len=s.size();
    for(int i=0;i<len;i++) bucket1[s[i]-'0']++;
    ll tmp;
    tmp = n*2;
    s = to_string(tmp);
    len = s.size();
    for(int i=0;i<len;i++) bucket2[s[i]-'0']++;
    for(int i=0;i<=9;i++){
        if(bucket1[i]!=bucket2[i]){
            flag = false;
            break;
        }
    }
    if(flag)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

24. MT1174 A的B次方

（1）题目描述
输入正整数N，判断它是否可以表示为A的B次方，其中B>1，A>0，都是整数。输出YES或者NO。

格式

输入格式: 输入正整数N
.
输出格式: 输出YES或者NO

样例1

输入格式: 6
.
输出格式: NO

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,tmp;
    bool flag=false;
    cin >> n;
    if(n==1){
        cout<<"YES";
        return 0;
    }
    for(int i=2;i*i<=n;i++){
        for(int j=2;pow(i,j)<=n;j++){
            if(pow(i,j)==n)  flag=true;

        }
    }
    if(flag) cout<<"YES";
    else cout<<"NO";
    return 0;
}

25. MT1175 网球比赛

（1）题目描述
两个网球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三对赛手的名单。

格式

输入格式: 无
.
输出格式: 分3行输出，见样例

样例1

输入格式: 无
.
输出格式:
a with z
b with x
c with y

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    cout<<"a with z"<<endl;
    cout<<"b with x"<<endl;
    cout<<"c with y"<<endl;
    return 0;
}

26. MT1176 两个点的距离

（1）题目描述
给定笛卡尔平面上两个点的坐标，求它们之间的距离向上舍入为最接近的整数。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int x1,y1,x2,y2,ans;
    cin >> x1 >> y1;
    cin >> x2 >> y2;
    ans = ceil(sqrt(pow(x1-x2,2) + pow(y1-y2,2)));
    cout << ans <<endl;
    return 0;
}

27. MT1177 三角形

（1）题目描述
输入三角形的三个顶点坐标，和点N的坐标。判断N是否位于三角形内，输出YES或者NO。

格式

输入格式: 第一行输入三角形的三个顶点坐标(x1,y1) , (x2，y2）和(x3，y3)，第二行输入点N的坐标，整型，空格分隔。
.
输出格式: 输出YES或者NO

样例1

输入格式:
0 0 20 0 10 30
10 15
.
输出格式: YES

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int Area(int x1,int y1,int x2,int y2,int x3,int y3){
    double result = abs((x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3)/2.0);
    return result;
}
int main( )
{
    int x1,y1,x2,y2,x3,y3,x4,y4;
    double s123,s124,s134,s234;
    cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;

    s123 = Area(x1, y1, x2, y2, x3, y3);
    s124 = Area(x1, y1, x2, y2, x4, y4);
    s134 = Area(x1, y1, x3, y3, x4, y4);
    s234 = Area(x4, y4, x2, y2, x3, y3);

    if(s123==s124+s134+s234){
        cout<<"YES"<<endl;
    }else cout<<"NO"<<endl;
    return 0;
}

28. MT1178 点与线段的关系

（1）题目描述
输入线段的2个端点的坐标值x和y，再输入第3个点的坐标，判断点在不在线段上，输出YES或者NO。

格式

输入格式: 按照先起点(x,y）再终点(x,y）的次序。第二行输入第3个点的坐标。坐标整型。第一行两点之间空格，如样例所示。
.
输出格式: 输出YES或者NO

样例1

输入格式:
(-20,20) (-20,-10)
(0,0)
.
输出格式: NO

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int p1x,p1y,p2x,p2y;
    int qx,qy;
    scanf("(%d,%d) (%d,%d)\n",&p1x,&p1y,&p2x,&p2y);
    scanf("(%d,%d)",&qx,&qy);
    if((qx-p1x)*(p2y-p1y)==(p2x-p1x)*(qy-p1y)&&min(p1x,p2x)<=qx&&qx<=max(p1x,p2x)&&min(p1y,p2y)<=qy&&qy<=max(p1y,p2y))
     cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

29. MT1179 线段与线段的关系

（1）题目描述
输入2个线段的端点的坐标值x和y，判断两条线是否为平行线。输出YES或者NO。另:不考虑共线情况。

格式

输入格式: 输入整型，空格分隔。按照先起点（x,y)，空格，再终点(x,y)的次序。每行一个线段的信息。
.
输出格式: 输出YES或者NO

样例1

输入格式:
(-20,20) (-20,-10)
(0,0) (5,0)
.
输出格式: NO

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int a,b,c,d,aa,bb,cc,dd;
    scanf("(%d,%d) (%d,%d)\n",&a,&b,&c,&d);
    scanf("(%d,%d) (%d,%d)",&aa,&bb,&cc,&dd);
    if((d-b)*(cc-aa)==(dd-bb)*(c-a)) cout<<"YES";
    else cout<<"NO";
    return 0;
}

30. MT1180 两条线段

（1）题目描述
输入2个线段的端点的坐标值x和y (x,y不重合)，判断两条线段是否交叉，输出YES或者NO。

格式

输入格式: 输入整型，空格分隔。按照先起点(x,y)，空格，再终点(x,y)）的次序。每行一个线段的信息。
.
输出格式: 输出YES或者NO

样例1

输入格式:
(-20,20) (-20,-10)
(0,0) (5,0)
.
输出格式: NO

（2）参考代码

#include<stdio.h>
#include<stdlib.h>
int judge(int Ax1,int Ay1,int Ax2,int Ay2,int Bx1,int By1,int Bx2,int By2);
int main()
{
    int Ax1,Ay1,Ax2,Ay2;
    int Bx1,By1,Bx2,By2;
    scanf("(%d,%d) (%d,%d)",&Ax1,&Ay1,&Ax2,&Ay2);
    scanf("(%d,%d) (%d,%d)",&Bx1,&By1,&Bx2,&By2);
     if(judge(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2))
        printf("YES\n");
     else
        printf("NO");
    return 0;
}
int max(int x, int y){
    if(x>y) y=x;
    return y;
}

int min(int x, int y){
    if(x<y) y=x;
    return y;
}

int judge(int Ax1,int Ay1,int Ax2,int Ay2,int Bx1,int By1,int Bx2,int By2)
{
    if(
        ( max(Ax1,Ax2)>=min(Bx1,Bx2)&&min(Ax1,Ax2)<=max(Bx1,Bx2) )&&  //判断x轴投影
        ( max(Ay1,Ay2)>=min(By1,By2)&&min(Ay1,Ay2)<=max(By1,By2) )    //判断y轴投影
    )
    {
        if(
            ( (Bx1-Ax1)*(Ay2-Ay1)-(By1-Ay1)*(Ax2-Ax1) ) *          //判断B是否跨过A
            ( (Bx2-Ax1)*(Ay2-Ay1)-(By2-Ay1)*(Ax2-Ax1) ) <=0 &&
            ( (Ax1-Bx1)*(By2-By1)-(Ay1-By1)*(Bx2-Bx1) ) *          //判断A是否跨过B
            ( (Ax2-Bx1)*(By2-By1)-(Ay2-By1)*(Bx2-Bx1) ) <=0
        )
        {
            return 1;
        }
        else
            return 0;
    }
    else
        return 0;
}

31. MT1181 圆包含

（1）题目描述
输入2个圆的圆心的坐标值(x，y)和半径，判断断一个圆是否完全包含另一个圆，输出YES或者NO。另:内切不算做完全包含。

格式

输入格式: 输入整型，空格分隔。每行输入一组信息。
.
输出格式: 输出YES或者NO

样例1

输入格式:
-20 20 50
50 50 1
.
输出格式: NO

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int x1,x2,y1,y2,r1,r2,r3;
    float l;
    scanf("%d%d%d%d%d%d", &x1,&y1,&r1,&x2,&y2,&r2);
    l = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
    if(r1>r2){
        if(r2+l<r1) cout<<"YES";
        else cout<<"NO";
    }else{
        if(r1+l<r2) cout<<"YES";
        else cout<<"NO";
    }
    return 0;
}

32. MT1182 圆相交

（1）题目描述
输入2个圆的圆心的坐标值(x，y)和半径，判断2个圆是否相交，输出YES或者NO。

格式

输入格式: 输入整型，空格分隔。每行输入一组信息。
.
输出格式: 输出YES或者NO

样例1

输入格式:
-20 20 50
50 50 1
.
输出格式: NO

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    double x1,x2,y1,y2,r1,r2;
    cin >> x1 >> y1 >> r1;
    cin >> x2 >> y2 >> r2;
    double r=r1+r2;
    double dis=sqrt(pow(x1-x2,(double)2)+pow(y1-y2,(double)2));
    if(r<=dis || abs(r1-r2)>=dis) cout<<"NO";
    else cout<<"YES";
    return 0;
}

33. MT1183 矩形包含

（1）题目描述
输入2个矩形的左上角和右下角两个点的坐标值(x，y)，判断2个矩形是否相互包含(一个在另一个内部，边框不重叠)，输出YES或者NO。矩形的边应与x，y轴相平行。

格式

输入格式: 输入整型，空格分隔。每行输入一组信息。
.
输出格式: 输出YES或者NO

样例1

输入格式:
-20 20 20 -10
-10 10 10 -5
.
输出格式: YES

（2）参考代码

#include<stdio.h>
int main() 
{ 
    int x1, y1,x2,y2,a1,b1,a2,b2;
    scanf("%d %d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&a1,&b1,&a2,&b2);
    if(x1<a1&&y1>b1&&x2>a2&&y2<b2) printf("YES");
    else if(x1>a1&&y1<b1&&x2<a2&&y2>b2) printf("YES");
    else printf("NO");
    return 0; 
}

34. MT1184 矩形相交

（1）题目描述
输入2个矩形的左上角和右下角两个点的坐标值(x，y)，判断2个矩形是否相交，输出YES或者NO。矩形的边应与x， y轴相平行。假定输入坐标能顺利构成矩形，不考虑无效矩形的情况。

格式

输入格式: 输入整型，空格分隔。每行输入一组信息。
.
输出格式: 输出YES或者NO

样例1

输入格式:
-20 20 20 -10
-10 10 10 -5
.
输出格式: NO

（2）参考代码

#include <bits/stdc++.h>
using namespace std;
int a[100];
int b[100];
int main()
{
    for(int i= 0; i <4; i++) cin >> a[i];
    for(int i= 0; i < 4;i++) cin >> b[i];

    int x1 = max(a[0],b[0]);
    int x2 = min(a[2],b[2]);


    int y1 = max(a[3],b[3]);int y2 = min(a[1],b[1]);
    int lenx = x2- x1;
    int leny = y2 -y1;
    int flag = 0;

    if(min(lenx,leny)==0&&max(lenx,leny)>0) flag = 1;
    if(lenx > 0 && leny > 0){
        flag = 1;
        if(b[0] > a[0] && b[1] < a[1] && b[2] < a[2] && b[3] > a[3]) flag=0;
    }

    if(flag == 1 ) puts("YES");
    else puts("NO");
}

35. MT1185 while循环

（1）题目描述
请编写一个简单程序，从小到大输出所有小于8的正整数和O（从0开始输出)。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    for(int i=0;i<8;i++){
        cout<<i<<" ";
    }
    return 0;
}

36. MT1186 do-while循环

（1）题目描述
请编写一个简单程序，从大到小输出所有小于n的正整数，直到0为止(不含0)。n从键盘输入

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    cin >> n;
    for(int i=n;i>0;i--){
        cout<<i<<" ";
    }
    return 0;
}

37. MT1187 累加和

（1）题目描述
从1累加到10，输出累加和。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    cout<<55;
    return 0;
}

38. MT1188 平均值

（1）题目描述
请编写一个简单程序，随机输入n个数字，输出他们的平均值

格式

输入格式: 输入分两行，第一行输入n，第二行输入n个float型数据，空格分隔
.
输出格式: 输出float型，空格分隔，保留2位小数

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    float a[n+1],sum=0,avg;
    cin >> n;
    for(int i=0;i<=n;i++){
        cin >> a[i];
        sum+=a[i];
    }
    avg=sum/n;
    printf("%.2f",avg);
    return 0;
}

39. MT1189 正负数的和

（1）题目描述
编写程序先输入n，再输入n个实数并分别统计正数的和、负数的和，然后输出统计结果。

格式

输入格式: 输入分两行，第一行输入整数n，第二行输入n个实数，空格分隔。
.
输出格式: 输出正数的和，和负数的和，实型，中间一个空格

样例1

输入格式:
4
1 -3 0.5 -2
.
输出格式: 1.500000 -5.000000

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n;
    double a[50],zn=0,fn=0;
    cin >> n;
    for(int i=0;i<n;i++){
        scanf("%lf",&a[i]);
        if(a[i]<0) fn+=a[i];
        else zn+=a[i];
 
    }
    printf("%lf %lf",zn,fn);
    return 0;
}

40. MT1190 分数乘法

（1）题目描述
输入5组分数，对他们进行乘法运算，输出结果。不考虑分母为0等特殊情况。

格式

输入格式: 输入整型，每组一行，如样例所示。
.
输出格式: 输出计算结果实型，如样例所示。

样例1

输入格式:
1/2 1/4
2/3 1/7
3/5 2/7
3/13 2/5
1/9 11/15
.
输出格式:
0.125000
0.095238
0.171429
0.092308
0.081481

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    double x1,y1,x2,y2;
    for(int i=0;i<5;i++){
        scanf("%lf/%lf %lf/%lf",&x1,&y1,&x2,&y2);
        printf("%lf\n",(x1*x2)/(y1*y2));
    }
    return 0;
}

小结(三)

典型范例：
MT1173、MT1174(ceil()取整函数)、MT1177、MT1178、MT1179
MT1180、MT1181、MT1182、MT1183、MT1184

41. MT1191 减半

（1）题目描述
输入两个值N和M，输出N做M次减半后的值。比如100，减半后依次为50，25,12...，减半3次后是12。输入不考虑0，负数或者其他特殊情况。

格式

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

样例1

输入格式: 100 3
.
输出格式: 12

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,m;
    cin >>n>>m;
    for(int i=0;i<m;i++) n/=2;
    cout<<n;
    return 0;
}

42. MT1192 翻倍

（1）题目描述
输入两个值N和M。输出N做M次翻倍后的值。比如12，翻倍后依次为24，48,96...。输入不考虑0，负数或者其他特殊情况。

格式

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

样例1

输入格式: 12 3
.
输出格式: 96

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,m;
    cin >>n>>m;
    for(int i=0;i<m;i++) n*=2;
    cout<<n;
    return 0;
}

43. MT1193 偶数的平方和

（1）题目描述
输入正整数N，求前N个偶数的平方和。不考虑溢出。

格式

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

样例1

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

备注：

本题第一个偶数从2起算

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,sum=0,num;
    cin >> n;
    for(int i=0;num<=n;num++){
        sum+=i*i;
        i=i+2;
    }
    cout<<sum;
    return 0;
}

44. MT1194 奇数的平方和

（1）题目描述
输入正整数N，求前N个奇数的平方和。不考虑溢出。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,sum=1,num;
    cin >> n;
    for(int i=3;num<n-1;num++){
        sum+=i*i;
        i=i+2;
    }
    cout<<sum;
    return 0;
}

45. MT1195 公式求和

（1）题目描述
输入正整数N和M，按照下列公式求和。
在这里插入图片描述

格式

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

样例1

输入格式: 2 4
.
输出格式: 0.42361

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,m;
    double sum=0;
    cin >> n >> m;
    for(int i=n;i<=m;i++){
        sum+=1.0/(i*i);
    }
    printf("%.5lf",sum);
    return 0;
}

46. MT1196 阶乘

（1）题目描述
请编写一个简单程序，输入正整数n，输出n的阶乘。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,res=1;
    cin >> n;
    for(int i=1;i<=n;i++){
        res*=i;
    }
    printf("%d!=%d",n,res);
    return 0;
}

47. MT1197 阶乘和

（1）题目描述
求1!+2!+3!+...+n!

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,sum=0;
    cin >> n;
    for(int j=1;j<=n;j++){
        int res=1;
        for(int i=1;i<=j;i++){
            res*=i;
        }
        sum+=res;
    }
    printf("%d",sum);
    return 0;
}

48. MT1198 阶乘差

（1）题目描述
求1!-2!-3!-...-n!

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,sum=1;
    cin >> n;
    for(int j=2;j<=n;j++){
        int res=1;
        for(int i=2;i<=j;i++){
            res*=i;
        }
        sum-=res;
    }
    printf("%d",sum);
    return 0;
}

49. MT1199 公式计算

（1）题目描述
输入正整数n和r，计算公式(n!)/ (n-r)!。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int main( )
{
    int n,r;
    double res=1;
    cin >> n >> r;
    for(int i=n-r+1;i<=n;i++) res*=i;
    printf("%.2lf",res);
    return 0;
}

50. MT1200 常数e

（1）题目描述
常数e的值可以表示为无穷级数: e=1+1/1!+1/2!+1/3! +... 1/n!编写一个程序，计算e的值，其中n是用户输入的整数。输入不考虑0，负数或者其他特殊情况。

格式

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

样例1

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

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;

int fact(int n){
    return n>1?n*fact(n-1):1;
}
int main( )
{
    int n,r;
    double res=1;
    cin >> n >> r;
    for(int i=1;i<=n;i++) res+=1.0/fact(i);
    printf("%.2lf",res);
    return 0;
}

结语

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

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

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

算法竞赛入门【码蹄集新手村600题】(MT1151-1200）

算法竞赛入门【码蹄集新手村600题】(MT1151-1200）

前言

为什么突然想学算法了？

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

目录

1. MT1151 韩信生气

2. MT1152 韩信又生气了

3. MT1153 真因子

4. MT1154 缺数

5. MT1155 单位矩阵

6. MT1156 稀疏矩阵

7. MT1157 矩阵相等

8. MT1158 分解

9. MT1159 指定集合

10. MT1160 尾数为零

11. MT1161 N的零

12. MT1162 数组最大公约数

13. MT1163 孪生质数

小结(一)

14. MT1164 最大数字

15. MT1165 卡罗尔数

16. MT1166 自守数

17. MT1167 自守数II

18. MT1168 阶乘数

19. MT1169 平衡数

20. MT1170 四叶玫瑰数

21. MT1171 幻数

小结(二)

22. MT1172 完美数字

23. MT1173 魔数

24. MT1174 A的B次方

25. MT1175 网球比赛

26. MT1176 两个点的距离

27. MT1177 三角形

28. MT1178 点与线段的关系

29. MT1179 线段与线段的关系

30. MT1180 两条线段

31. MT1181 圆包含

32. MT1182 圆相交

33. MT1183 矩形包含

34. MT1184 矩形相交

35. MT1185 while循环

36. MT1186 do-while循环

37. MT1187 累加和

38. MT1188 平均值

39. MT1189 正负数的和

40. MT1190 分数乘法

小结(三)

41. MT1191 减半

42. MT1192 翻倍

43. MT1193 偶数的平方和

44. MT1194 奇数的平方和

45. MT1195 公式求和

46. MT1196 阶乘

47. MT1197 阶乘和

48. MT1198 阶乘差

49. MT1199 公式计算

50. MT1200 常数e

结语

热门文章

最新文章

相关课程

相关电子书

相关实验场景