第十三届蓝桥杯省赛C++B组错题笔记_小明特别喜欢顺子。顺子指的就是连续的三个数字:123、456 等。顺子日期指的就是在

A: 九进制转十进制

问题描述
九进制正整数 (2022)₉ 转换成十进制等于多少？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#include<bits/stdc++.h>

using namespace std;

int main()
{
    string s = to_string(2022);
    int res = 0;
    for(int i = 0;i < s.size();i++)
        res = res * 9 + s[i] - '0';
    cout << res << endl;//答案: 1478
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

B：顺子日期

问题描述
小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日
期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺
子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123； 而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022
年份中，一共有多少个顺子日期。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#include<bits/stdc++.h>

using namespace std;

const int months[] = {
    0,31,28,31,30,31,
    30,31,31,30,31,30,
    31
};

bool check(string str)
{
    for(int i = 0;i + 2 < str.size();i++)
        if(str[i + 1] == str[i] + 1 && str[i + 2] == str[i] + 2)
            return true;
    return false;
}

int main()
{
    int year = 2022,month = 1,day = 1;
    int res = 0;
    for(int i = 0;i < 365;i++)
    {
        char str[10];
        sprintf(str,"%04d%02d%02d",year,month,day);
        if(check(str))
        {
            res++;
            cout << str << endl;
        }
        
        if(++day > months[month])
        {
            day = 1;
            month ++;
        }
    }
    cout << res << endl;
    return 0;
}
/*结果显示：
20220120
20220121
20220122
20220123
20220124
20220125
20220126
20220127
20220128
20220129
20221012
20221123
20221230
20221231
14
*/
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

C：刷题统计

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

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

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

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

输出格式
输出一个整数代表天数。

数据范围
对于 50% 的评测用例，1 ≤ a,b,n ≤ 10⁶，
对于 100% 的评测用例，1 ≤ a,b,n ≤ 10¹⁸。

输入样例：
10 20 99
输出样例：
8

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ll a,b,n;
    cin >> a >> b >> n;
    ll week[] = {a,a,a,a,a,b,b};//注意开long long
    ll s = 5 * a + 2 * b;
    ll res = n / s * 7;
    n %= s;//如果可以整除，就可以直接跳过下面的for循环了(取模好评)
    for(int i = 0;n > 0;i++)//剩下就不足一个周期了
    {
        n -= week[i];
        res++;
    }
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

D：修剪灌木

题目描述
爱丽丝要完成一项修剪灌木的工作。

有 N 棵灌木整齐的从左到右排成一排。

爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。

爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。

当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。

直到修剪了最左的灌木后再次调转方向。

然后如此循环往复。

灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。

在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

输入格式
一个正整数 N，含义如题面所述。

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

数据范围
对于 30% 的数据，N ≤ 10，
对于 100% 的数据，1 < N ≤ 10000。

输入样例：
3
输出样例：
4
2
4

#include<bits/stdc++.h>

using namespace std;
const int N = 1e4 + 10;


int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
        cout << max(i - 1,n - i) * 2 << endl;
    return 0;
}
/*
* * * * * * * *
1 2 3 i 5 6 7 8
(i - 1) * 2:第i个灌木被剪掉后，从右往左开始走，到下次再走到i的时候的长度
(n - i) * 2:第i个灌木被剪掉后，从左往右开始走，到下次再走到i的时候的长度
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

E：X进制减法

题目描述
进制规定了数字在数位上逢几进一。

X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！

例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 X 进制数 321 转换为十进制数为 65。

现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。

请你算出 A−B 的结果最小可能是多少。

请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。

输入格式
第一行一个正整数 N，含义如题面所述。

第二行一个正整数 M_a，表示 X 进制数 A 的位数。

第三行 M_a 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。

第四行一个正整数 M_b，表示 X 进制数 B 的位数。

第五行 M_b 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。

请注意，输入中的所有数字都是十进制的。

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

数据范围
对于 30% 的数据，N ≤ 10;M_a,M_b ≤ 8，
对于 100% 的数据，2 ≤ N ≤ 1000;1 ≤ M_a,M_b ≤ 100000; A ≥ B。

输入样例：
11
3
10 4 0
3
1 2 0
输出样例：
94
样例解释
当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。

此时 A 在十进制下是 108，B 在十进制下是 14，差值是 94。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5+10,mod = 1e9+7;

int n,m1,m,m2;
int a[N],b[N];

int main()
{
    scanf("%d",&n);
    scanf("%d",&m1);//读入的时候有可能这两个数的位数不一样，我们是个位对齐，而不是高位对齐(因为高位对不齐)
    for(int i = m1 - 1;i >= 0;i--)  scanf("%d",&a[i]);//故从高往低存储
    scanf("%d",&m2);
    for(int i = m2 - 1;i >= 0;i--)  scanf("%d",&b[i]);

    int m = max(m1,m2);//取较大的位数

    int res = 0;
    for(int i = m - 1;i >= 0;i--)//秦九韶算法
        res = (res * (ll)max({2,a[i] + 1,b[i] + 1}) + a[i] - b[i]) % mod;//最低得是二进制
    printf("%d",res);
    return 0;
}
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

F：统计子矩阵

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

输入格式
第一行包含三个整数 N,M 和 K。

之后 N 行每行包含 M 个整数，代表矩阵 A。

输出格式
一个整数代表答案。

数据范围
对于 30% 的数据，N,M ≤ 20，
对于 70% 的数据，N,M ≤ 100，
对于 100% 的数据，1 ≤ N,M ≤ 500;0 ≤ A_ij ≤ 1000;1 ≤ K ≤ 250000000。

输入样例：
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
输出样例：
19
样例解释
满足条件的子矩阵一共有 19，包含：

大小为 1×1 的有 10 个。
大小为 1×2 的有 3 个。
大小为 1×3 的有 2 个。
大小为 1×4 的有 1 个。
大小为 2×1 的有 3 个。
解析：
全在注释里了。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;

const int N = 510;

int n,m,k;
int s[N][N];//每一列的前缀和

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
        {//按列划分的一维前缀和
            scanf("%d",&s[i][j]);
            s[i][j] += s[i - 1][j];
        }

    ll res = 0;
    for(int i = 1;i <= n;i++)
        for(int j = i;j <= n;j++)//枚举一下上下边界
            for(int l = 1,r = 1,sum = 0;r <= m;r++)//枚举一下左右边界
            {
                sum += s[j][r] - s[i - 1][r];
                while(sum > k)
                {
                    sum -= s[j][l] - s[i - 1][l];
                    l++;
                }
                res += r - l + 1;//每次以r为右边界，一个长度、两个长度...共r - l + 1个
            }
    printf("%lld\n",res);
    return 0;
}
/*
思路：
把子矩阵的枚举转换一下，我们可以先固定上下边界(设左右边界分别为l和r)，那么接下来我们只需要看
在l~r之间的子矩阵之和是否小于等于k，由于我们固定了矩阵的上下边界，所以我们此时就只用枚举左右
连续几列的元素之和是否小于等于k。我们可以使用双指针枚举元素和sum <= k，如果sum <= k,以l为左边界，
以r为右端点，从以r为左端点一直枚举到以l为左端点的区间个数，它们都可以构成一个合法区间，且区间个数
为r-l+1，如果sum > k，我们就移动左端点使sum < k继续变成合法区间。
*/
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

