第十一届蓝桥杯(2020 10月17日)省赛C/C++ A组 赛后总结

发布于 2020-10-17  1052 次阅读


怎么说呢,感觉我就是个废物。。这次题还难的特难,简单的特简单(一看就会那种)。哭哭唧唧.jpg

结果出来了,最水赛区的省一(好像是赛区第一),冲冲冲

#试题A 门牌制作

本题总分:5 分

【问题描述】
小蓝要为一条街的住户制作门牌号。这条街一共有2020 位住户,门牌号从1 到2020 编号。小蓝制作门牌的方法是先制作0 到9 这几个数字字符,最后根据需要将字符粘贴到门牌上,例如门牌1017 需要依次粘贴字符1、0、1、7,即需要1 个字符0,2 个字符1,1 个字符7。请问要制作所有的1 到2020 号门牌,总共需要多少个字符2?

【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

【个人解法】
这玩意就有手就行。
##答案624

#include <stdio.h>
int main()
{
    int get( int m );


    int i, sum = 0;
    for ( i = 1; i <= 2020; i++ )
    {
        sum = sum + get( i );
    }
    printf( "%d", sum );
    return(0);
}


int get( int m )
{
    int    res = 0;
    int    temp;
    while ( m != 0 )
    {
        temp = m % 10;
        if ( temp == 2 )
        {
            res++;
        }
        m = m / 10;
    }
    return(res);
}


#试题B: 既约分数

本题总分:5 分

【问题描述】
如果一个分数的分子和分母的最大公约数是1,这个分数称为既约分数。例如,3/4 , 5/2 , 1/8 , 7/1都是既约分数。请问,有多少个既约分数,分子和分母都是1 到2020 之间的整数(包括1和2020)?

【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
【个人解法】
实际上就是康康分子分母的最大公约数是不是1。
##答案 2481215

#include <stdio.h>
int main()
{
    int get( int m );


    int i, j, sum = 0;
    for ( i = 1; i <= 2020; i++ )
    {
        for ( j = 1; j <= 2020; j++ )
        {
            if ( gcd( i, j ) == 1 )
            {
                sum++;
            }
        }
    }
    printf( "%d", sum );
    return(0);
}


int gcd( int a, int b )
{
    if ( a % b == 0 )
    {
        return(b);
    }else{
        return(gcd( b, a % b ) );
    }
}

#试题C: 蛇形填数

本题总分:10 分

【问题描述】

如下图所示,小明用从1 开始的正整数“蛇形”填充无限大的矩阵。

1 2 6 7

3 5 8

4 9

10

容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20 行第20 列的数是多少?

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

【个人解法】

**##答案761

这道题。。。第一反应excel,写了四五组发现是个三角形,用高斯能求出来起始列的顶点,是39列的第一行,780,再往回找就能找到对应的20/20是761**


#试题D: 七段码

本题总分:10 分

【问题描述】
小蓝要用七段码数码管来表示一种特殊的文字。

上图给出了七段码数码管的一个图示,数码管中一共有7 段可以发光的二极管,分别标记为a, b, c, d, e, f, g。小蓝要选择一部分二极管(至少要有一个)发光来表达字符。在设计字符的表达时,要求所有发光的二极管是连成一片的。

  1. 例如:b 发光,其他二极管不发光可以用来表达一种字符。

例如:c 发光,其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符,尽管看上去比较相似。

例如:a, b, c, d, e 发光,f, g 不发光可以用来表达一种字符。

例如:b, f 发光,其他二极管不发光则不能用来表达一种字符,因为发光的二极管没有连成一片。

请问,小蓝可以用七段码数码管表达多少种不同的字符?

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

【个人解法】

答案:听说是80(也有说81的)

用二进制也就是枚举十进制(1到127)。会产生一个二进制7位数,用0代表打开,1代表关闭,再判断是否连同就可以判断。搬运一个大佬的码

#include <bits/stdc++.h>
using namespace std;

int    head[100];
int    ct = 1;
struct node
{
    int v, next;
} e[100];

