第十三届蓝桥杯C++ B组省赛编程题详解 第一题：刷题统计 题目描述

【Tag：枚举】
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。

创新互联公司-专业网站定制、快速模板网站建设、高性价比新密网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式新密网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖新密地区。费用合理售后完善，10年实体公司更值得信赖。

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

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

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

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

数据范围
对于 50% 的评测用例， 1 ≤ a , b , n ≤ 1 0 6 {1≤a,b,n≤10^6} 1≤a,b,n≤106，
对于 100% 的评测用例， 1 ≤ a , b , n ≤ 1 0 18 {1≤a,b,n≤10^{18}} 1≤a,b,n≤1018。

输入样例：

10 20 99

输出样例：

8

思路分析

我们可以先统计出每周刷题数目s，然后求出有多少个整周的天数res。

接着求出我们还要做多少题目n,最后把余数加起来即可。

注意：数据范围一定要考虑！！！

实现

#include#include#include 

using namespace std;

typedef long long LL;

LL a, b, n;

int main()
{
    scanf("%lld%lld%lld", &a, &b, & n);
    
    LL s = 5 * a + 2 * b; //每周的刷题数
    LL res = n / s * 7; //整周的天数
    n %= s; //剩余的题目数量
    
    LL d[] = {a, a, a, a, a, b, b};
    for (int i = 0; n >0; i ++)
    {
        n -= d[i];
        res ++;
    }
    
    printf("%lld\n", res);
    return 0;
}

第二题：修建灌木 题目描述

【Tag：模拟】
爱丽丝要完成一项修剪灌木的工作。有N棵灌木整齐的从左到右排成一排。

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

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

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

直到修剪了最左的灌木后再次调转方向。然后如此循环往复。

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

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

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

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

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

输入样例：

3

输出样例：

4
2
4

思路分析

我们可以简单的模拟出每棵树的高度变化。

每棵树的高度：

天数	第一棵树	第二棵树	第三棵树	第四棵树	第五棵树
①	1	1	1	1	1
②	1	2	2	2	2
③	2	1	3	3	3
④	3	2	1	4	4
⑤	4	3	2	1	5
⑥	5	4	3	2	1
⑦	6	5	4	1	2
⑧	7	6	1	2	3
⑨	8	1	2	3	4
⑩	1	2	3	4	5
…	…	…	…	…	…

注意：加粗的数字为我们要修剪的树木。

我们可以看出是一个循环的序列，总结出每个树可以长到的大高度为max(i - 1, n - i ) * 2

实现

#include#include#include 

using namespace std;
const int N = 10010;
int n, a[N];

int main()
{
    cin >>n;
    
    for (int i = 1; i<= n; i ++ )
    {
        cout<< max(i - 1, n - i) * 2<< endl;
    }
    
    return 0;
}

第三题： X 进制减法 题目描述

【Tag：数学】
进制规定了数字在数位上逢几进一。

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

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

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

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

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

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

第二行一个正整数 M a {M_a} Ma​，表示 X 进制数 A 的位数。

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

第四行一个正整数 M b {M_b} Mb​，表示 X 进制数 B 的位数。

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

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

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

数据范围
对于 30% 的数据， N ≤ 10 ; M a , M b ≤ 8 {N≤10;M_a,M_b≤8} N≤10;Ma​,Mb​≤8，
对于 100% 的数据， 2 ≤ N ≤ 1000 ; 1 ≤ M a , M b ≤ 100000 ; A ≥ B {2≤N≤1000;1≤M_a,M_b≤100000;A≥B} 2≤N≤1000;1≤Ma​,Mb​≤100000;A≥B。

输入样例：

11
3
10 4 0
3
1 2 0

输出样例：

94

样例解释
当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。

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

思路实现：

我们平常所见到的数字，他的每一位数的进制都是相同的，每位数字的权重是 X n {X^n} Xn（n为该位数字后面的位数），比如二进制1000中首位的1的权重是 2 3 {2^3} 23=8。

对于题目中的样例，某种X进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则X进制数321转换为十进制数为65。

使用记次数的方式理解进制

最低位为二进制，“逢二进一”，最低为为1；

