学校2020年第一届新生赛 反思&总结

26
26*26 702
今年我们学校办了一场声势浩大的程序设计新生赛,吸引了学校一百三十多号新生前来参赛,可喜可贺。
作为弱鸡,为了第一时间围观dalao的风范,切身体会被dalao吊打的感觉,我上周日八点半就起了床,饭也没吃脸也没洗,打开浏览器就开始等待比赛开始。
九点的钟声准时敲响,比赛准时开始。

出了啥题

学长老早之前就说了,这次新生赛题目简单。

题目很简单.jpg

真的嘛?比赛一开始,首先点击题目按钮,让我们来看看我们亲爱的老师给我们准备了啥题目。

A 序列和

题述

求出一个整数序列每一位的和

输入
一个数字组成的串
输出
输出每一位数的和

输入样例1

1234

输出样例1

10

提示

1+2+3+4=10

解析

第一题,好家伙,这个题还是可以做一做的嘛!只需要遍历一下输入的数组就OK了。

#include<stdio.h>
#include<string.h>

int main() {
    char s[666];
    int sum = 0;
    scanf("%s", s);
    for (int i = 0; i < strlen(s); ++i) {
        sum += (s[i] - '0');
    }
    printf("%d", sum);
    return 0;
}

B integer endpoints

好家伙,整了个英文题目

题述

You are given a set of n segments on the axis Ox.each segment has integer endpoints between

1 and m inclusive. Segments may intersect, overlap or even coincide with each other.

Each segment is characterized by two integers li and ri (1<=li<=ri<=m)

— coordinates of the left and of the right endpoints.

Consider all integer points between 1 and m inclusive. Your task is to print all such points that

don't belong to any segment. The point x belongs to the segment [l:r] if and only if l<=x<=r.

Input

The first line of the input contains two integers n and m (1<=n,m<=100)

— the number of segments and the upper bound for coordinates.

The next n lines contain two integers each li and ri (1<=li<=ri<=m) —the endpoints of the i-th segment.

Segments may intersect, overlap or even coincide with each other.

Note, it is possible that li=ri,i.e. a segment can degenerate to a point.

Output

In the first line print one integer k — the number of points that don't belong to any segment.

In the second line print exactly k integers in order from small to large

— the points that don't belong to any segment. All points you print should be distinct.

If there are no such points at all, print a single integer 0 in the first line

Sample Input 1

3 5
2 2
1 2
5 5

**Sample Output 1***

2
3 4

题目理解

现在给你数轴上的几个片段Ox,每个片段的端点取值范围都是整数的1到m,并且每个片段之间可能是相互独立的、重叠的或者是互相包含的。
每个片段都会用两个int类型的量liri(1<=li<=ri<=m)表示,对应着他们的左右端点。
分析所有从1到m的整数点,你的任务就是找出其中不属于任何片段的点。
每个片段都是闭区间。

输入
第一行输入n和m,n表示片段个数
接下来n行表示各个片段

输出
第一行输出这样的点的个数
第二行输出这些点,空格隔开

解析

这道题因为数据范围只是1到100,所以可以直接开一个数组,用来存这个数字有没有被某个区间包含即可。

#include<iostream>

using namespace std;

int main() {
    char b[105] = {0};
    int n, m;
    cin >> n >> m;

    int k = m;

    for (int i = 0; i < n; ++i) {
        int li, ri;
        cin >> li >> ri;
        for (int j = li; j <= (ri < m ? ri : m); ++j) {
            if (!b[j]) {
                k -= 1;
                b[j] = 1;
            }
        }
    }

    cout << k << endl;

    for (int i = 1; i <= m; ++i) {
        if (!b[i])
            cout << i << " ";
    }

    return 0;
}

C 整除

题述

求出整数a到整数b之间有多少个数数位之和为5的倍数

输入
输入一行包含2个整数a,b(0<=a,b<=1000)

输出
输出一个整数

输入样例 1

10 20

输出样例 1

2

提示

14和19的数位之和为5和10,符合条件

解析

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt(), b = scanner.nextInt();
        int t = 0;
        for (int i = a; i <= b; i++) {
            if (sum(i) % 5 == 0)
                t += 1;
        }
        System.out.println(t);
    }

    //求一个数字的数位和
    public static int sum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

J 2的整数次方

题述

给定一个正整数N,请你判断它能否表示成三个2的非负整数次幂的和,如果能输出"YES",否则输出"NO"。(不包含引号)