void add( int u, int v )
{
    e[ct].v        = v;
    e[ct].next    = head[u];
    head[u]        = ct++;
    swap( u, v );
    e[ct].v        = v;
    e[ct].next    = head[u];
    head[u]        = ct++;
}


void init()         /* 建图 */
{
    add( 1, 2 ), add( 1, 6 ), add( 2, 7 ), add( 2, 3 ), add( 3, 4 );
    add( 3, 7 ), add( 4, 5 ), add( 5, 6 ), add( 5, 7 ), add( 6, 7 );
}


int        ans[100], vis[100];
set<int>    st;

void save( int ct )
{
    int anss[10];
    for ( int i = 1; i <= ct; i++ )
        anss[i] = ans[i];
    sort( anss + 1, anss + 1 + ct );
    int res = 0;
    for ( int i = 1; i <= ct; i++ )
        res = res * 10 + anss[i];
    st.insert( res );
}


void dfs( int now, int all, int ct )
{
    ans[ct] = now;
    if ( all == ct )   /* 如果找到了大小为all的连通块 保存答案 */
    {
        save( all );
        return;
    }
    for ( int i = head[now]; i; i = e[i].next )
    {
        int v = e[i].v;
        if ( !vis[v] )
        {
            vis[v] = 1;
            dfs( v, all, ct + 1 );
            vis[v] = 0;
        }
    }
}


int main()
{
    init();
    for ( int i = 1; i <= 7; i++ )          /* 起点 */
        for ( int j = 1; j <= 7; j++ )  /* 连通块大小 */
        {
            vis[i] = 1;
            dfs( i, j, 1 );
            vis[i] = 0;
        }
    cout << st.size() << endl;
    return(0);
}

#试题E: 平面分割

本题总分:15 分

【问题描述】

20 个圆和20 条直线最多能把平面分成多少个部分?

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

【个人解法】

恕我不配!!!(这不是数学题吗,哭哭唧唧.jpg)


#试题F: 成绩分析

时间限制: 1.0s 内存限制: 256.0MB 本题总分:15 分

【问题描述】

小蓝给学生们组织了一场考试,卷面总分为100 分,每个学生的得分都是一个0 到100 的整数。请计算这次考试的最高分、最低分和平均分。

【输入格式】

输入的第一行包含一个整数n,表示考试人数。
接下来n 行,每行包含一个0 至100 的整数,表示一个学生的得分。

【输出格式】

输出三行。

第一行包含一个整数,表示最高分。

第二行包含一个整数,表示最低分。

第三行包含一个实数,四舍五入保留正好两位小数,表示平均分。

【样例输入】

7
80
92
56
74
88
99
10

【样例输出】

99
10
71.29

【评测用例规模与约定】

对于50% 的评测用例, 1 ≤ n ≤ 100。

对于所有评测用例,1 ≤ n ≤10000。

【个人解法】

这题,很简单,遍历。

#include <stdio.h>
int main()
{
    int    a[10000], n, i, sum, max, min;
    double    ave;
    scanf( "%d", &n );
    scanf( "%d", &a[0] );
    max = a[0], min = a[0], sum = a[0];
    for ( i = 1; i < n; i++ )
    {
        scanf( "%d", &a[i] );
        if ( max < a[i] )
        {
            max = a[i];
        }
        if ( min > a[i] )
        {
            min = a[i];
        }
        sum = sum + a[i];
    }
    ave = sum * 1.0 / n * 1.0;
    printf( "%d\n%d\n%.2lf", max, min, ave );
    return(0);
}

试题G: 回文日期

时间限制: 1.0s 内存限制: 256.0MB 本题总分:20 分

【问题描述】

