第11届蓝桥杯省赛B组题解

作者： 作者的头像   胡图图 ,  2020-07-07 03:13:24 ,  所有人可见 ,  阅读 2395

7


7

更好的观看体验

A.

题目描述

小明要做一个跑步训练。

初始时，小明充满体力，体力值计为 10000。如果小明跑步，每分钟损耗

600 的体力。如果小明休息，每分钟增加 300 的体力。体力的损耗和增加都是

均匀变化的。

小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循

环。如果某个时刻小明的体力到达 0，他就停止锻炼。

请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。

答案中只填写数，不填写单位。

解题思路

直接模拟一遍，注意单位是秒

#include <bits/stdc++.h>

using namespace std;

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int x;

    cin >> x;

    int res = 0;

    while(x)
    {
        if(x > 600)
        {
            x -= 600;
            res += 60;
        }
        else
        {
            res += x / 10;
            break;
        }


        if(x > 0)
        {
            x += 300;
            res += 60;
        }

    }

    cout << res << endl;
    // res = 3880

    return 0;
}

B

题目描述

2020 年 7 月 1 日是中国共产党成立 99 周年纪念日。

中国共产党成立于 1921 年 7 月 23 日。

请问从 1921 年 7 月 23 日中午 12 时到 2020 年 7 月 1 日中午 12 时一共包

含多少分钟？

解题思路

每年365天，先跑到2020年7月23日，注意闰年的2月份是29天，

然后再-22天，到7月1就可以了

#include <bits/stdc++.h>

using namespace std;

int leap(int x)
{
    return x % 400 == 0 || x % 4 == 0 && x % 100 != 0;
}

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int S = 1921;
    int E = 2020;
    int res = 0;

    for(int i = S + 1 ; i <= E ;i ++ )
    {
        res += 365;
        if(leap(i)) res ++ ; 
    }

    res -= 22;

    cout << res * 24 * 60 << endl; 
    // 52038720

    return 0;
}

C

题目描述

新冠疫情由新冠病毒引起，最近在 A 国蔓延，为了尽快控制疫情，A 国准

备给大量民众进病毒核酸检测。

然而，用于检测的试剂盒紧缺。

为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（k

个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 k

个人都是阴性，用一个试剂盒完成了 k 个人的检测。如果结果为阳性，则说明

至少有一个人为阳性，需要将这 k 个人的样本全部重新独立检测（从理论上看，

如果检测前 k 1 个人都是阴性可以推断出第 k 个人是阳性，但是在实际操作中

不会利用此推断，而是将 k 个人独立检测），加上最开始的合并检测，一共使用

了 k + 1 个试剂盒完成了 k 个人的检测。

A 国估计被测的民众的感染率大概是 1%，呈均匀分布。请问 k 取多少能

最节省试剂盒？

解题思路

E = E1 + E2

E: k个人完成测试的用掉测试多少个试剂的数学期望

E1: 如果k个人一起检测时成功的数学期望

E2: 如果k个人一起检测时失败之后单独检测的数学期望

$ E1 = 0.99^k $
$ E2 = (1 - 0.99^k) * (k + 1)$
$ E = k - 0.99^k * k + 1$

量化到每个人的话就是

$ e = E / k = 1 - 0.99^k + 1 / k$

这显然是一个凹函数，所以跑个程序找最小值点就行了

#include <bits/stdc++.h>

using namespace std;

double get(int i)
{
    return 1 + 1.0 / i - pow(0.99,i);
}

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    // 用二分或者线性扫描找到最优点

    int res = 0;

    for(int i=1;i<=1000;i++)
    {
        if(res == 0 || get(res) > get(i))
            res = i;  
    }

    cout << res << endl;
    // 11;

    return 0;
}

D

题目描述

附件 prog.txt 中是一个用某种语言写的程序。

其中 REPEAT k 表示一个次数为 k 的循环。循环控制的范围由缩进表达，

从次行开始连续的缩进比该行多的（前面的空白更长的）为循环包含的内容。

例如如下片段：

REPEAT 2:

A = A + 4

REPEAT 5:

REPEAT 6:

A = A + 5

A = A + 7

A = A + 8

A = A + 9

该片段中从 A = A + 4 所在的行到 A = A + 8 所在的行都在第一行的
循环两次中。

REPEAT 6: 所在的行到 A = A + 7 所在的行都在 REPEAT 5: 循环中。
A = A + 5 实际总共的循环次数是 2 × 5 × 6 = 60 次。

请问该程序执行完毕之后，A 的值是多少？

解题思路

模拟一遍就行了

ps: UPD 2020.9.27

#include <bits/stdc++.h>

using namespace std;