输入

输入一个正整数N(1<=N<=10e9)

输出

输出一行字符串"YES"或"NO"(不包含引号)

输入样例 1

10

输出样例 1

YES

输入样例 2

2

输出样例 2

NO

提示

2^2+2^2+2^1=10

解析

这道题我的思路是转换为二进制来思考。具体需要考虑这几个问题:

二的正次方数的二进制

2的0次方是1,二进制是1。那么其他的2的正次方数字呢?

2的1次方是2,二进制是10
2的2次方是4,二进制是100
2的3次方是8,二进制是1000
2的4次方是16,二进制是10000
2的5次方是32,二进制是100000

很显然通过观察可以得出结论,2的正次方数的二进制表示起来,格式是开头是1,后面有幂次那么多个的0。比如32的二进制,由于它是2的5次方,所以他是1后面跟5个0。

这其实很好理解为什么,如果我们有x=1,现在我们x<<=1,就是把x往左移一位,也就相当于乘2,左移的规则就是右侧空位补0,那不正好跟我们刚才得出的结论相一致嘛?

我们还可以偶然间得出这样的结论,即,如果想要把一个数字乘2,可以x*2,但是这样操作还有更高效快速的方法,就是x<<=1,也就是乘了2的一次方,如果想乘4,就是x<<=2

两个二的非负次方数相加会出现什么?

先考虑三个不相等的二的正次方数相加

如果有这样一个数(都是二进制)10010000,相加的话二进制表示很显然应该是10100
不信我们可以转换成十进制试一试,100(2)=410000(2)=1610100(2)=204+16显然就是20,这是正确的。

诶,我们可以发现这样的规律:

如果有三个不相等的二的次方数相加,那么结果用二进制表示,肯定会有三个1,其他位上都是0。

想一想是不是这个道理!!!

三个不一样的二的非负次方(算上1了)

继续思考,拓展到二的非负次方,也是这样子,因为2的0次方是1,这完全不影响我们的结论。

要是出现两个相等或者三个都等的情况呢?

观察(二进制表示)1+1=10,可以发现,其实我们可以任意拆开任意一个1。

什么叫做能拆开任意一个1?看(二进制表示的)数字10001。我们发现这个数字里有2个1,根据上面的结论我们可以得出他可以由两个数字(二进制表示)100001相加计算得出。
我想说,如果我们得出这个结论了,我们一定可以得出这个结论:这个数字必然能表示成三个二的非负次方数字相加,其中有两个数字相同。

我凭什么这样讲?因为,第一个1是可以拆的。
为啥呢?

我不看二进制了,我看十进制,显然二进制数10001可以表示成二进制的100001的和。
行,2进制下就是17=16+1
我们小学就学过16=8*2,因为16是个二的正次方的数字,所以他肯定有个因数是2,我们这样表示显然是没问题,根据乘法的定义,这意味着16=8+8,而8不也是2的正次方数嘛?

所以二进制下我们看到10001,个位上的1我们拿他没办法,不能继续拆了,其他位上的1都能继续拆。
举例验证:
如果十位上有个1,可以理解为10=1+1,也就是二进制的2=1+1,没问题,可以拆。
如果百位上有个1,可以理解为100=10+10,也就是二进制的4=2+2,没问题,可以拆。
如果千位上有个1,可以理解为1000=100+100,也就是二进制的8=4+4,没问题,可以拆。
后面都不用试了,很明显,都能拆呀!

问题迎刃而解

OK知道了这个道理回到这道题本身,这道题怎么做?

首先,要验证n是不是可以表示成三个二的非负次方数字相加,那可以先把n表示成2进制。根据我们刚才的结论,我们要判断的重要标准就是二进制数字里究竟有几个1。

这里需要讨论几个特殊情况,1的二进制有1个1,2的二进制有1个1,这俩数字需要特殊处理,它们不能表示成三个二的非负次方数之和。3(3=1+1+1)和之后的数字就可以了。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), k = 0;
        if(n<=2){
            System.out.println("NO");
            return;
        }
        while (n > 0) {
            //这里是在十进制的角度下数的二进制1的个数
            //意思跟上面是一样的
            //因为我不太会写进制转换所以就这样写了
            if (n % 2 == 1)
                k += 1;
            n /= 2;
        }
        System.out.println(k <= 3 ? "YES" : "NO");
    }
}
上一篇
下一篇