• 第十三届蓝桥杯省赛C++B组题解

    写在前面

    · 本篇题解对应的是第十三届蓝桥杯省赛C++组的B组的第一场

    · 所使用的语言时Python3（其实主要看思路、是什么语言不重要🤫）

    · 仅包含8道大题的代码及思路

    · 有错误欢迎指出

    目录

    写在前面

    刷题统计 

    题目描述

    思路及代码

    修建灌木 

    题目描述

    思路及代码 

    X进制减法 

    题目描述

    思路及代码 

    统计子矩阵 

    题目描述

    思路及代码

    积木画

    题目描述

    思路及代码

    扫雷

    题目描述

    思路及代码 

    李白打酒加强版

    题目描述

    思路及代码 

    砍竹子 

    题目描述

    思路及代码 

    刷题统计 

    题目描述

    小明决定从下周一开始努力刷题准备蓝桥杯竞赛。

    他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。

    请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？

    输入格式

    输入一行包含三个整数 a,b 和 n。

    输出格式

    输出一个整数代表天数。

    数据范围

    对于 50% 的评测用例，1≤a,b,n≤10^6，
    对于100% 的评测用例，1≤a,b,n≤10^18

    输入样例：

    10 20 99

    输出样例：

    8

    思路及代码

    1.  
    2. # 简单模拟
    3.  
    4. a,b,n = map(int,input().split())
    5.  
    6. tot = 5 * a + 2 * b
    7.  
    8. cnt = n // tot 
    9. n -= tot * cnt
    10. cnt *= 7
    11.  
    12. flag = 0
    13. while n > 0 :
    14.     cnt += 1
    15.     flag += 1
    16.     if 1 <= flag <= 5 : n -= a
    17.     else : n -= b
    18.     
    19. print(cnt)

    修建灌木 

    题目描述

    爱丽丝要完成一项修剪灌木的工作。
    有 N 棵灌木整齐的从左到右排成一排。
    爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。
    爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。
    当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。
    直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
    灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。
    在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

    输入格式

    一个正整数N ，含义如题面所述。
    30%的测试数据：1 100%的测试数据：1

    输出格式

    输出 N 行，每行一个整数，第 i 行表示从左到右第 i 棵树最高能长到多高。

    输入样例 

    3

    输出样例 

    1. 4
    2. 2
    3. 4

    思路及代码 

    1.  
    2. # 每个树木被修剪后，爱丽丝有向左和向右走两种情况。我们找两个方向最长的，
    3. # 爱丽丝再次回来*2即可。
    4. n = int(input())
    5.  
    6. for i in range(1,n+1) :
    7.     print(max(i-1,n-i) * 2)

    X进制减法 

    题目描述

    进制规定了数字在数位上逢几进一。
    X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！
    例如说某种X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制：
    则 X 进制数321 转换为十进制数为65。65=3*(2*10)+2*(2)+1*(1)。
    现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定。
    只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。
    请你算出 A − B 的结果最小可能是多少。
    请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。

    输入格式

    第一行一个正整数 N，含义如题面所述。
    第二行一个正整数 Ma，表示 X 进制数 A 的位数。
    第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。
    第四行一个正整数 Mb，表示 X 进制数 B 的位数。
    第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。
    请注意，输入中的所有数字都是十进制的。
    30%的测试数据：2≤N≤10,1≤Ma,Mb≤8。
    100%的测试数据：2≤N≤1000,1≤Ma,Mb≤100000，B≤A。

    输出格式

    输出一行一个整数，表示X 进制数A − B 的结果的最小可能值转换为十进制后再模1000000007 的结果。

    输入样例

    1. 11
    2. 3
    3. 10 4 0
    4. 3
    5. 1 2 0

    输出样例

    94

    数据范围与提示

    当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。
    此时A 在十进制下是108，B 在十进制下是 14，差值是 94。

    思路及代码 

    1. MOD=int(1e9+7)
    2. if __name__ == '__main__':
    3.     n=int(input().strip())
    4.     ma=int(input().strip())
    5.     la=list(map(int,input().strip().split()))
    6.     la.reverse()
    7.     mb=int(input().strip())
    8.     lb=list(map(int,input().strip().split()))
    9.     lb.reverse()
    10.  
    11.     for i in range(ma-mb):
    12.         lb.append(0)
    13.     cnt=[0]*(ma+1)
    14.     cnt1=[0]*(ma+1)
    15.     for i in range(ma):
    16.         cnt[i]=max(la[i],lb[i],1)+1
    17.  
    18.     cnt1[0]=1
    19.     for i in range(1,ma):
    20.         cnt1[i]=cnt1[i-1]*cnt[i-1]%MOD
    21.     add1,add2=0,0
    22.     for i in range(ma):
    23.         add1=(add1+cnt1[i]*la[i])%MOD
    24.     for i in range(ma):
    25.         add2=(add2+cnt1[i]*lb[i])%MOD
    26.  
    27.     ans=(add1-add2)%MOD
    28.     print(ans)
    29.

    统计子矩阵 

    题目描述

    给定一个 N × M 的矩阵A，请你统计有多少个子矩阵(最小 1 × 1，最大 N × M) 满足：
    子矩阵中所有数的和不超过给定的整数K?

    输入格式

    第一行包含三个整数N, M 和K.
    之后 N 行每行包含 M 个整数，代表矩阵A.
    30%的测试数据：1≤N,M≤20；
    70%的测试数据：1≤N,M≤100；
    100%的测试数据：1≤N,M≤500；0≤Aij≤1000；1≤K≤250000000。

    输出格式

    一个整数代表答案。

    输入样例

    1. 3 4 10
    2. 1 2 3 4
    3. 5 6 7 8
    4. 9 10 11 12

    输出样例

    19

    数据范围与提示

    满足条件的子矩阵一共有19，包含：
    大小为1 × 1 的有10 个。
    大小为1 × 2 的有3 个。
    大小为1 × 3 的有2 个。
    大小为1 × 4 的有1 个。
    大小为2 × 1 的有3

    思路及代码

    1.  
    2. # 时间复杂度 O(n3)
    3. # 这题的思路就是，先枚举两条竖着的直线，为矩阵的左边和右边，然后从上到下双指针扫描，
    4. # 把二维问题变成一维问题：给定一个一维数组，求连续一段区间和小于等于k的区间数量，这可以用双指针去做。
    5. # TLE了两个点。
    6.  
    7. N,M,K = map(int,input().split())
    8. Map = [[0] * (M+1)]
    9.  
    10. for i in range(N) :
    11.     Map.append([0] + list(map(int,input().split())))
    12.     
    13. for i in range(1,N+1) :
    14.     for j in range(1,M+1) :
    15.         Map[i][j] += Map[i-1][j] + Map[i][j-1] - Map[i-1][j-1] 
    16.         
    17. ans = 0
    18.  
    19. for l in range(1,M+1) : # 枚举矩阵的左边
    20.     for r in range(l,M+1) : # 枚举矩阵的右边
    21.         j = 1 
    22.         for i in range(1,N+1) : # 有了左右边界，从上到下双指针扫描
    23.             
    24.             while j <= i and Map[i][r] - Map[j-1][r] - Map[i][l-1] + Map[j-1][l-1] > K : j += 1
    25.             if j <= i : ans += i - j + 1 # 有可能最小的矩阵都不满足，此时j>i
    26.  
    27. print(ans)

    积木画

    题目描述

    小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2 个单位面积）和 L 型（大小为 3 个单位面积）：


    同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构成。
    小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？
    积木可以任意旋转，且画布的方向固定。

    输入格式

    输入一个整数N，表示画布大小。
    对于所有测试用例，1 ≤ N ≤ 10000000。

    输出格式

    输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值

    输入样例 

    3

    输出样例 

    5

    思路及代码

    1.  
    2. '''
    3. dp[i][j]表示前i列填满并且填了第i+1列j个位置的方案，最终答案为dp[n][0]
    4. 由于n较大，但第i种状态只与i-1有关，可以用滚动数组优化
    5. '''
    6.  
    7. mod = 1000000007
    8. dp = [[0] * 3 for i in range(3)] # dp[i][j]表示前i列填满并且填了第i+1列j个位置的方案
    9.  
    10. dp[1][0] = 1 # 一个长条竖着放
    11. dp[1][1] = 2 # 一个L型竖着放（可以上下翻转所以是两种）
    12. dp[1][2] = 1 # 两个长条横着放
    13.  
    14. n = int(input())
    15.  
    16. for i in range(2,n+1) :
    17.     # 这一列长条竖着放 + 前一列占满
    18.     dp[i&1][0] = (dp[i-1&1][0] + dp[i-1&1][2]) % mod
    19.     # 一个L型竖着放（上下翻转*2） + 这一列被占一个再横着放一个长条
    20.     dp[i&1][1] = (dp[i-1&1][0]*2 + dp[i-1&1][1]) % mod
    21.     # 这一列两个长条横着放 + 一个L型摆成7字形
    22.     dp[i&1][2] = (dp[i-1&1][0] + dp[i-1&1][1]) % mod
    23.     
    24. print(dp[n&1][0]%mod)

    扫雷

    题目描述

    小明最近迷上了一款名为《扫雷》的游戏。
    其中有一个关卡的任务如下，在一个二维平面上放置着 n 个炸雷
    第 i 个炸雷(xi, yi, ri) 表示在坐标(xi, yi) 处存在一个炸雷，它的爆炸范围是以半径为 ri 的一个圆。
    为了顺利通过这片土地，需要玩家进行排雷。
    玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向。
    第 j 个排雷火箭(xj, yj, rj) 表示这个排雷火箭将会在(xj, yj) 处爆炸，它的爆炸范围是以半径为 rj 的一个圆，
    在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。
    现在小明想知道他这次共引爆了几颗炸雷？
    你可以把炸雷和排雷火箭都视为平面上的一个点。
    一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。

    输入格式

    输入的第一行包含两个整数n、m.
    接下来的 n 行，每行三个整数xi, yi, ri，表示一个炸雷的信息。
    再接下来的 m 行，每行三个整数xj, yj, rj，表示一个排雷火箭的信息。
    40% 的评测用例：0 ≤ x, y ≤ 10^9; 0 ≤ n,m ≤ 10^3; 1 ≤ r ≤ 10:
    100% 的评测用例：0 ≤ x, y ≤ 10^9; 0 ≤ n,m ≤ 5 × 10^4; 1 ≤ r ≤ 10:

    输出格式

    输出一个整数表示答案。

    输入样例 

    1. 2 1
    2. 2 2 4
    3. 4 4 2
    4. 0 0 5

    输出样例 

    2

    数据范围与提示

    示例图如下，排雷火箭1 覆盖了炸雷1，所以炸雷1 被排除；炸雷1 又覆盖了炸雷2，所以炸雷2 也被排除。

    思路及代码 

    1. //注：本题需要用到LL数据类型来进行哈希 Python语言较难通过
    2. // 因此这里给大家粘贴一份大佬的C++代码
    3.  
    4. #include 
    5. #include 
    6. #include 
    7. using namespace std;
    8.  
    9. const int N = 5e4 + 10, M = 1e6 + 7, X = 1e9 + 1;
    10. int n, m;
    11. struct node {
    12.     int x, y, r;
    13. }b[N];
    14. typedef long long ll;
    15. ll h[M]; // 哈希数组
    16. bool st[N]; // 判断是否访问过
    17. int id[M], res; // id数组为哈希数组中key对应的地雷下标
    18.  
    19. ll get_hs(int x, int y) { // 得到每个坐标的哈希值
    20.     return (ll)x * X + y;
    21. }
    22.  
    23. int find(int x, int y) { // 找到该坐标被哈希数组存储的下标key
    24.     ll hs = get_hs(x, y);
    25.     int key = (hs % M + M) % M; // 映射到哈希数组内部
    26.     // 如果该位置已经被占用并且不等于我们要求的哈希值，要在之后找到相应位置
    27.     while(h[key] != -1 && h[key] != hs) { 
    28.  
    29.         key++;
    30.         if(key == M) key = 0; // 哈希表走到末尾，又从0开始
    31.     }
    32.     return key;
    33. }
    34.  
    35. // 判断x1，y1为圆心，半径为r的圆是否包含x，y
    36. bool check(int x1, int y1, int r, int x, int y) { 
    37.     int d = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
    38.     return d <= r * r;
    39. }
    40.  
    41. void bfs(int pos) {
    42.     queue<int> q;
    43.     q.push(pos);
    44.     st[pos] = 1;
    45.     while(q.size()) {
    46.         int t = q.front();
    47.         q.pop();
    48.         int x = b[t].x, y = b[t].y, r = b[t].r;
    49.         for(int xx = x - r; xx <= x + r; xx++) { // 从(x-r, y-r)枚举到(x+r, y+r)
    50.             for(int yy = y - r; yy <= y + r; yy++) {
    51.                 int key = find(xx, yy); // 找到该坐标点对应的哈希下标
    52.                 // 该点是不是地雷，有没有被访问过，能不能炸到 
    53.                 if(id[key] && !st[id[key]] && check(x, y, r, xx, yy)) { 
    54.                     int pos = id[key]; // 获得对应地雷编号
    55.                     st[pos] = 1;
    56.                     q.push(pos);
    57.                 }
    58.             }
    59.         }
    60.     }
    61. }
    62.  
    63. int main() {
    64.     cin >> n >> m;
    65.     memset(h, -1, sizeof(h));
    66.     int x, y, r;
    67.     for(int i = 1; i <= n; i++) { // 读入地雷，存入哈希表
    68.         cin >> x >> y >> r;
    69.         b[i] = {x, y, r};
    70.         int key = find(x, y);// 找到该坐标点对应的哈希下标
    71.         if(h[key] == -1) h[key] = get_hs(x, y); // 如果哈希对应位置为空，则插入
    72.  
    73.         // id数组没有被标记或者找到了同一个坐标点更大半径的地雷
    74.         if(!id[key] || b[id[key]].r < r) { 
    75.             id[key] = i;
    76.         }
    77.     }
    78.     for(int i = 1; i <= m; i++) { // 枚举导弹
    79.         cin >> x >> y >> r;
    80.         for(int xx = x - r; xx <= x + r; xx++) {
    81.             for(int yy = y - r; yy <= y + r; yy++) {
    82.                 int key = find(xx, yy);
    83.  
    84.                 // 如果该点有地雷，没有被访问过，能被炸到
    85.                 if(id[key] && !st[id[key]] && check(x, y, r, xx, yy)) bfs(id[key]);
    86.             }
    87.         }
    88.     }
    89.     // 遍历每个地雷，看是否被标记
    90.     for(int i = 1; i <= n; i++) {
    91.         int key = find(b[i].x, b[i].y); // 获得坐标点对应哈希下标
    92.         int pos = id[key]; // 哈希下标对应的地雷编号
    93.         if(pos && st[pos]) res++; // 如果有地雷并且被访问过
    94.     }
    95.     cout << res;
    96.     return 0;
    97. }
    98.

    李白打酒加强版

    题目描述

    话说大诗人李白，一生好饮。幸好他从不开车。
    一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：
    无事街上走，提壶去打酒。
    逢店加一倍，遇花喝一斗。
    这一路上，他一共遇到店 N 次，遇到花 M 次。
    已知最后一次遇到的是花，他正好把酒喝光了。
    请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
    注意：壶里没酒( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

    输入格式

    输入包含多组测试数据。
    第一行为T，表示存在T组测试数据，T不超过30。
    对于每组测试数据，输入两个整数N 和M.
    1 ≤ N, M ≤ 100。

    输出格式

    输出一个整数表示答案。由于答案可能很大，输出模1000000007 的结果。

    输入样例 

    1. 1
    2. 5 10

    输出样例 

    14

    数据范围与提示

    如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：

    010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100 

    思路及代码 

    1. '''
    2. 题目要求的是求遇到遇到花的次数i=N、遇到店的次数j=M、且剩余酒的量k=0斗的情况有多少种。
    3. 由此我们的思路就很容易确定了，即设置一个三维数据f[i][j][k]，
    4. i即遇到花的次数，j即遇到店的次数，k即当前酒的量。
    5. f[i][j][k]即遇到花的次数为i，遇到店的次数为j，酒量为k的情况数量。
    6. '''
    7.  
    8. N,M = map(int,input().split())
    9. mod = 1000000007 
    10.  
    11. dp = [[[0] * (M+5) for i in range(M+5)] for j in range(N+5)]
    12. dp[0][0][2] = 1
    13.  
    14. for i in range(N+1) : 
    15.     for j in range(M+1) :
    16.         for k in range(M+1) :
    17.             if i and k % 2 == 0 : dp[i][j][k] += dp[i-1][j][k//2] # 当前到店
    18.             if j : dp[i][j][k] += dp[i][j-1][k+1] # 当前到花
    19.             dp[i][j][k] %= mod
    20.  
    21. # 最后一步必然是到店，所以看倒数第二步的状态
    22. print(dp[N][M-1][1])

    砍竹子 

    题目描述

    这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 hi.
    他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。
    魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为H，
    那么使用一次魔法可以把这一段竹子的高度都变为：

    其中 ⌊x⌋ 表示对 x 向下取整。

    小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为1。

    输入格式

    第一行为一个正整数 n，表示竹子的棵数。
    第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。
    20%的测试数据：n ≤ 1000; hi ≤ 10^6。
    100%的测试数据：n ≤ 2 × 10^5; hi ≤ 10^18。

    输出格式

    一个整数表示答案。

    输入样例 

    1. 6
    2. 2 1 4 2 6 7

    输出样例 

    5

    数据范围与提示

    其中一种方案：
    2 1 4 2 6 7
    → 2 1 4 2 6 2
    → 2 1 4 2 2 2
    → 2 1 1 2 2 2
    → 1 1 1 2 2 2
    → 1 1 1 1 1 1
    共需要 5 步完成。

    思路及代码 

    1.  
    2. '''
    3. 这个题本质是一个最长公共下降子序列的问题，
    4. 对于任意一个h,只要它高度降到了与前一个高度下降过程中的公共值，那么它就不需要花费代价继续下降。
    5. 如果它降得的当前高度与前一个高度没有公共值，则需要多花费一个代价，来降低自己的高度。
    6. 我们只需要开两个数组暴力做一下就行。
    7. '''
    8.  
    9. from math import sqrt
    10. n = int(input())
    11. lst = [0] + list(map(int,input().split()))
    12.  
    13. def solve(num) :
    14.     return int(sqrt(num//2+1))
    15.     
    16. res = 0
    17. b = [[] for i in range(n+10) ]
    18.  
    19. for i in range(1,n+1) :
    20.     while lst[i] > 1 :
    21.         flag = 0
    22.         for j in b[i-1] :
    23.             if lst[i] == j :
    24.                 flag = 1
    25.                 break
    26.         if not flag : res += 1
    27.         b[i].append(lst[i])
    28.         lst[i] = solve(lst[i])
    29.             
    30. print(res)

    🔚

  • 相关阅读:
    猿创征文 | 【IoT开发工具箱】Postman模拟https请求
    批处理生成带有时间戳或递增编号的临时文件名
    redis学习笔记
    Android webView JS 之间的交互
    [附源码]Python计算机毕业设计Django-Steam游戏平台系统论文
    安卓APP抓包环境配置
    政策解读：《科技保险业务统计制度》带来新要求，数据报送攻略大公开！
    设计模式之【模板方法模式】
    【毕业季·进击的技术er】年少有梦，何惧彷徨
    Java当中的BIO模型
  • 原文地址：https://blog.csdn.net/m0_54689021/article/details/127358812