G：积木画

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

同时，小明有一块面积大小为 2×N 的画布，画布由 2×N 个 1×1 区域构成。

小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？

积木可以任意旋转，且画布的方向固定。

输入格式
输入一个整数 N，表示画布大小。

输出格式
输出一个整数表示答案。

由于答案可能很大，所以输出其对 1000000007 取模后的值。

数据范围
1 ≤ N ≤ 10⁷。

输入样例：
3
输出样例：
5
样例解释
五种情况如下图所示，颜色只是为了标识不同的积木：

// #include<bits/stdc++.h>

// using namespace std;

// const int N = 1e7 + 10,mod = 1e9 + 7;

// int n;
// int g[4][4] = {
//     {1,1,1,1},
//     {0,0,1,1},
//     {0,1,0,1},
//     {1,0,0,0},
// };
// int f[N][4];//表示已经操作完前i - 1列，且第i列的状态为j的所有方案的集合

// int main()
// {
//     scanf("%d",&n);
//     f[1][0] = 1;

//     for(int i = 1;i <= n;i++)
//         for(int j = 0;j < 4;j++)
//             for(int k = 0;k < 4;k++)
//                 if(g[j][k])//提前判断，可以提高时间效率
//                     f[i + 1][k] = (f[i + 1][k] + f[i][j]) % mod;
//     printf("%d\n",f[n + 1][0]);
//     return 0;
// }