第二位为十进制，“逢十进一”，计数法进位会经过0,1,10,11,20，所以我们数 2 × 2 {2 × 2} 2×2次便会得到2。

第三位为八进制，“逢八进一”，计数法进位会经过0,1,10,11,20,21,30,31,40,41,50,51,60,61,70,71,80,81,90,91,100,…310,311,320,321，结束计数，我们会经过 3 × 10 × 2 {3 × 10 × 2 } 3×10×2次得到3。

由此我们可以看出在本题各位数字进制不同情况下，该位数字的权重其实是后面各位数字的进制的乘积。

进制类似于盖大楼，要想高数位上有数字，就必须时底数位上有数字，并且满足条件。

对于任意一个P我们可以将其分为两部分：包含P与不包含P。

所以我们每次取最小值时，必须满足每一位进制P取最小值即可。
最小值为{a_i+1,b_i+1,2}，这三个数取最小值。（此处的+1，与2防止出现1进制）。
使用秦九韶算法进行进制计算的优化

实现

#include#include#include 

using namespace std;
typedef long long LL;
const int N = 100010, MOD = 1000000007;
int n, m1, m2;
int a[N], b[N];

int main()
{
    cin >>n;
    cin >>m1;
    for (int i = m1 - 1; i >= 0; i -- )  cin >>a[i];//逆序存储，使得个位数字对齐，便于计算
    cin >>m2;
    for (int i = m2 - 1; i >= 0; i -- )  cin >>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;
    }
    
    cout<< res<< endl;
    return 0;
}

第四题：统计子数组

【Tag：前缀和， 双指针】

给定一个 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≤2.5×10^8。

输入样例：

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 个。

思路描述

我们要求出满足条件（子矩阵的和不超过K的矩阵数量），先使用前缀个处理出数组和。然后采用暴力去求解问题，发现每一维都有500的范围，所以我们的时间复杂度会在 50 0 4 {500^4} 5004左右，会面临超时的风险。

我们使用双指针进行优化，我们可以先确定出上下边界，然后动态去求解左右边界。

优化方法为：

1. 依次枚举子矩阵的上下边界i，j；
2. 使用双指针来维护子矩阵的左右边界l，r，r为快指针，l为慢指针。
3. 求出以i，j为上下边界，以l，r为左右边界的子矩阵的和sum；
4. 调整慢指针l，当计算得到的子矩阵和sum大于K时，我们让l向右移动。当l向右移动的时候，子矩阵和sum必然会单调不增。当计算子矩阵和sum不超过K的时候，慢指针l移动结束；
5. 最后所有满足条件的子矩阵数量为r - l + 1;

优化之后时间复杂度为 O ( N 3 ) {O(N^3)} O(N3)。

实现

#include#include#include 
using namespace std;

const int N = 510;
typedef long long LL;
LL a[N][N];
int n, m, K;


int main()
{
    scanf("%d%d%d", &n, &m, &K);
    //输入A数组，预处理前缀和
    for (int i = 1; i<= n; i ++)
        for (int j = 1; j<= m; j ++)
        {
            scanf("%lld", &a[i][j]);
            a[i][j] += a[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 += a[j][r] - a[i - 1][r];//计算当前子矩阵的和
                while(sum >K) //当子矩阵和大于K时， l++
                {
                    sum -= a[j][l] - a[i - 1][l];
                    l ++;
                }
                res += r - l + 1;
            }
    cout<< res<< endl;
    return 0;
}

第五题：积木画

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

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

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

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

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

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

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

数据范围
1 ≤ N ≤ 1 0 7 {1≤N≤10^7} 1≤N≤107。

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

思路描述

状态压缩DP类型。

状态表示：f[i][j]表示前i - 1个位置已经确定，并且第i个状态为j的方案。

状态计算：因为此题的转换数量很少，只有16种可能，所以我们进行枚举即可。

实现

朴素版：时间高，空间高

#include#include#include 

using namespace std;

const int N = 1e7 + 10, MOD = 1000000007;

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];

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 ++ )
                f[i + 1][k] = (f[i + 1][k] + f[i][j] * g[j][k]) % MOD;
    }
    
    printf("%d\n", f[n + 1][0]);
    
    return 0;
}

