流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

暑三集训--总结

　　作者: 流离之人追逐幻影　　　　发表时间：2019-08-30 22:29:28 浏览：228　|　评论：0　

1.最大公约数和最小公约数
```
描述

输入2个正整数x0，y0（2<=x0<100000，2<=y0<=1000000），求出满足下列条件的P，Q的个数。

条件：
1. P，Q是正整数；
2. 要求P，Q以x0为最大公约数，以y0为最小公倍数。

试求：
满足条件的所有可能的两个正整数的个数。
```
```
输入
每个测试文件包含不超过5组测试数据，每组两个正整数x0和y0（2<=x0<100000，2<=y0<=1000000）。

输出
对于每组输入数据，输出满足条件的所有可能的两个正整数的个数。
```
```
下面是对样例数据的说明：
输入3 60

此时的P Q分别为:
3 60
15 12
12 15
60 3
所以，满足条件的所有可能的两个正整数的个数共4种。
```
```
输入样例 1

3 60
输出样例 1

4
```
题解：
```
	正常的思路是两层循环，定义好上下限，分别将两个数带入gcd算法和gbd算法，令其等于P，Q,不过这样时间复杂度会比较差劲，（两层循环+递归）。
	因为求出P，就可以知道Q,所以就可以少用一个递归算法，由于P,Q的相关性，两层循环可以减少一层，关键在条件限制，
	p<=p*q/i&&p*q/i<=q&&gcd(i,p*q/i)==p&&q%i==0
	前两个条件限制i范围，p*q/i 肯定大于等于最大公约数，小于等于最小公倍数
	gcd（i,p*q/i） 在i<p*q/i时 最后一个条件不起作用，反之，需要对其后的i的进行验证。
	时间复杂度不仅需要平时多学习方法，更得自己平时勤加练习，每一次写同一种算法都可以思考，让其逻辑更加清晰，代码更加精简，更能学会控制好时间复杂度。
	不过如果能直接暴力解决的，而没有其他想法时，就先用它解决，事后在进行总结反思，有没有更加精巧的解题方法。
```
代码：
```
#include<stdio.h>
int gcd(int a, int b) {
    if(a%b==0)
        return b;
    else
        return gcd(b,a%b);
}
int main(){
    int i,p,q;
    while(scanf("%d %d",&p,&q)!=EOF){
        int sum=0;
        for(i=p;i<=q;i+=p)
            if(p<=p*q/i&&p*q/i<=q&&gcd(i,p*q/i)==p&&q%i==0)
                sum++;
        printf("%d\n",sum);
    }
return 0;
}

```
2.田忌赛马
```
描述

这是中国历史上一个著名的故事。“那是大约2300年前。田忌将军是齐国的高官。他喜欢和国王和其他人一起玩赛马。”“田和王都有三匹不同等级的马，即下等马、中等马和高等马。规则是比赛中有三轮；每匹马必须一轮使用。一轮的赢家从输家那里拿走200银元，打平则什么都不做。”“国王是这个国家最有权力的人，他的马非常好，每一个等级他的马都比田的好。结果，每次国王从田里拿走六百银元。””田忌对此并不高兴，直到他遇到了孙膑，中国历史上最著名的将军之一。田忌用了一个小把戏，在下一场比赛中赢回了两百银元和这样的恩惠。”“这是一个相当简单的把戏。利用他的下等赛马对抗国王的高等赛马，他们肯定会输掉那一轮。但是他的中等赛马打败了国王的下等赛马，他的高等赛马打败了国王的中等赛马。多么简单的把戏。你觉得中国的高官田忌怎么样？”如果田忌现在住在这里，他肯定会自嘲。

更重要的是，如果他现在参加ACM竞赛，他可能会发现赛马问题可以简单地被视为在二分图中找到最大匹配。在这个问题中，你被要求写一个程序来解决这个特殊的匹配问题。
```
```
输入
输入由多达50个测试用例组成。每种情况都从第一行的正整数n(n≤1000)开始，即每边的马数。第二行的下n个整数是田忌的马的速度。第三行接下来的n个整数是国王的马的速度。输入以最后一个测试用例后只有一个0的行结束。

输出
对于每种输入情况，输出一行包含一个数字，这是田忌所能得到的最高金额，单位为银元。
```
```
输入样例 1

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
输出样例 1

200
0
0
```
题解：
```
经典贪心算法：
贪心策略：
一、当田忌最快的马比国王最快的马快时，用田忌最快的马赢国王最快的马。 
二、当田忌最快的马比国王最快的马慢时，用田忌最慢的马输给国王最快的马。
三、当田忌最快的马跟国王最快的马一样快时，分情况。
1、当田忌最慢的马比国王最慢的马快，那么用田忌最慢的马赢国王最慢的马
2、当田忌最慢的马比国王最慢的马慢，那么用田忌最慢的马输给国王最快的马
3、当田忌最慢的马跟国王最慢的马相等的时候，用田忌最慢的马跟国王最快的马比
```
代码：
```
#include<bits/stdc++.h>
using namespace std;
int a[1001],b[1001];
int main(){
    int n;
    while(cin>>n&&n){
        for(int i=0; i<n; i++)
            cin>>a[i];
        for(int i=0; i<n; i++)
            cin>>b[i];
        sort(a,a+n);
        sort(b,b+n);
        int s=0;
        for(int i=0,j=0,k=n-1,l=n-1; i<=k;){
            if(a[i]>b[j])s++,i++,j++;  // 最慢斗最慢
            else if(a[k]>b[l])s++,k--,l--;  // 最快斗最快
            else{// 其余情况都用田最慢的马去跟齐最快的马比
                if(a[i]<b[l])s--;
                if(a[i]>b[l])s++;
                i++,l--;
            }
        }
        cout<<s*200<<endl;
    }
    return 0;
}
```
3.呼噜声合奏曲
```
描述

在广东，有个美丽的地方，它位于中国大陆南端、广东省西南部，介于东经109°31′～110°55′，北纬20°12′～21°35′之间，总面积13225.44平方公里。 属于热带北缘季风气候，终年受海洋气候的调节，冬无严寒，夏无酷暑，亚热带作物及海产资源丰富，别称“港城”。没错，这个地方就是湛江，在湛江，有一个大学叫做岭南师范学院，简称“岭南师院”，是一所全日制普通本科高等院校，是广东省新增硕士学位授权立项建设单位、广东首批普通本科转型试点高校、省市共建高校、广东省特殊教育教师发展联盟理事长单位、首批民政部社会工作专业人才培训基地。岭南师范学院办学历史可追溯到1636年创办的雷阳书院，1902年，学校改建为雷州中学堂，1904年始设师范科教育，1935年改名为广东省立雷州师范学校，1978年正式改建为雷州师范专科学校，1991年升格并更名为湛江师范学院，2014年更为岭南师范学院。而在这么美丽的学校里有一栋叫做新民的宿舍楼，每天夜里，新民苑的某间宿舍里总会传出奇怪的声音，十分吓人，但如果你仔细听听，你就会发现其实那是几重呼噜声混杂而成的声音。在这个宿舍里，有三人睡觉时会打呼噜，分别是小陈、小李、小张，其中，小陈一周有四天不睡觉，分别是周一、周三、周四和周五；小李每月日期尾数为5的他都不睡觉；小张生活很规律，每天都会按时睡觉。其中三人一起打呼噜的声音被其舍友称之为呼噜合奏曲，现给你一个年份，问这一年他们的舍友可以欣赏到几次三人的呼噜合奏曲。
```
```
输入
输入年份n（2000<=n<=2100）。

输出
输出这一年舍友可以听到呼噜合奏曲的总天数，每行一个。
```
```
输入样例 1

2000
2019
输出样例 1

140
143
```
```
注意，本次实验有多组试例。
提示：2000年的1月1号是星期六
```
题解：
```
难度较低，就是有点耗时间。模拟每一年的第一天是星期几时，写的有点久。事后发现可以用一条公式解决。
基姆拉尔森计算公式：W= (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400) mod 7
```
代码：
```
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,y,j,st,d,s;
    int ct;
    int M[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    while(cin>>n){
            st=6;
            y=j=0;
            ct=0;
            d=1;
        for(int i=0;i<n-2000;i++){
            y+=365;
            if(j%4==0)
                y++;
            j++;
        }
        st+=y%7;
        if(st>7)st-=7;
        //计算1,1 星期几
        s=st;
        if((n-2000)%4==0){y=366;M[2]=29;}
        else {y=365;M[2]=28;}
    int  ctt=0;
        for(int m=1;m<=12;m++){
                ctt=0;
            for(int i=1;i<=M[m];i++){
                if(s>7)s=1;
                if(i%10!=5&&(s==2||s==6||s==7)){
                    ct++;
                    ctt++;
                }
                s++;
            }
        }
        cout<<ct<<endl;
    }
    return 0;
}
```