#include<bits/stdc++.h>

using namespace std;

const int N = 1e7 + 10,mod = 1e9 + 7;

int n;
int g[4][4] = {
    {1,1,1,1},
    {0,0,1,1},
    {0,1,0,1},
    {1,0,0,0},
};
int f[2][4];//滚动数组优化

int main()
{
    scanf("%d",&n);
    f[1][0] = 1;

    for(int i = 1;i <= n;i++)
    {
        memset(f[i + 1 & 1],0,sizeof(f[0]));
        for(int j = 0;j < 4;j++)
            for(int k = 0;k < 4;k++)
                if(g[j][k])//提前判断，可以提高时间效率
                    f[i + 1 & 1][k] = (f[i + 1 & 1][k] + f[i & 1][j]) % mod;
    }
    printf("%d\n",f[n + 1 & 1][0]);
    return 0;
}
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

H：扫雷

题目描述
小明最近迷上了一款名为《扫雷》的游戏。

其中有一个关卡的任务如下：

在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 (x_i,y_i,r_i) 表示在坐标 (x_i,y_i) 处存在一个炸雷，它的爆炸范围是以半径为 r_i 的一个圆。

为了顺利通过这片土地，需要玩家进行排雷。

玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (x_j,y_j,r_j) 表示这个排雷火箭将会在 (x_j,y_j) 处爆炸，它的爆炸范围是以半径为 rj 的一个圆，在其爆炸范围内的炸雷会被引爆。

同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。

现在小明想知道他这次共引爆了几颗炸雷？

你可以把炸雷和排雷火箭都视为平面上的一个点。

一个点处可以存在多个炸雷和排雷火箭。

当炸雷位于爆炸范围的边界上时也会被引爆。

输入格式
输入的第一行包含两个整数 n、m。

接下来的 n 行，每行三个整数 x_i,y_i,r_i，表示一个炸雷的信息。

再接下来的 m 行，每行三个整数 x_j,y_j,r_j，表示一个排雷火箭的信息。

输出格式
输出一个整数表示答案。

数据范围
对于 40% 的评测用例：0 ≤ x,y ≤ 10⁹,0 ≤ n,m ≤ 10³,1 ≤ r ≤ 10，
对于 100% 的评测用例：0 ≤ x,y ≤ 10⁹,0 ≤ n,m ≤ 5×10⁴,1 ≤ r ≤ 10。

输入样例：
2 1
2 2 4
4 4 2
0 0 5
输出样例：
2
样例解释
示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2 也被排除。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 5e4+10,M = 999997;//M开到近10倍
int n,m;
struct Circle
{
    int x,y,r;
}cir[N];
ll h[M];//哈希数组
int id[M];//哈希数组中key对应的地雷下标
bool st[M];//判断是否访问过

ll get_key(int x,int y)//得到每个坐标的哈希值
{
    return x * 100000000ll + y;
}

int find(int x,int y)
{
    ll key = get_key(x,y);
    int t = (key % M + M) % M;
    while(h[t] != -1 && h[t] != key)//如果该位置被占了且并不等于我们要求的哈希值,继续查找
        if(++t == M)//哈希表走到末尾，又从0开始
            t = 0;
    return t;
}

int sqr(int x)
{
    return x * x;
}