2020 年春节期间,有一个特殊的日期引起了大家的注意:2020年2月2日。因为如果将这个日期按“yyyymmdd” 的格式写成一个8 位数是20200202,恰好是一个回文数。我们称这样的日期是回文日期。有人表示20200202 是“千年一遇” 的特殊日子。对此小明很不认同,因为不到2年之后就是下一个回文日期:20211202 即2021年12月2日。也有人表示20200202 并不仅仅是一个回文日期,还是一个ABABBABA型的回文日期。对此小明也不认同,因为大约100 年后就能遇到下一个ABABBABA 型的回文日期:21211212 即2121 年12 月12 日。算不上“千年一遇”,顶多算“千年两遇”。

给定一8 位数的日期,请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天。

【输入格式】

输入包含一个八位整数N,表示日期。

【输出格式】

输出两行,每行1 个八位数。第一行表示下一个回文日期,第二行表示下

一个ABABBABA 型的回文日期。

【样例输入】

20200202

【样例输出】

20211202
21211212

【评测用例规模与约定】

对于所有评测用例,10000101 ≤ N ≤ 89991231,保证N 是一个合法日期的8位数表示。

【个人解法】

为了保证数据。。可靠性.emmmm,我把所有回文时间都给扔数组里了,但是纠结11111111和22222222属不属于ABABBABA型的。

#include <stdio.h>
int main()
{
    int n;
    scanf( "%d", &n );
    int    a[307]    = { 10011001, 10100101, 10111101, 10200201, 10211201, 10300301, 10400401, 10500501, 10600601, 10700701, 10800801, 10900901, 11011011, 11100111, 11111111, 11200211, 11211211, 11300311, 11400411, 11500511, 11600611, 11700711, 11800811, 11900911, 12011021, 12100121, 12111121, 12200221, 12211221, 12300321, 12400421, 12500521, 12600621, 12700721, 12800821, 12900921, 13011031, 13100131, 13211231, 13300331, 13500531, 13700731, 13800831, 20011002, 20100102, 20111102, 20200202, 20211202, 20300302, 20400402, 20500502, 20600602, 20700702, 20800802, 20900902, 21011012, 21100112, 21111112, 21200212, 21211212, 21300312, 21400412, 21500512, 21600612, 21700712, 21800812, 21900912, 22011022, 22100122, 22111122, 22200222, 22211222, 22300322, 22400422, 22500522, 22600622, 22700722, 22800822, 22900922, 30011003, 30100103, 30111103, 30200203, 30211203, 30300303, 30400403, 30500503, 30600603, 30700703, 30800803, 30900903, 31011013, 31100113, 31111113, 31200213, 31211213, 31300313, 31400413, 31500513, 31600613, 31700713, 31800813, 31900913, 32011023, 32100123, 32111123, 32200223, 32211223, 32300323, 32400423, 32500523, 32600623, 32700723, 32800823, 32900923, 40011004, 40100104, 40111104, 40200204, 40211204, 40300304, 40400404, 40500504, 40600604, 40700704, 40800804, 40900904, 41011014, 41100114, 41111114, 41200214, 41211214, 41300314, 41400414, 41500514, 41600614, 41700714, 41800814, 41900914, 42011024, 42100124, 42111124, 42200224, 42211224, 42300324, 42400424, 42500524, 42600624, 42700724, 42800824, 42900924, 50011005, 50100105, 50111105, 50200205, 50211205, 50300305, 50400405, 50500505, 50600605, 50700705, 50800805, 50900905, 51011015, 51100115, 51111115, 51200215, 51211215, 51300315, 51400415, 51500515, 51600615, 51700715, 51800815, 51900915, 52011025, 52100125, 52111125, 52200225, 52211225, 52300325, 52400425, 52500525, 52600625, 52700725, 52800825, 52900925, 60011006, 60100106, 60111106, 60200206, 60211206, 60300306, 60400406, 60500506, 60600606, 60700706, 60800806, 60900906, 61011016, 61100116, 61111116, 61200216, 61211216, 61300316, 61400416, 61500516, 61600616, 61700716, 61800816, 61900916, 62011026, 62100126, 62111126, 62200226, 62211226, 62300326, 62400426, 62500526, 62600626, 62700726, 62800826, 62900926, 70011007, 70100107, 70111107, 70200207, 70211207, 70300307, 70400407, 70500507, 70600607, 70700707, 70800807, 70900907, 71011017, 71100117, 71111117, 71200217, 71211217, 71300317, 71400417, 71500517, 71600617, 71700717, 71800817, 71900917, 72011027, 72100127, 72111127, 72200227, 72211227, 72300327, 72400427, 72500527, 72600627, 72700727, 72800827, 72900927, 80011008, 80100108, 80111108, 80200208, 80211208, 80300308, 80400408, 80500508, 80600608, 80700708, 80800808, 80900908, 81011018, 81100118, 81111118, 81200218, 81211218, 81300318, 81400418, 81500518, 81600618, 81700718, 81800818, 81900918, 82011028, 82100128, 82111128, 82200228, 82211228, 82300328, 82400428, 82500528, 82600628, 82700728, 82800828, 82900928, 90011009 };
    int    b[10]    = { 10100101, 20200202, 21211212, 30300303, 40400404, 50500505, 60600606, 70700707, 80800808, 90900909 };
    int    i;
    for ( i = 0; i < 307; i++ )
    {
        if ( a[i] <= n && a[i + 1] > n )
        {
            printf( "%d\n", a[i + 1] );
            break;
        }
    }
    for ( i = 0; i < 10; i++ )
    {
        if ( b[i] <= n && b[i + 1] > n )
        {
            printf( "%d", b[i + 1] );
            break;
        }
    }
    return(0);
}