int main(){

    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int res = 0;

    stack<int> stk;

    string str;

    int cur = 0;
    int mul = 1;

    while(true)
    {
        getline(cin,str);

        if(str == ";") break;

        reverse(str.begin(),str.end());

        int c = 0;

        while(str.back() == ' ')
        {
            c ++ ;
            str.pop_back();
        }

        reverse(str.begin(),str.end());

        c /= 4;

        if(cur > c)
        {
            while(cur > c)
            {
                mul /= stk.top();
                stk.pop();
                cur -- ;
            }

            if(str[0] == 'R')
            {
                int x = str[7] - '0';
                mul *= x;
                stk.push(x);
            }
            else
            {
                int x = str[8] - '0';
                res += mul * x;
            }

        }
        else if(cur <= c)
        {
            cur = c;
            if(str[0] == 'R')
            {
                int x = str[7] - '0';
                mul *= x;
                stk.push(x);
            }
            else
            {
                int x = str[8] - '0';
                res += mul * x;
            }
        }
    }

    cout << res << endl;
    //241830

    return 0;
}

E

题目描述

把 1 ∼ 2020 放在 2 × 1010 的矩阵里。要求同一行中右边的比左边大，同一

列中下边的比上边的大。一共有多少种方案？

答案很大，你只需要给出方案数除以 2020 的余数即可

解题思路

想成两个栈，A,B(一上一下),从1~2020依次向A,B内放数，要想合法，

必须要保证在A内放的数 >= B内放的数，那么这就是个卡特兰数 了，

写个代码就行了。

#include <bits/stdc++.h>

using namespace std;

const int mod = 2020;

const int N = 3010;

int C[N][N];

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    // 第1010个卡特兰数

    int n = 1010;

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }


    cout << ((C[n * 2][n] - C[2 * n][n - 1]) % mod + mod) % mod << endl;
    // 1340


    return 0;
}

F

问题描述

有一个序列，序列的第一个数是 n，后面的每个数是前一个数整除 2，请输

出这个序列中值为正数的项。

算法

模拟 O(log(n))

按他说的模拟就行了

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    ll x;

    cin >> x;

    while(x)
    {
        cout << x << " ";
        x /= 2;
    }

    return 0;
}

G

问题描述

小明有一串很长的英文字母，可能包含大写和小写。

在这串字母中，有很多连续的是重复的。小明想了一个办法将这串字母表

达得更短：将连续的几个相同字母写成字母 + 出现次数的形式。

例如，连续的 5 个 a，即 aaaaa，小明可以简写成 a5（也可能简写成 a4a、

aa3a 等）。对于这个例子：HHHellllloo，小明可以简写成 H3el5o2。为了方便表

达，小明不会将连续的超过 9 个相同的字符写成简写的形式。

现在给出简写后的字符串，请帮助小明还原成原来的串。

算法

模拟 O(n)

#include <bits/stdc++.h>

using namespace std;

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    string s;

    cin >> s;

    string res;

    int n = s.size();

    for(int i=0;i<n;i++)
    {
        int x = 1;
        char ch = s[i];

        if(i + 1 < n && s[i + 1] >= '0' && s[i + 1] <= '9')
        {
            x = s[i + 1] - '0';
            i ++ ;
        }
        if(x > 0) res += string(x,ch);
    }

    cout << res << endl;

    return 0;
}

H

题目描述

在平面上有一些二维的点阵。

这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，

从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。

现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。只能向右或者向下

走。

注意，如果行号和列数都是偶数，不能走入这一格中。

问有多少种方案。

算法

DP O(n*m)

f[i][j]:只能从f[i - 1][j],f[i][j - 1]转移而来(从上和左走过来)。

如果违反规定则置0

转移方程： f[i][j] = f[i - 1][j] + f[i][j - 1]

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 45;

int f[N][N];

int n,m;

signed main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(i == 1 && j == 1) 
            {
                f[i][j] = 1;
                continue;
            }

            if(i % 2 == 0 && j % 2 == 0)
            {
                f[i][j] = 0;
                continue;
            }

            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }

    cout << f[n][m] << endl;

    return 0;
}

I

题目描述

给定义个长度为 n 的数组A1, A2, · · · , An。你可以从中选出两个数 Ai 和 Aj
(i 不等于 j)，然后将 Ai 和 Aj

一前一后拼成一个新的整数。例如 12 和 345 可

以拼成 12345 或 34512。注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便

是 Ai = Aj 时。

请你计算有多少种拼法满足拼出的整数是 K 的倍数。

算法

DP O(N * log(a[i]))

在这题中我们主关心这个数%k是多少。

所以我们的运算都是%k的

a拼在b后面意味着，b * 10 ^ (p[a] + 1) + a,p[a](a的在十进制下的位数)

然后我们递推就行了

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 10;

int n,k;

int a[N],p[N];
int mp[12][N];

int get(int x) // 获取一个数的位数
{
    int res = 0;

    do
    {
        res ++ ;
        x /= 10;
    } while (x);

    return res;
}

void work(int x,int d) // 将每个数*10^j的结果存入mp里面，方便快速计算答案
{
    for(int j=1;j<12;j++)
    {
        x = x * 10 % k;
        mp[j][x] += d ;
    }
}