使用滚动数组优化：空间低，时间高

#include#include#include 

using namespace std;

const int N = 1e7 + 10, MOD = 1000000007;

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 ++ )
                f[i + 1 & 1][k] = (f[i + 1 & 1][k] + f[i & 1][j] * g[j][k]) % MOD;
    }
    
    printf("%d\n", f[n + 1 & 1][0]);
    
    return 0;
}

优化常数：空间低，时间低

#include#include#include 

using namespace std;

const int N = 1e7 + 10, MOD = 1000000007;

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;
}

第六题：扫雷

【Tag: 哈希表，搜索】
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下：

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

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

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

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

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

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

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

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

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

接下来的 n 行，每行三个整数 x i , y i , r i {x_i,y_i,r_i} xi​,yi​,ri​，表示一个炸雷的信息。

再接下来的 m 行，每行三个整数 x j , y j , r j {x_j,y_j,r_j} xj​,yj​,rj​，表示一个排雷火箭的信息。

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

数据范围
对于 40% 的评测用例： 0 ≤ x , y ≤ 1 0 9 , 0 ≤ n , m ≤ 1 0 3 , 1 ≤ r ≤ 10 {0≤x,y≤10^9,0≤n,m≤10^3,1≤r≤10} 0≤x,y≤109,0≤n,m≤103,1≤r≤10，

对于 100% 的评测用例： 0 ≤ x , y ≤ 1 0 9 , 0 ≤ n , m ≤ 5 × 1 0 4 , 1 ≤ r ≤ 10 {0≤x,y≤10^9,0≤n,m≤5×10^4,1≤r≤10} 0≤x,y≤109,0≤n,m≤5×104,1≤r≤10。

输入样例：
2 1
2 2 4
4 4 2
0 0 5
输出样例：
2

样例解释

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

思路描述

手写哈希表+搜索

实现

#include#include#includeusing namespace std;

const int N = 5e4 + 10, M = 1e6 + 7, X = 1e9 + 1;
int n, m;
struct node {
    int x, y, r;
}b[N];
typedef long long ll;
ll h[M]; // 哈希数组
bool st[N]; // 判断是否访问过
int id[M], res; // id数组为哈希数组中key对应的地雷下标

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

int find(int x, int y) { // 找到该坐标被哈希数组存储的下标key
    ll hs = get_hs(x, y);
    int key = (hs % M + M) % M; // 映射到哈希数组内部
    // 如果该位置已经被占用并且不等于我们要求的哈希值，要在之后找到相应位置
    while(h[key] != -1 && h[key] != hs) { 

        key++;
        if(key == M) key = 0; // 哈希表走到末尾，又从0开始
    }
    return key;
}

// 判断x1，y1为圆心，半径为r的圆是否包含x，y
bool check(int x1, int y1, int r, int x, int y) { 
    int d = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
    return d<= r * r;
}

void bfs(int pos) {
    queueq;
    q.push(pos);
    st[pos] = 1;
    while(q.size()) {
        int t = q.front();
        q.pop();
        int x = b[t].x, y = b[t].y, r = b[t].r;
        for(int xx = x - r; xx<= x + r; xx++) { // 从(x-r, y-r)枚举到(x+r, y+r)
            for(int yy = y - r; yy<= y + r; yy++) {
                int key = find(xx, yy); // 找到该坐标点对应的哈希下标
                // 该点是不是地雷，有没有被访问过，能不能炸到 
                if(id[key] && !st[id[key]] && check(x, y, r, xx, yy)) { 
                    int pos = id[key]; // 获得对应地雷编号
                    st[pos] = 1;
                    q.push(pos);
                }
            }
        }
    }
}