至于数组的生成就这样:

#include <stdio.h>
int main()
{
    int    a[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    int    i, t, month, day;
    for ( i = 1000; i <= 9090; i++ )
    {
        t    = i;
        month    = t / 10 % 10 + t % 10 * 10;
        if ( month <= 12 )
        {
            day = t / 1000 % 10 + t / 100 % 10 * 10;
            if ( day <= a[month - 1] )
            {
                printf( "%d", t );
                if ( month < 10 )
                {
                    printf( "0%d", month );
                }else{
                    printf( "%d", month );
                }
                if ( day < 10 )
                {
                    printf( "0%d,", day );
                }else{
                    printf( "%d,", day );
                }
            }
        }
    }
}

试题H: 子串分值

时间限制: 1.0s 内存限制: 256.0MB 本题总分:20 分

【问题描述】

对于一个字符串S,我们定义S 的分值 f(S) 为S中恰好出现一次的字符个数。例如f (”aba”) = 1,f (”abc”) = 3, f (”aaa”) = 0。

现在给定一个字符串S[0…n-1](长度为n),请你计算对于所有S的非空子串Si…j, f (S[i… j]) 的和是多少。

【输入格式】

输入一行包含一个由小写字母组成的字符串S。

【输出格式】

输出一个整数表示答案。

【样例输入】

ababc

【样例输出】

21

【样例说明】

子串   f值:
a          1
ab          2
aba         1
abab       0
ababc       1
 b            1
 ba         2
 bab         1
 babc       2
  a         1
  ab        2
  abc       3
   b        1
   bc       2
    c       1

【评测用例规模与约定】

对于20% 的评测用例,1 ≤ n ≤ 10;

对于40% 的评测用例,1 ≤ n ≤ 100;

对于50% 的评测用例,1 ≤ n ≤ 1000;

对于60% 的评测用例,1 ≤ n ≤ 10000;

对于所有评测用例,1 ≤ n ≤ 100000。

【个人解法】

这个暴力起来还算简单,但是估计能过40% ,50%可能能try一下。

#include <stdio.h>
#include <string.h>
int main()
{
    char    a[10000];
    int    b[26];
    scanf( "%s", a );
    int i, j, k, sum = 0, q = 0;
    for ( i = 0; i < 26; i++ )
    {
        b[i] = 0;
    }
    for ( i = 0; i < strlen( a ); i++ )
    {
        for ( j = i + 1; j <= strlen( a ); j++ )
        {
            q = 0;
            for ( k = 0; k < i; k++ )
            {
                printf( " " );
            }
            for ( k = i; k < j; k++ )
            {
                printf( "%c", a[k] );
                b[a[k] - 97]++;
            }
            printf( "\t" );
            for ( k = 0; k < 26; k++ )
            {
                if ( b[k] == 1 )
                {
                    q++;
                }
                b[k] = 0;
            }
            sum = sum + q;
            printf( "%d\n", q );
        }
    }
    printf( "res=%d", sum );
}

试题I: 荒岛探测

时间限制: 1.0s 内存限制: 256.0MB 本题总分:25 分

【问题描述】

科学家小蓝来到了一个荒岛,准备对这个荒岛进行探测考察。小蓝使用了一个超声定位设备来对自己进行定位。为了使用这个设备,小蓝需要在不同的点分别安装一个固定的发射器和一个固定的接收器。小蓝手中还有一个移动设备。定位设备需要从发射器发射一个信号到移动设备,移动设备收到后马上转发,最后由接收器接收,根据这些设备之间传递的时间差就能计算出移动设备距离发射器和接收器的两个距离,从而实现定位。小蓝在两个位置已经安装了发射器和接收器,其中发射器安装在坐标 (xA,yA) (xA,yA) (xA,yA),接收器安装在坐标 (xB,yB) (xB,yB) (xB,yB )。小蓝的发射器和接收器可能在岛上,也可能不在岛上。小蓝的定位设备设计有些缺陷,当发射器到移动设备的距离加上移动设备到接收器的距离之和大于L 时,定位设备工作不正常。当和小于等于L 时,定位设备工作正常。为了安全,小蓝只在定位设备工作正常的区域探测考察。已知荒岛是一个三角形,三个顶点的坐标分别为 (x1,y1)(x1,y1)(x1,y1), (x2,y2)(x2,y2) (x2,y2), (x3,y3) (x3,y3) (x3,y3)。

请计算,小蓝在荒岛上可以探测到的面积有多大?

【输入格式】

输入的第一行包含五个整数,分别为xA,yA,xB,yB,L

第二行包含六个整数,分别为x1,y1,x2,y2,x3,y3

【输出格式】

输出一行,包含一个实数,四舍五入保留2位小数,表示答案。

考虑到计算中的误差,只要你的输出与参考输出相差不超过0.01即可得分。

【样例输入】

10 6 4 12 12

0 2 13 2 13 15

【样例输出】

39.99

【样例说明】

当输出为39.98、39.99或40.00时可以得分。

【个人解法】

恕我高中数学啥也不是,我椭圆和三角形相交面积。emmm,是不是可以用极坐标来积分。


试题J :字串排序

时间限制: *s 内存限制: 256.0MB 本题总分:25 分

【问题描述】

小蓝最近学习了一些排序算法,其中冒泡排序让他印象深刻。在冒泡排序中,每次只能交换相邻的两个元素。小蓝发现,如果对一个字符串中的字符排序,只允许交换相邻的两个字符,则在所有可能的排序方案中,冒泡排序的总交换次数是最少的。例如,对于字符串 lan 排序,只需要 1 次交换。对于字符串 qiao 排序,总共需要 4 次交换。小蓝找到了很多字符串试图排序,他恰巧碰到一个字符串,需要 V 次交换,可是他忘了把这个字符串记下来,现在找不到了。

请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串,对该串的字符排序,正好需要 V 次交换。如果可能找到多个,请告诉小蓝最短的那个。如果最短的仍然有多个,请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。

【输入格式】

输入的第一行包含一个整数V,小蓝的幸运数字。

【输出格式】

题面要求的一行字符串。

【样例输入】

4

【样例输出】

bbaa

【评测用例规模与约定】

对于20% 的评测用例,1 ≤ n ≤ 20;

对于50% 的评测用例,1 ≤ n ≤ 100;

对于100% 的评测用例,1 ≤ n ≤ 10000;

【个人解法】

恕我只会骗用例


不会写珂朵莉树的废柴ACMer