Advertisement

2018年第九届蓝桥杯【C++省赛B组】

阅读量：

1. 第几天

在208年元旦这一天相当于全年中的第一天那么在28年5月4日这一天相当于全年中的第几天注意：需要提交的是一个整数不要填写任何多余内容

solution

2000年是闰年，2月29天，所以是31+29+31+30+4=125天。

2. 明码

汉字形状记录于字体库中，在当今技术仍具重要价值。
采用16×16分辨率的技术将每个汉字分解为像素数据，并将这些像素数据编码存储在单个字节中。
因此需要占用32个连续的字节来完整保存一个汉字的信息。
将每个字符转换为其对应的二进制表示形式，并按行排列组织。
每行包含两个相邻的8位单元（即两个连续的字符），共有16行这样的排列组合。
每一行的数据对应一个完整的汉字符号。
题目的关键信息就藏在这些编码数据之中。
这段测试信息共计包含了十个独立汉字符号的数据样本，
每一个都是通过特定编码方式表示出来的基本单元，
你的任务就是通过分析这些编码特征，
找出其中隐藏的关键点，
并据此推断出完整的字体结构。

复制代码 
    4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 
    16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16 
    4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 
    0 -128 64 -128 48 -128 17 8 1 -4 2 8 8 80 16 64 32 64 -32 64 32 -96 32 -96 33 16 34 8 36 14 40 4 
    4 0 3 0 1 0 0 4 -1 -2 4 0 4 16 7 -8 4 16 4 16 4 16 8 16 8 16 16 16 32 -96 64 64 
    16 64 20 72 62 -4 73 32 5 16 1 0 63 -8 1 0 -1 -2 0 64 0 80 63 -8 8 64 4 64 1 64 0 -128 
    0 16 63 -8 1 0 1 0 1 0 1 4 -1 -2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 0 2 0 
    2 0 2 0 7 -16 8 32 24 64 37 -128 2 -128 12 -128 113 -4 2 8 12 16 18 32 33 -64 1 0 14 0 112 0 
    1 0 1 0 1 0 9 32 9 16 17 12 17 4 33 16 65 16 1 32 1 64 0 -128 1 0 2 0 12 0 112 0 
    0 0 0 0 7 -16 24 24 48 12 56 12 0 56 0 -32 0 -64 0 -128 0 0 0 0 1 -128 3 -64 1 -128 0 0

注意：需要提交的是一个整数，不要填写任何多余内容。

solution

  • 为了存储输入信息到本地in.txt文件中，请采用freopen()函数进行读取操作。
    • 用于将数字转化为二进制形式或执行直接的位运算，并以每两个一组的形式输出即可。
    • 计算结果是9^{9}等于387,420,489。
复制代码 
    #include <iostream>
    #include <cstdio>
    using namespace std;
    void print_num(int n)
    {
    for (int i = 6; i >= 0; i--)
    {
        if (n & (1 << i))
            printf("*");
        else
            printf(" ");
    }
    }
    int main()
    {
    freopen("in.txt", "r", stdin);
    int n, cnt = 0;
    while (~scanf("%d", &n))
    {
    
        print_num(n);
        if (++cnt % 2 == 0)
            printf("\n");
    }
    return 0;
    }

3. 乘积尾零

如下的10行数据，每行有10个整数，请你求出它们的乘积的末尾有多少个零？

复制代码 
    5650 4542 3554 473 946 4114 3871 9073 90 4329 
    2758 7949 6113 5659 5245 7432 3051 4434 6704 3594 
    9937 1173 6866 3397 4759 7557 3070 2287 1453 9899 
    1486 5722 3135 1170 4014 5510 5120 729 2880 9019 
    2049 698 4582 4346 4427 646 9742 7340 1230 7683 
    5693 7015 6887 7381 4172 4341 2909 2027 7355 5649 
    6701 6645 1671 5978 2704 9926 295 3125 3878 6785 
    2066 4247 4800 1578 6652 4616 1113 6205 3264 2915 
    3966 5291 2904 1285 2193 1428 2265 8730 9436 7074 
    689 5510 8243 6114 337 4096 8199 7313 3685 211

注意：需要提交的是一个整数，表示末尾零的个数。不要填写任何多余内容。

