2019.12.8蓝桥杯校赛writeup

2019.12.8蓝桥杯校赛writeup

十二月 08, 2019

一次蓝桥杯的writeup

说实话和去年的蓝桥杯校赛比起来，难度简单许多，
很多经典数据结构都没有考
那废话不多说，直接进入正题吧

  1. 问题描述
    　　不超过19000的正整数中，与19000互质的数的个数是多少？
    答案提交
    　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

Solve: 这是一道填空题,比较简单.说白了就是欧拉筛的用法,没什么好说的,代码如下:

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
#include <stdio.h>

int euler(int n)
{
    int  res = n;
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            res = res / i * (i - 1);
            while(n % i == 0){
                n /= i;
            }
        }
    }
    if(n > 1)
    {
        res = res / n * (n - 1);
    }
    return res;
}

int main(int argc, char** argv)
{
    int n;
    scanf("%d", &n);
    printf("%d", euler(n));
    getchar();
    return 0;
}

结果为7200

  1. 问题描述
    　　请问十六进制数1949对应的十进制数是多少？请特别注意给定的是十六进制，求的是十进制。
    答案提交
    　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

Solve: 进制转换题,一道送分题,非常的简单,python一行代码搞定,如下:

1
print(int('1949', 16))

结果为6473

  1. 问题描述
    　　一棵包含有2019个结点的树，最多包含多少个叶结点？
    答案提交
    　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

Solve: …..这个题目不会的,建议重新看一遍数据结构…….

结果为2018

  1. 问题描述
    　　由1对括号，可以组成一种合法括号序列：()。
    　　由2对括号，可以组成两种合法括号序列：()()、(())。
    　　由4对括号组成的合法括号序列一共有多少种？
    答案提交
    　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

Solve: 乍一看是一道递归,但是比赛的时候懒得写了,故直接手算,解决思路如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

结果为14

  1. 问题描述
    　　小明非常不喜欢数字 2，包括那些数位上包含数字 2 的数。如果一个数的数位不包含数字 2，小明将它称为洁净数。
    　　请问在整数 1 至 n 中，洁净数有多少个？
    输入格式
    　　输入的第一行包含一个整数 n。
    输出格式
    　　输出一行包含一个整数，表示答案。
    样例输入
    30
    样例输出
    18
    评测用例规模与约定
    　　对于 40% 的评测用例，1 <= n <= 10000。
    　　对于 80% 的评测用例，1 <= n <= 100000。
    　　对于所有评测用例，1 <= n <= 1000000。

Solve: 由于我选的是C/C++,所以编程题都是用C写的.这题没什么难点,故直接暴力解得(遇事不决走暴力~),代码如下:

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
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv)
{
    int n;
    int count = 0;
    scanf("%d", &n);
    for(int i = 1;i <= n; i++){
        int b = i;
        while(1){
            if(b == 0)
                break;
            if(b % 10 == 2){
                count += 1;
                break;
            }
            b = b / 10;
        }
    }
    count = n - count;
    printf("%d", count);
    getchar();
    return 0;
}
  1. 问题描述
    　　给定一个单词，请使用凯撒密码将这个单词加密。
    　　凯撒密码是一种替换加密的技术，单词中的所有字母都在字母表上向后偏移3位后被替换成密文。即a变为d，b变为e，…，w变为z，x变为a，y变为b，z变为c。
    　　例如，lanqiao会变成odqtldr。
    输入格式
    　　输入一行，包含一个单词，单词中只包含小写英文字母。
    输出格式
    　　输出一行，表示加密后的密文。
    样例输入
    lanqiao
    样例输出
    odqtldr
    评测用例规模与约定
    　　对于所有评测用例，单词中的字母个数不超过100。

Solve: …..又是一道送分题,凯撒密码都不知道写了多少次了…..代码如下:

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char** argv)
{
    char passwd[100];
    int i,j,k,t,move;
    gets(passwd);
    move = 3;
    for(i=0; i<strlen(passwd); i++)
    {
        if(passwd[i] >= 'A' && passwd[i] <= 'Z')
        {
            passwd[i] = ((passwd[i]-'A')+move)%26+'A';
        }
        else if(passwd[i] >= 'a' && passwd[i] <= 'z')
        {
            passwd[i] = ((passwd[i] - 'a') + move) % 26 + 'a';
        }
    }
    printf("%s", passwd);
    printf("\n");
    getchar();
    return 0;
}
  1. 问题描述
    　　给定正整数 n，请问在整数 1 至 n 中，数字中没有数位相同的数有多少个？
    　　例如，当 n=30 时，除开 11 和 22 以外，其他的数都没有数位相同，因此答案为 28。
    输入格式
    　　输入的第一行包含一个整数 n。
    输出格式
    　　输出一行包含一个整数，表示答案。
    样例输入
    30
    样例输出
    28
    评测用例规模与约定
    　　对于 40% 的评测用例，1 <= n <= 1000。
    　　对于 80% 的评测用例，1 <= n <= 100000。
    　　对于所有评测用例，1 <= n <= 1000000。