void dfs(int x,int y,int r)
{
    st[find(x,y)] = true;
    for(int i = x - r;i <= x + r;i++)
        for(int j = y - r;j <= y + r;j++)//枚举长方形
            if(sqr(i - x) + sqr(j - y) <= sqr(r))//判断在圆内
            {
                int t = find(i,j);
                if(id[t] && !st[t])
                    dfs(i,j,cir[id[t]].r);
            }
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    for(int i = 1;i <= n;i++)
    {
        int x,y,r;
        scanf("%d%d%d",&x,&y,&r);

        cir[i] = {x,y,r};
        int t = find(x,y);//找到该坐标点对应的哈希下标
        if(h[t] == -1)  h[t] = get_key(x,y);//如果哈希对应位置为空，则插入

        if(!id[t] || cir[id[t]].r < r)//id数组没有被标记或者找到了同一个坐标点更大半径的地雷
            id[t] = i;
    }

    while(m--)
    {
        int x,y,r;
        scanf("%d%d%d",&x,&y,&r);
        for(int i = x - r;i <= x + r;i++)
            for(int j = y - r;j <= y + r;j++)
                if(sqr(i - x) + sqr(j - y) <= sqr(r))//判断是否在半径为r的圆内
                {
                    int t = find(i,j);
                    if(id[t] && !st[t])//如果有地雷并且没有并访问过
                        dfs(i,j,cir[id[t]].r);
                }
    }
    int res = 0;
    for(int i = 1;i <= n;i++)//遍历每个地雷，看是否被标记
        if(st[find(cir[i].x,cir[i].y)])
            res++;
    printf("%d\n",res);
    return 0;
}
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

I：李白打酒加强版

题目描述
话说大诗人李白，一生好饮。

幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。

他边走边唱：

无事街上走，提壶去打酒。

逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店 N 次，遇到花 M 次。

已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？

注意：壶里没酒 (0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

输入格式
第一行包含两个整数 N 和 M。

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

数据范围
对于 40% 的评测用例：1 ≤ N,M ≤ 10。
对于 100% 的评测用例：1 ≤ N,M ≤ 100。

输入样例：
5 10
输出样例：
14
样例解释
如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：

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

#include<bits/stdc++.h>

using namespace std;

const int N = 110,mod = 1e9 + 7;
int n,m;
int f[N][N][N];//经过了i个店，j个花，手里有k斗酒

int main()
{
    cin >> n >> m;
    f[0][0][2] = 1;
    for(int i = 0;i <= n;i++)
        for(int j = 0;j <= m;j++)
            for(int k = 0;k <= m;k++)//酒的量若是超过m就即使一直减也不可能减完，故k最大为m
            {
                int& v= f[i][j][k];
                if(i && k % 2 == 0) v = (v + f[i - 1][j][k / 2]) % mod;//k必须是偶数
                if(j)   v = (v + f[i][j - 1][k + 1] % mod);
            }
    cout << f[n][m - 1][1] << endl;
    return 0;
}
/*
最后一步是f[i,j,k]，上一步有两种情况:上一步是店或上一步是花
若上一步是店:即为f[i - 1][j][k / 2]，因为是遇到店才到的f[i,j,k]状态，酒量加倍，那么k必须为偶数，i - 1也必须得非负
若上一步是花:即为f[i][j - 1][k + 1]，因为遇到了花，所以上一步的酒量得比当前多1，且j - 1必须非负
*/
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

J：砍竹子

题目描述
这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 hi。

他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。

魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以把这一段竹子的高度都变为 ⌊sqrt(⌊H/2⌋+1)⌋，其中 ⌊x⌋ 表示对 x 向下取整。

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

输入格式
第一行为一个正整数 n，表示竹子的棵数。

第二行共 n 个空格分开的正整数 h_i，表示每棵竹子的高度。

输出格式
一个整数表示答案。

数据范围
对于 20% 的数据，保证 1 ≤ n ≤ 1000,1 ≤ h_i ≤ 10⁶。
对于 100% 的数据，保证 1 ≤ n ≤ 2×10⁵,1 ≤ h_i ≤ 10¹⁸。

输入样例：
6
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 步完成。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 200010,M = 10;
int n,m;
ll f[N][M];

int main()
{
    scanf("%d",&n);
    ll stk[M];

    int res = 0;
    for(int i = 0;i < n;i++)
    {
        ll x;
        int top = 0;
        scanf("%lld",&x);
        while(x > 1)    stk[++top] = x,x = sqrt(x / 2 + 1);//计算有多少层
        res += top;
        m = max(m,top);//m是最大层数
        for(int j = 0,k = top;k;j++,k--)
            f[i][j] = stk[k];//低位对齐，可由一个图清晰描绘
    }

    for(int i = 0;i < m;i++)
        for(int j = 1;j < n;j++)
            if(f[j][i] && f[j][i] == f[j - 1][i])
                res--;//如果层数相同就减减
                
    printf("%d\n",res);
    return 0;
}
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