solution

  • 只有当数字能被2和5整除时才会有末尾为0的情况存在
    因此，在对所有数字进行素因数分解后统计其中2和5的数量
    其中较小数量的那个即为最终答案\boxed{31} 。
  • 建议在程序运行时首先从文件中读取所需数据以简化后续处理流程
复制代码 
    #include <cstdio>
    int main()
    {
    freopen("in.txt", "r", stdin);
    int sum2 = 0, sum5 = 0, n;
    while (~scanf("%d", &n))
    {
        int tmp = n;
        while (n % 2 == 0)
            sum2++, n /= 2;
        while (tmp % 5 == 0)
            sum5++, tmp /= 5;
    }
    printf("%d\n", sum5 < sum2 ? sum5 : sum2);
    return 0;
    }

5. 快速排序

以下代码能够确定数组a中的第k小元素。此代码采用了类似于快速排序的分治策略，在预期情况下运行时间为O(N)。建议您深入分析源码，并补充划线部分所缺少的内容。

复制代码 
    #include <stdio.h>  
    int quick_select(int a[], int l, int r, int k) {  
    int p = rand() % (r - l + 1) + l;  
    int x = a[p];  
    {int t = a[p]; a[p] = a[r]; a[r] = t;}  
    int i = l, j = r;  
    while(i < j) {  
        while(i < j && a[i] < x) i++;  
        if(i < j) {  
            a[j] = a[i];  
            j--;  
        }  
        while(i < j && a[j] > x) j--;  
        if(i < j) {  
            a[i] = a[j];  
            i++;  
        }  
    }  
    a[i] = x;  
    p = i;  
    if(i - l + 1 == k) return a[i];  
    if(i - l + 1 < k) return quick_select( _____________________________ ); //填空  
    else return quick_select(a, l, i - 1, k);  
    }  
    
    int main()  
    {  
    int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};  
    printf("%d\n", quick_select(a, 0, 14, 5));  
    return 0;  
    }

注意：只填写划线部分缺少的代码，不要抄写已经存在的代码或符号。

solution

a, i+1, r, k-i+l-1

9. 全球变暖

你有一张某海域NxN像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

复制代码 
    .......
    .##....
    .##....
    ....##.
    ..####.
    ...###.
    .......

具体来说，在上下左右四个方向相连的一片陆地上形成了一个岛屿。例如上图所示就有两座这样的岛屿。

因为全球变暖导致海平面升高，在未来几十年内可能会出现这样的情况：岛屿边缘的一个像素范围可能会被海水淹没。

当一块陆地像素与海洋相邻（即上下左右四个相邻像素中存在海洋），它就会被淹没。

例如上图中的海域未来将会呈现出如下变化的样子：

复制代码 
    .......
    .......
    .......
    .......
    ....#..
    .......
    .......

输入样例

输入格式

复制代码 
    7 
    .......
    .##....
    .##....
    ....##.
    ..####.
    ...###.
    .......

【输出样例】
1

solution

  • 首先对输入的二维数组执行一个预处理操作，在该操作中会将与点号\.相邻的所有\#符号替换成用字符\*代替。
  • 接着通过广度优先搜索（BFS）遍历整个二维数组，在这一过程中会计算所有连通区域的数量。\n其数量即为问题的答案。
复制代码 
    #include <iostream>
    #include <cstdio>
    #include <queue>
    #include <cstring>
    using namespace std;
    const int maxn = 1111;
    char pic[maxn][maxn];
    bool vst[maxn][maxn];
    int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int N;
    //点的结构体
    struct point
    {
    int x, y;
    point()
    {
        x = y = 0;
    }
    };
    // 检测点是否超出边界
    bool check(point p)
    {
    if (p.x >= 0 && p.x < N && p.y >= 0 && p.y < N && !vst[p.x][p.y] && pic[p.x][p.y] == '#')
        return true;
    return false;
    }
    // 广度搜索，对每一个#的联通块设置的vst[x][y]为true
    void bfs(int x, int y)
    {
    memset(vst, false, sizeof(vst));
    queue<point> q;
    point now, tmp;
    now.x = x, now.y = y;
    q.push(now);
    vst[x][y] = true;
    while (!q.empty())
    {
        now = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            tmp.x = now.x + dir[i][0];
            tmp.y = now.y + dir[i][1];
            if (check(tmp))
            {
                q.push(tmp);
                vst[tmp.x][tmp.y] = true;
            }
        }
    }
    }
    int main()
    {
    // freopen("in.txt", "r", stdin);
    while (~scanf("%d", &N))
    {
        for (int i = 0; i < N; i++)
            scanf("%s", &pic[i]);
        // 预处理输入的数组，将临近.的#替换为*
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (pic[i][j] == '.')
                {
                    for (int k = 0; k < 4; k++)
                    {
                        int ni = i + dir[k][0], nj = j + dir[k][1];
                        if (ni < 0 || ni >= N || nj < 0 || nj >= N)
                            continue;
                        if (pic[ni][nj] == '#')
                            pic[ni][nj] = '*';
                    }
                }
        //广度搜索统计#联通块个数
        int ans = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (!vst[i][j] && pic[i][j] == '#')
                {
                    bfs(i, j);
                    ans++;
                }
        printf("%d\n", ans);
    }
    return 0;
    }