Solve: 这题….没什么好说的,很基本的一道算法题.要注意:只要有位数相同,就是数位相同,代码如下:

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
#include <stdio.h>
#include <stdlib.h>

int getlen(int a)
{
    int count = 0;
    while (1)
    {
        a = a / 10;
        count++;
        if(a == 0)
        {
            break;
        }
    }
    return count;
}

int main(int argc, char** argv)
{
    int i, j, n, count, signal, semaphore, mode, sema;
    scanf("%d", &n);
    count = n;
    for(i = 1; i < n; i++)
    {
        if(i / 10 == 0)
        {
            continue;
        }
        else
        {
            signal = i;
            semaphore = signal % 10;
            signal = signal / 10;
            for (j = 1; j < getlen(i); j++)
            {
                if(signal == semaphore)
                {
                    count--;
                    break;
                }
                else
                {
                    continue;
                }
                signal = signal / 10;
            }
        }
    }
    printf("%d", count);
    getchar();
    return 0;
}

P.S. 这道题我写的比较的复杂,主要是刚考完操作系统,对semaphore,signal有着独特的情怀=_=,原谅我=w=

  1. 问题描述
    　　小明开了一家花店，这天，有个客户定了非常多的花，按客户的需要，这些花要排成 n 行 m 列。
    　　小明要将这些花运送到客户那，然而由于花太多，需要分两辆车才能装下。
    　　小明怕自己弄错花的顺序，因此在分车的时候，他准备将前面一些列（注意不是行）的花放在第一辆车上，将其实的花放在第二辆车上。
    　　已知每盆花的重量，要使第一辆车和第二辆车尽可能总重量一致，请帮助小明分装这些花，请告诉小明两辆车的重量最小差多少。
    输入格式
    　　输入的第一行包含两个整数 n, m，分别表示行数和列数。
    　　接下来 n 行，每行 m 个正整数，分别表示每盆花的重量。
    输出格式
    　　输出一个整数，表示总重量最接近时两车的重量之差（的绝对值）。
    样例输入
    3 4
    1 2 3 9
    5 6 7 8
    2 3 4 9
    样例输出
    7
    样例说明
    　　将前 3 列放一辆车，后 1 列放一辆车，第一辆比第二辆重 7 。
    评测用例规模与约定
    　　对于 30% 的评测用例，2 <= n, m <= 20。
    　　对于 70% 的评测用例，2 <= n, m <= 100。
    　　对于所有评测用例，2 <= n, m <= 1000，每盆花的重量不超过 1000。

Solve: 终于来了一道比较有兴趣的了,说白了就是先算出每一列的重量和,然后排序,再循环累加比较,具体代码如下:

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char** argv)
{
    int m, n;
    int top = 0, flo = 0;
    int i, j;
    int weight[m];
    int con = 0;
    int min = 9999;
    scanf("%d %d", &n, &m);
    int a[n][m];
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < m; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < n; j++)
        {
            con += a[j][i];
        }
        weight[i] = con;
        con = 0;
    }
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < m; j++)
        {
            if(weight[i] < weight[j])
            {
                weight[i] = weight[i] + weight[j];
                weight[j] = weight[i] - weight[j];
                weight[i] = weight[i] - weight[j];
            }
        }
    }
    top = 0;
    flo = 0;
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < i; j++)
        {
            top += weight[j];
        }
        for(j; j < m; j++)
        {
            flo += weight[j];
        }
        if(min > abs(top - flo))
        {
            min = abs(top - flo);
        }
        else
        {
            continue;
        }
        top = 0;
        flo = 0;
    }
    printf("%d", min);
    getchar();
    return 0;
}
  1. 问题描述
    　　小明用积木搭了一个城堡。
    　　为了方便，小明在搭的时候用的是一样大小的正方体积本，搭在了一个 n 行 m 列的方格图上，每个积木正好占据方格图的一个小方格。
    　　当然，小明的城堡并不是平面的，而是立体的。小明可以将积木垒在别的积木上面。当一个方格上的积木垒得比较高时，就是一个高塔，当一个方格上没有积木时，就是一块平地。
    　　小明的城堡可以用每个方格上垒的积木层数来表示。例如，下面就表示一个城堡。
    　　9 3 3 1
    　　3 3 3 0
    　　0 0 0 0
    　　这个城堡南面和东面都有空地，西北面有一个大房子，在西北角还有一个高塔，东北角有一个车库。
    　　现在，格格巫要来破坏小明的城堡，他施了魔法水淹小明的城堡。
    　　如果水的高度为1，则紧贴地面的那些积木要被水淹，在上面的例子中，有7块积木要被水淹。
    　　如果水的高度为2，则更多积木要被水淹，在上面的例子中，有13块积木要被水淹。
    　　给定小明的城堡图，请问，水的高度依次为1, 2, 3, …., H 时，有多少块积木要被水淹。
    输入格式
    　　输入的第一行包含两个整数 n, m。
    　　接下来 n 行，每行 m 个整数，表示小明的城堡中每个位置积木的层数。
    　　接下来包含一个整数 H，表示水高度的上限。
    输出格式
    　　输出 H 行，每行一个整数。第 i 的整数表示水的高度为 i 时被水淹的积木数量。
    样例输入
    3 4
    9 3 3 1
    3 3 3 0
    0 0 0 0
    10
    样例输出
    7
    13
    19
    20
    21
    22
    23
    24
    25
    25
    评测用例规模与约定
    　　对于 40% 的评测用例，1 <= n, m <= 100，1 <= H <= 100，积木层数不超过100；
    　　对于 70% 的评测用例，1 <= n, m <= 1000，1 <= H <= 1000，积木层数不超过1000；
    　　对于所有评测用例，1 <= n, m <= 1000，1 <= H <= 100000，积木层数不超过1000000000。