int main() {
    cin >>n >>m;
    memset(h, -1, sizeof(h));
    int x, y, r;
    for(int i = 1; i<= n; i++) { // 读入地雷，存入哈希表
        cin >>x >>y >>r;
        b[i] = {x, y, r};
        int key = find(x, y);// 找到该坐标点对应的哈希下标
        if(h[key] == -1) h[key] = get_hs(x, y); // 如果哈希对应位置为空，则插入

        // id数组没有被标记或者找到了同一个坐标点更大半径的地雷
        if(!id[key] || b[id[key]].r< r) { 
            id[key] = i;
        }
    }
    for(int i = 1; i<= m; i++) { // 枚举导弹
        cin >>x >>y >>r;
        for(int xx = x - r; xx<= x + r; xx++) {
            for(int yy = y - r; yy<= y + r; yy++) {
                int key = find(xx, yy);

                // 如果该点有地雷，没有被访问过，能被炸到
                if(id[key] && !st[id[key]] && check(x, y, r, xx, yy)) bfs(id[key]);
            }
        }
    }
    // 遍历每个地雷，看是否被标记
    for(int i = 1; i<= n; i++) {
        int key = find(b[i].x, b[i].y); // 获得坐标点对应哈希下标
        int pos = id[key]; // 哈希下标对应的地雷编号
        if(pos && st[pos]) res++; // 如果有地雷并且被访问过
    }
    cout<< res;
    return 0;
}

第七题：李白打酒加强版

【Tag：DP】
话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒 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

思路描述

动态规划题，使用闫氏DP分析法求解。

状态表示：f(i,j,k)分别表示为经过第i朵店，第j个花时，酒壶中酒的数量为k。

状态属性：数量。

状态计算：

分为两种：

1. f(i - 1, j, k / 2):遇到的是店，说明此前遇到店的数量为i - 1，遇到花的数量仍然为j，酒壶中酒的数量为k/2;满足条件i大于等于1，k能被二整除
2. f(i, j - 1, k + 1):遇到的是花，说明此前遇到店的数量为i，遇到花的数量为j - 1，酒壶中酒的数量为k + 1。满足条件j大于等于1

实现

#include#include#include 

using namespace std;

const int N = 110, MOD = 1e9 + 7;

int n, m;
int f[N][N][N];

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 ++ )
            {
                int& v = f[i][j][k];
                if (i && k % 2 == 0) v = (v + f[i - 1][j][k / 2]) % MOD;
                if (j) v = (v + f[i][j - 1][k + 1]) % MOD;
            }

    cout<< f[n][m - 1][1]<< endl; //输出最后一步，经过了n个店，m - 1朵花，酒壶中剩余的酒为1
    return 0;
}

第八题：砍竹子

这天，小明在砍竹子，他面前有n棵竹子排成一排，一开始第i棵竹子的高度为 h i {h_i} hi​。

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

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

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

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

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

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

数据范围
对于 20% 的数据，保证 1 ≤ n ≤ 1000 , 1 ≤ h i ≤ 1 0 6 {1≤n≤1000,1≤h_i≤10^6} 1≤n≤1000,1≤hi​≤106 。
对于 100% 的数据，保证 1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ h i ≤ 1 0 18 {1≤n≤2×10^5,1≤h_i≤10^{18}} 1≤n≤2×105,1≤hi​≤1018。

输入样例：

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#include#include 
#includetypedef long long LL;

int main()
{
    LL x = 1e18;
    while(x != 1) {
        x = sqrt(x / 2 + 1);
        printf("%lld\n", x);
    }
    return 0;
}

输出结果为

707106781
18803
96
7
2
1

可以看出每个数大的操作次数为6次，题目的数据量为 1 ≤ n ≤ 2 × 1 0 5 {1≤n≤2×10^5} 1≤n≤2×105,所以我们可以使用暴力法去求解。

我们先对每个数进行预处理，将预处理后的数据存储起来，题目中说我们可以对连续的一段相同高度的竹子进行操作，所以我们在判断连续的一段竹子的高度是否相等即可。

实现

#include#include 
#include#includeusing namespace std;
typedef long long LL;
const int N = 200010, M = 10;
int f[N][M];
int 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);//对x进行预处理，每次向栈顶加入x处理后的结果
        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;
}

调研

主要想收集一下，阅读者对我书写文章、题解时的建议或者看法。

欢迎各位读者留言，评论。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文题目：【第十三届蓝桥杯C++B组省赛编程题详解】-创新互联
文章路径：http://kswsj.cn/article/psgjc.html