signed main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;

    for(int i=1;i<=n;i++) 
    {
        cin >> a[i];

        p[i] = get(a[i]);
        a[i] = a[i] % k;
        work(a[i],1);
    }

    int res = 0;

    for(int i=1;i<=n;i++)
    {
        work(a[i],-1); // 把自己先删掉，不能和自己拼

        int nd = (k - a[i]) % k;

        res += mp[p[i]][nd];

        work(a[i],1); // 恢复

    }

    cout << res << endl;

    return 0;
}

J

题目描述

小明正在做一个网络实验。

他设置了 n 台电脑，称为节点，用于收发和存储数据。

初始时，所有节点都是独立的，不存在任何连接。

小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信

了。两个节点如果存在网线连接，称为相邻。

小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送

到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接

或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。

一条信息只存储一次。

给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

算法

启发式合并 + 并查集 O(n*log(n))

并查集内存储，预留的add，和最终答案w

每一次操作2，将其放在该节点所对应集合的头节点的add上

每一次操作1，将两个点所在的集合a,b.把b合并在a上面，

要把b的add散下去，并且要-去a的add，因为a最后还是要

散下去，这样就能避免重复计算。

最后将所有add散下去，计算答案。

// 带权并查集

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int cap[N],add[N],w[N];

vector<int> v[N];

void merge(int a,int b)
{
    a = cap[a];
    b = cap[b];

    if(a == b) return ;

    if(v[a].size() > v[b].size()) 
    {
        swap(a,b);
    }

    for(auto x : v[a])  
    {
        w[x] += add[a] - add[b];
        cap[x] = b;
        v[b].push_back(x);
    }

    v[a].clear();
    add[a] = 0;

}

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int n,m;

    cin >> n >> m;

    for(int i=1;i<=n;i++)
    {
        cap[i] = i;
        v[i].push_back(i);
    }

    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        if(a == 1) merge(b,c);
        else
        {
            b = cap[b];
            add[b] += c;
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(auto x : v[i])
            w[x] += add[i];
        add[i] = 0;
    }

    for(int i=1;i<=n;i++) cout << w[i] << " ";
    cout << endl;



    return 0;
}

20 评论

用户头像
zzt   2020-10-20 17:22         踩      回复

感觉c题应该错了吧，我开始也是这么想的，但它说的是均匀分布，可以参考下这个https://blog.csdn.net/qq_43408978/article/details/108165611

用户头像
胡图图   2020-10-20 17:31         踩      回复

均匀分布是啥了？100个里面有且仅有1个？我可能学了个假的均匀分布。貌似抛骰子就是一种均匀分布吧，你能假设6次里面一定1、2、3、4、5、6各出一次嘛？

用户头像
胡图图   2020-10-20 17:32         踩      回复

题意是指每个人的发病率都一样吧？是嘛？不知道啊（等个专业大佬解答

用户头像
fedfan   2020-09-26 13:45         踩      回复

大佬d题错了啊，不是求题目描述中的a，是求prog.txt里面的a

用户头像
胡图图   2020-09-26 20:41         踩      回复

没有那个附件啊。。。┭┮﹏┭┮

用户头像
yxc胡建分灿   2020-08-31 11:39         踩      回复

这是什么组别的B组呀，为什么试题不太一样

用户头像
胡图图   2020-08-31 11:57         踩      回复

我看群里面发的题，应该是c++B吧

用户头像
yxc胡建分灿   2020-08-31 11:26         踩      回复

没能明白：请问 k 取多少能 最节省试剂盒？ 为啥求的是凸函数的最大点？

用户头像
胡图图   2020-08-31 11:58         踩      回复

写错了写错了，凹函数最小点

用户头像
小雪菜本菜   2020-07-22 23:16         踩      回复

请问卡特兰数那道题是怎么解释右边的数都大于左边，下面的数都大于上面呢 (⊙o⊙)？

用户头像
胡图图   2020-07-23 04:59         踩      回复

想象一下，从1~2*n，向上下依次插数，如果下面插得数>上面的话，必然会非法

用户头像
尤雨溪   2020-07-07 16:57         踩      回复

厉害

用户头像
dys   2020-07-07 09:35         踩      回复

大佬有题目的内容吗？

用户头像
胡图图   2020-07-07 09:50         踩      回复

群里面就有，网上应该也能搜到

用户头像
dys   2020-07-07 10:26    回复了 胡图图 的评论         踩      回复

好的，十分感谢

用户头像
cht   2020-07-07 06:39         踩      回复

o r z

用户头像
歪嘴战神叁叁叁   2020-07-07 03:29         踩      回复

扫了一眼，感觉除了最后两道题，其他好像难度不是很大，虽然我还没看题qwq

用户头像
胡图图   2020-07-07 07:36         踩      回复

是的，最后一题用了挺久的

用户头像
歪嘴战神叁叁叁   2020-07-07 03:27         踩      回复

写完用了多久啊

用户头像
歪嘴战神叁叁叁   2020-07-07 03:26         踩      回复

棒！