全部评论 (0)

还没有任何评论哟~

相关文章推荐

2018年第九届蓝桥杯【C++省赛B组】

1\.第几天 2000年的1月1日，是那一年的第1天。 那么，2000年的5月4日，是那一年的第几天？ 注意：需要提交的是一个整数，不要填写任何多余内容。 solution 2000年是闰年，2月29...

2018年第九届蓝桥杯C/C++B组省赛

2018年第九届蓝桥杯C/C++B组省赛 1\.【填空题】第几天 题目 题解 思路 答案 2\.【填空题】明码 题目 题解 思路 答案 3\.【填空题】乘积尾零 题目 题解 思路 答案 4\.【填空题...

2018年第九届蓝桥杯省赛C语言B组

2018年第九届蓝桥杯省赛C语言B组 题目来源：蓝桥杯 作者：GGG166 第一题 标题：第几天 2000年的1月1日，是那一年的第1天。 那么，2000年的5月4日，是那一年的第几天？ 注意：需要提...

2018年第九届蓝桥杯python组省赛

前言： 这年的题感觉比去年难度飙升了一个档次... 目录 填空题 第几天 明码 乘积尾零 测试次数 编程大题 递增三元组 螺旋折线 日志统计 全球变暖 乘积最大 填空题 第几天 题目： 2000年的1...

蓝桥杯2018年第九届C/C++ B组省赛习题题解

目录 第一题：第几天（手算） 第二题：明码（模拟） 第三题：乘积尾零（数学） 第四题：测试次数（dp） 第五题：快速排序（数据结构） 第六题：递增三元组（二段二分） 第七题：螺旋折线（数学） 第八题：...

蓝桥杯--2018第九届C/C++C组省赛

标题：哪天返回 小明被不明势力劫持。后莫名其妙被扔到x星站再无问津。小明得知每天都有飞船飞往地球，但需要108元的船票，而他却身无分文。 他决定在x星战打工。好心的老板答应包食宿，第1天给他1元钱。 ...

2018年省赛第九届蓝桥杯B组C/C++第二题解 明码

第二题：明码 汉字的字形存在于字库中，即便在今天，16点阵的字库也仍然使用广泛。16点阵的字库把每个汉字看成是16x16个像素信息。并把这些信息记录在字节中。一个字节可以存储8位信息，用32个字节就可...

2018年第九届蓝桥杯C/C++省赛A组题解

2018年第九届蓝桥杯C/C++省赛A组题解第一题： 题意：就是求一个，首项为1，等比为1/2的等比数列的前二十项之和 答案：就是2^201/2^19 第二题： 题意：求整个二十世纪总共有多少个星期一...

2018年第九届C/C++ A组蓝桥杯省赛真题

目录 第一题：哪天返回 第二题：猴子分香蕉 第三题：字母阵列 第四题：第几个幸运数 第五题：书号验证 第六题：稍小分数 第七题：次数差 第八题：等腰三角形题目描述 第九题：小朋友崇拜圈 第十题：耐摔指...

2018年 第九届蓝桥杯 C++省赛B组 第十题：乘积最大

[乘积最大] 题目 话8多说先上题目： 给定N个整数A1,A2,...AN。请你从中选出K个数，使其乘积最大。 请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余...