4.数数有多少个矩形
```
描述

给你一个高为n ，宽为m列的网格，计算出这个网格中有多少个矩形（正方形是特殊的矩阵），下图为高为2，宽为4的网格.
```
![](/image_editor_upload/20190830102712_29924.png)
```
输入
第一行输入一个t, 表示有t组数据，然后每行输入n,m,分别表示网格的高和宽 ( n < 100 , m < 100).

输出
每行输出网格中有多少个矩形.
```
```
输入样例 1

2
1 2
2 4
输出样例 1

3
30
```
题解：
```
找规律推公式，我喜欢。
对于一行：其规律为1+2+3+4+...;sum1=m*(m+1)/2
列同理 sum1=n*(n+1)/2;
其规律必和这两个数相关。
逐步推算验证数据，得出sum=sum1*sum2;
做这类题目我都是求出相关量来逐一推演，逻辑推算总是要建立在正确的数据上。
```
代码：
```
#include<stdio.h>
int main(){
    int t;
    while(scanf("%d",&t)!=EOF){
        while(t--){
            int n,m;
            int sum=0;
            scanf("%d %d",&n,&m);
            sum=(m*(m+1)/2)*(n*(n+1)/2);
            printf("%d\n",sum);
        }
    }
    return 0;
 }
```
5.水题，不记录了
6.出现次数
```
描述

统计某个给定范围[L, R] 的所有整数中，数字n出现的次数。比如输入2 22 2 ，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。
```
```
输入
每组输入数据共1行，为三个正整数L、R和n，之间用一个空格隔开。（1≤L≤R≤10000,0<=n<=9）

输出
每组输出共1行，表示数字n出现的次数。
```
```
输入样例 1

2 22 2
3 33 3
1 100 0
输出样例 1

6
8
11
```
题解：也比较水，，，，。
代码：
```
#include<bits/stdc++.h>
using namespace std;

int main(){
    int L,R,N;
    int flag,ct;
    while(cin>>L>>R>>N){
            ct=0;
        for(int i=L;i<=R;i++){
            flag=i;
            while(flag){
                if(flag%10==N)
                    ct++;
                flag/=10;
            }
        }
        cout<<ct<<endl;
    }

return 0;
}
```
7.均分糖果
```
描述

有N堆糖果，编号分别为1，2，...，N。每堆上有若干个，但糖果总数必为N的倍数。可以在任一堆上取若干个糖果，然后移动。

移动规则为：在编号为1的堆上取的糖果，只能移到编号为2的堆上；在编号为N的堆上取的糖果，只能移到编号为N-1的堆上；其他堆上取的糖果，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上糖果数都一样多。

例如N=4，4堆糖果数分别为：

①　9　②　8　③　17　④　6

移动3次可达到目的：

从③取4个糖放到④（9 8 13 10）->从③取3个糖放到②（9 11 10 10）->从②取1个糖放到①（10 10 10 10）。
```
```
输入
每个测试文件包含多组测试数据，每组输入的第一行输入一个整数N（1<=N<=100），表示有N堆糖果。

接下来一行输入N个整数A1 A2...An，表示每堆糖果初始数，1<=Ai<=10000。

输出
对于每组输入数据，输出所有堆均达到相等时的最少移动次数。
```
```
输入样例 1

4
9 8 17 6
输出样例 1

3
```
题解：
```

```
代码：
```
#include<bits/stdc++.h>
using namespace std;
# define N 105
int val[N];
int Move(int n)
{
    int cnt=0;
    int avg=0;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&val[i]);
        avg+=val[i];
    }
    avg/=n;
    for(int i=0;i<n-1;i++)
    {
        val[i]-=avg;
        if(val[i]!=0)
        {
            cnt++;
            val[i+1]+=val[i];
        }
    }
    return cnt;
}
int main()
{
    int t;
    int sum;
    while(scanf("%d",&t)!=EOF){
        sum=Move(t);
        cout<<sum<<endl;
    }
    return 0;
 }

```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

暑三集训--总结

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题8.2 （Java代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

The 3n + 1 problem （C语言代码）

敲七（C语言代码）

排序算法（选择，插入，冒泡）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

暑三集训--总结

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题8.2 （Java代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

The 3n + 1 problem （C语言代码）

敲七 （C语言代码）

排序算法（选择，插入，冒泡）

　　评论区

敲七（C语言代码）