Solve: 这个问题也是比较简单的题目了,基本思路和上一题差不多,不过多赘述了,代码如下:

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
56
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char** argv)
{
    int m, n;
    int i, j;
    int h;
    int count;
    scanf("%d %d", &n, &m);
    int a[n][m];
    int height[m * n];
    int len = 0;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < m; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < m; j++)
        {
            if(a[i][j] != 0)
            {
                height[len] = a[i][j];
                len++;
            }
        }
    }
    scanf("%d", &h);
    for(i = 1; i < h + 1; i++)
    {
        count = 0;
        for(j = 0; j < len; j++)
        {
            if (height[j] >= i)
            {
                count += i;
            }
            else if(height[j] < i)
            {
                count += height[j];
            }
        }
        printf("%d", count);
        if(i != h)
        {
            printf("\n");
        }
    }
    getchar();
    return 0;
}
  1. 问题描述
    　　2015年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。
    　　这一次，小明要帮助 n 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。
    　　现在，这 n 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。
    　　小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为 (x_1, y_1) 高度为 h_1 的村庄与坐标为 (x_2, y_2) 高度为 h_2 的村庄之间连接的费用为
    　　sqrt((x_1-x_2)(x_1-x_2)+(y_1-y_2)(y_1-y_2))+(h_1-h_2)*(h_1-h_2)。
    　　在上式中 sqrt 表示取括号内的平方根。请注意括号的位置，高度的计算方式与横纵坐标的计算方式不同。
    　　由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。
    输入格式
    　　输入的第一行包含一个整数 n ，表示村庄的数量。
    　　接下来 n 行，每个三个整数 x, y, h，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。
    输出格式
    　　输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。
    样例输入
    4
    1 1 3
    9 9 7
    8 8 6
    4 5 4
    样例输出
  2. 41
    评测用例规模与约定
    　　对于 30% 的评测用例，1 <= n <= 10；
    　　对于 60% 的评测用例，1 <= n <= 100；
    　　对于所有评测用例，1 <= n <= 1000，0 <= x, y, h <= 10000。

Solve: 本题是本次比赛里最难的一题,基本思路非常简单,但是考验写程序的人是否拥有基本的数据结构的概念,以及对图,prim算法,Kruskal算法的理解.题目大意就是,每个村庄有三个属性,(x, y, h)基本就是坐标轴嘛,然后每个结点间都要直接或间接的和1号节点连接,求怎么样花费最小
这个题一眼看过去,就知道是图论的最小生成树问题,自然而然的就想到了prim算法和Kruskal算法,代码如下:

1

P.S. 写这题的时候,旁边有一个小老弟问我怎么做,我就直接简述了我的想法(还特意问了一下学过数据结构吗,他点了点头.)结果到最后的时候跟我说,”克鲁斯卡尔算法是啥”.真实给我整笑了hhhh

总结一下吧,其实本来难度上并不是很高,可能原因是为了让所有人都适应这个比赛,不过难度确实应该再提高一点比较好.不过这次比赛也有些遗憾,自己的准备不充分也是一部分原因(没有复习结构体导致Kurskal算法纯数组实现,非常的麻烦而且看的头皮发麻),反思一下,为下次做准备.

以上就是我对本次蓝桥杯的所有writeup
有什么写错的地方欢迎指出~
QQ:527430509

  1. 1. 一次蓝桥杯的writeup