试题A: 九进制转十进制

本题总分:5分

【问题描述】

九进制正整数 (2022), 转换成十进制等于多少?

【答案提交】

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

题解：进制转换

2 * 9^0 + 2 * 9^1 + 0 + 2 * 9^3 = 1478

1

试题B: 顺子日期

本题总分:5分

【问题描述】

小明特别喜欢顺子。顺子指的就是连续的三个数字:123、456等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如20220123就是一个顺子日期，因为它出现了一个顺子: 123; 而20221023则不是一个顺子日期，它一个顺子也没有。小明想知道在整个2022年份中，一共有多少个顺子日期。

【答案提交】

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

题解：日历

很多人在讨论 012 算不算顺子，因为题目里说 0123 中的顺子是 123，我是算了的，不算的话答案应该是 4

年份 2022 是不变的，而且不可能搭上顺子，所以只考虑后四位即可

可能搭上顺子的月份有：

   1月：0120 ~ 0129 共 10 个，顺子是 012 (其中 0123 可以认为顺子是 123)

   10月：1012，顺子是 012

   11月：1123，顺子是 123

   12月：1230，1231，顺子是 123

一共 14 个

蓝桥杯2022年第十三届省赛真题-刷题统计

时间限制: 1s 内存限制: 256MB 提交: 8920 解决: 1735

题目描述

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？

输入格式

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

输出格式

输出一个整数代表天数。

样例输入

复制

10 20 99

样例输出

复制

8

提示

对于 50% 的评测用例，1 ≤ a, b, n ≤ 106 . 对于 100% 的评测用例，1 ≤ a, b, n ≤ 1018 .

80分解法：

#include<stdio.h>

long long int f(long long int n,long long int a,long long int b)      //n代表总题数,a代表星期一到星期五做的题的数量,b代表星期六和星期天做题的数量

{

   int flag;

   long long int sum=0;          //flag用来记录最后是在1-5停的,还是在6-7停的

   while(n!=0)

   {

       n-=5*a;                 //先算1-5

       if(n<0)

       {

           flag=1;

           break;

       }

       sum+=5;

       n-=2*b;                  //再算6-7

       if(n<0)

       {

           flag=2;

           break;

       }

       sum+=2;

   }

   if(flag==1)               //如果是在1-5停的话

   {

       n+=5*a;                //加回来,然后算是在第几天的

       while(n>a)

       {

           n-=a;

           sum++;

       }

       sum++;                //不满一天就加回去

   }

   else if(flag==2)

   {

       n+=2*b;

       while(n>b)

       {

           n-=b;

           sum++;

       }

       sum++;

   }

   return sum;

}

int main()

{

   long long int a,b,n;

   scanf("%lld%lld%lld",&a,&b,&n);

   printf("%lld",f(n,a,b));

   return 0;

}

AC代码：

解题思路:

先用ans表示有多少周，n/(5*a+b*2)

工作日有二天，周末有二天

sum表示天数

用n-（5*a+2*b）*ans=剩余的天数

剩余的天数一定会落在工作日，或者周末这两种情况；

再用(n-(5*a+2*b)*ans)/a表示能在工作日完成的a题，

如果(n-(5*a+2*b)*ans)%a 不等于0，说明有剩余，还要加一天

在周末这种情况也同理；

注意事项:对于 100% 的评测用例，1 ≤ a, b, n ≤ 1018，要用long long

参考代码:

#include<bits/stdc++.h>

using namespace std;

int main()

{

   long long a,b,n;

   long long ans=0,sum=0;

   scanf("%lld%lld%lld",&a,&b,&n);

   ans+=n/(5*a+b*2);

   sum=ans*7;

   if((n-(a*5+b*2)*ans)<=5*a)

   {

       sum+=(n-(5*a+2*b)*ans)/a;

       if((n-(5*a+2*b)*ans)%a!=0)

       {

           sum++;

       }

   }

   else

   {

       sum+=5;

       sum+=((n-(5*a+2*b)*ans)-5*a)/b;

       if(((n-(5*a+2*b)*ans)-5*a)%b!=0)

       {

           sum++;

       }

   }

   printf("%lld",sum);

}

题目 2657: 蓝桥杯2022年第十三届省赛真题-修剪灌木

时间限制: 1s 内存限制: 256MB 提交: 2361 解决: 1502

题目描述

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

输入格式

一个正整数 N ，含义如题面所述。

输出格式

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

样例输入

3

样例输出

4

2

4

提示

对于 30% 的数据，N ≤ 10. 对于 100% 的数据，1 < N ≤ 10000.

#include<stdio.h>

int main()

{

   int n;

   int a[10005];

   scanf("%d",&n);

   if(n%2==0)//n为偶数的时候

   {

       for(int i=1;i<=n/2;i++)

       {

           a[i]=2*(n-i);

           printf("%d\n",a[i]);

       }

       for(int j=n/2+1;j<=n;j++)

       {

           a[j]=a[n+1-j];

           printf("%d\n",a[j]);

       }

   }

   if(n%2!=0)//n为奇数的时候

   {

       for(int i=1;i<=n/2;i++)

       {

           a[i]=2*(n-i);

           printf("%d\n",a[i]);

       }

       printf("%d\n",n-1);

       for(int j=n/2+2;j<=n;j++)

       {

           a[j]=a[n+1-j];

           printf("%d\n",a[j]);

       }

   }

   return 0;

}

题目 2658: 蓝桥杯2022年第十三届省赛真题-X进制减法

时间限制: 1s 内存限制: 256MB 提交: 2258 解决: 651

题目描述

进制规定了数字在数位上逢几进一。

X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 X 进制数 321 转换为十进制数为 65。

现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A − B 的结果最小可能是多少。

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

输入格式

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

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

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

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

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

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

输出格式

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

样例输入

11

3

10 4 0

3

1 2 0

样例输出

94

提示

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

对于 30% 的数据，N ≤ 10; Ma, Mb ≤ 8. 对于 100% 的数据，2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B.

解题背景

1：理解进制的转化算法

2：理解如何达到最小值

注意：

  1：如何是使得差值最小呢，我们可以利用dp的思想，要使得整体最小，那么组成他的各个部分也是最小，那么问题就变成了，如何使得各个部分的值最小；

  2：每个部分有对应位上的差值组成，那么，要使得这个差值乘的进制数尽可能小就可以了；

  3：如何使得进制尽可能小呢，进制的区间在2~N之间，那么只需要在这个区间之内，选取能包含a[i]和b[i]两个值的最小进制值就ok了，至此，思路就出来了

代码

#include<stdio.h>

int a[100005]={0};

int b[100005]={0};

int mod= 1000000007;

int max(int x,int y)

{

   return x>y?x:y;

}

int main()

{

   //录入数据

   int N,Ma,Mb;

   scanf("%d%d",&N,&Ma);

   for(int i=Ma;i>=1;i--)

   {

       scanf("%d",&a[i]);

   }

   scanf("%d",&Mb);

   for(int i=Mb;i>=1;i--)

   {

       scanf("%d",&b[i]);

   }

   //处理获取进制数组

   int jz[100005]={0};

   for(int i=Ma;i>=1;i--)//A-B以A 的位数为标准

   {

       jz[i]=max(max(a[i]+1,b[i]+1),2);//找出对应位置上最小的进位，且进位不小于2

       //printf("%d ",jz[i]);

   }

   //printf("\n");

/*    //处理得到对应为的乘数 （超时O（n^2），换一种搞法）

   int cs[100005]={0};

   for(int i=Ma;i>=1;i--)

   {

       cs[i]=1;

       for(int j=i-1;j>=1;j--)//乘数不包括自身进位值

       {

           cs[i]*=jz[j];

       }

       //printf("%d ",cs[i]);

   }

   //printf("\n");

   //处理得到最小值的和

   int sum=0;

   for(int i=Ma;i>=1;i--)//从高位加起

   {

       sum+=(a[i]-b[i])*cs[i];

       sum%=mod;

   }*/

   long long sum=0;

   for(int i=Ma;i>=2;i--)

   {

       sum=((sum+a[i]-b[i])*jz[i-1])%mod;

   }

   sum+=(a[1]-b[1]);

   printf("%lld\n",sum);

   return 0;    

}

试题F: 统计子矩阵

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

【问题描述】

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

【输入格式】

第一行包含三个整数N,M和K.

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

【输出格式】

一个整数代表答案。

【样例输入】

3 4 10

1 2 3 4

5 6 7 8

9 10 11 12

1

2

3

4

【样例输出】

19

1

【样例说明】

满足条件的子矩阵一共有19，包含:

大小为1×1的有10个。

大小为1×2的有3个。

大小为1×3的有2个。

大小为1×4的有1个。

大小为2×1的有3个。

【评测用例规模与约定】

对于30%的数据, N, M ≤ 20.

对于70%的数据，N, M ≤ 100.

对于100%的数据，1 ≤ N,M ≤ 500; 0 ≤ Aij ≤1000;1 ≤ K ≤ 250000000.

题解：二维前缀和+二分

一看题就想到前缀和了，不过暴力枚举的话肯定超时了，想了个半枚举+二分查找的歪点子，时间复杂度大概 是O(n^3 * log(n))，大概有 10^9 了，再加上一点剪枝，能不能过看运气了

假设 (i, j) 是子矩阵的起点坐标，(x, y) 是终点坐标，枚举 i, j, x，二分查找符合条件的最大 y，就是找起点为 (i, j) ，终点在第 x 行最多有多少个矩阵

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

const int N = 505;

ll m, n, k;

ll a[N][N];

ll ans = 0;

ll getsum(int i, int j, int x, int y) {

return a[x][y] - a[i - 1][y] - a[x][j - 1] + a[i - 1][j - 1];

}

int main() {

cin >> m >> n >> k;

for (int i = 1; i <= m; i++) {

 for (int j = 1; j <= n; j++) {

  cin >> a[i][j];

  a[i][j] += a[i - 1][j] - a[i - 1][j - 1] + a[i][j - 1];

 }

}

for (int i = 1; i <= m; i++) {

 for (int j = 1; j <= n; j++) {

  if (getsum(i, j, i, j) > k) continue;

  for (int x = i; x <= m; x++) {

   int l = j, r = n;

   while (l < r) {

    int mid = (l + r + 1) >> 1;

    if (getsum(i, j, x, mid) > k) r = mid - 1;

    else l = mid;

   }

   if (getsum(i, j, x, l) > k) break;

   ans += l - j + 1;

  }

 }

}

cout << ans << endl;

return 0;

}

真·题解：前缀和 + 连续子段个数

这题有解了，其实是个套路题

先确定子矩阵的两个列边界，然后做一次行遍历，就是求符合条件的连续子段个数（双指针滑动窗口），复杂度缩小到 O(n^3)

由于每次只需拿到某一行内的和，只做一维前缀和即可

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

const int N = 505;

ll m, n, k;

ll a[N][N];

ll ans = 0;

int main() {

cin >> m >> n >> k;

for (int i = 1; i <= m; i++) {

 for (int j = 1; j <= n; j++) {

  cin >> a[i][j];

  a[i][j] += a[i][j - 1];

 }

}

for (int i = 1; i <= n; i++) {

 for (int j = i; j <= n; j++) {

  int left = 1;

  ll cur = 0;

  for (int right = 1; right <= m; right++) {

   cur += a[right][j] - a[right][i - 1];

   while (cur > k) {

    cur -= a[left][j] - a[left][i - 1];

    left++;

   }

   ans += right - left + 1;

  }

 }

}

cout << ans << endl;

return 0;

}

试题G: 积木画

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

【问题描述】

小明最近迷上了积木画，有这么两种类型的积木，分别为Ⅰ型(大小为2个单位面积)和L型(大小为3个单位面积):

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

【输入格式】

输入一个整数N,表示画布大小。

【输出格式】

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

【样例输入】

3

【样例输出】

5

【样例说明】

五种情况如下图所示，颜色只是为了标识不同的积木;

【评测用例规模与约定】

对于所有测试用例，1 ≤ N ≤ 10000000.

题解：动态规划（错解）

要摆出 n 列方格，可以在 n - 1 列方格后加一个竖着的 I 形积木，也可以在 n - 2 方格后加两个横着的 I 形积木，也可以在 n - 3 列方格上后加 两个 L 形积木的两种摆法

用 dp[i] 表示 i 列方格的摆法

则有，当 i >= 3 时 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] * 2;

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

const int N = 10000005;

int n;

ll dp[N];

int main() {

cin >> n;

dp[0] = dp[1] = 1;

dp[2] = 2;

for (int i = 3; i <= n; i++) {

 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] * 2;

 dp[i] %= MOD;

}

cout << dp[n] << endl;

return 0;

}

思路想的太简单了，寄！

题解：动态规划

看过别人说的，可以先放一个 L 形，再连续放若干个横着的 I 形积木，末尾再放一个 L 形，直接一记重锤打脑门上

然而还有另一种情况：

话说蓝桥故意只放一个小样例是不是不太好（虽然确实考验思维就是了）

那么在上面错解的基础上，要摆出 n 列方格，还可以由（n - 4, n - 5, n - 6, n - 7, ……）转换而来

也就有：

① dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] * 2 + dp[i - 4] * 2+ dp[i - 5] * 2 + …… + * dp[1] * 2

② dp[i - 1] = dp[i - 2] + dp[i - 3] + dp[i - 4] * 2 + dp[i - 4] * 2+ dp[i - 5] * 2 + …… + * dp[1] * 2

① - ② 得出 dp[i] - dp[i - 1] = dp[i - 1] + dp[i - 3] 即 dp[i] = dp[i - 1] * 2 + dp[i - 3]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

const int N = 10000005;

int n;

ll dp[N];

int main() {

cin >> n;

dp[1] = 1;

dp[2] = 2;

dp[3] = 5;

for (int i = 4; i <= n; i++) {

 dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % MOD;

}

cout << dp[n] << endl;

return 0;

}

试题H:扫雷

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

【问题描述】

小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下，在一个二维平面上放置着 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，表示一个排雷火箭的信息。

【输出格式】

输出一个整数表示答案。

【样例输入】

2 1

2 2 4

4 4 2

0 0 5

1

2

3

4

【样例输出】

2

1

【样例说明】

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

【评测用例规模与约定】

对于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.

题解：广搜

比赛时没看到题里说一个点可以有多个雷，又寄！

坐标的范围 10^9 太大了，于是用哈希表放 pair，同一个点上的多个雷，可以状态压缩一下，用百位开始放雷的个数，个位放最大半径

队列里放将要爆炸的雷，集合放已经被扫描到的雷

还是比较偏暴力的，不知道行不行

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct point {

int x, y, r;

point(int xx, int yy, int rr) : x(xx), y(yy), r(rr) {}

};

double get_len(int i, int j, int  x, int y) {

return sqrt((i - x) * (i - x) + (j - y) * (j - y));

}

map<pair<int, int>, int> mp;

queue<point> q;

set<pair<int, int> > s;

int m, n;

ll ans = 0;

int main() {

cin >> n >> m;

int x, y, r;

for (int i = 0; i < n; i++) {

 cin >> x >> y >> r;

 int tmp = mp[make_pair(x, y)] + 100;

 mp[make_pair(x, y)] = max(tmp, tmp / 100 * 100 + r);

}

for (int i = 0; i < m; i++) {

 cin >> x >> y >> r;

 q.push(point(x, y, r));

}

while (!q.empty()) {

 point po = q.front();

 x = po.x, y = po.y, r = po.r;

 q.pop();

 for (int i = x - r; i <= x + r; i++) {

  for (int j = y - r; j <= y + r; j++) {

   pair<int, int> pir(i, j);

   if (s.count(pir)) continue;

   if (!mp.count(pir)) continue;

   if (get_len(i, j, x, y) > r) continue;

   s.insert(pir);

   q.push(point(i, j, mp[pir] % 100));

   ans += mp[pir] / 100;

  }

 }

}

cout << ans << endl;

return 0;

}

试题:李白打酒加强版

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

【问题描述】

话说大诗人李白，一生好饮。幸好他从不开车。

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

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

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

这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花，他正好把酒喝光了。

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

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

【输入格式】

第一行包含两个整数 N 和 M.

【输出格式】

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

【样例输入】

5 10

1

【样例输出】

14

1

【样例说明】

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

010101101000000

010110010010000

011000110010000

100010110010000

011001000110000

100011000110000

100100010110000

010110100000100

011001001000100

100011001000100

100100011000100

011010000010100

100100100010100

101000001010100

【评测用例规模与约定】

对于40%的评测用例: 1 ≤ N, M ≤ 10。

对于100%的评测用例: 1 ≤ N, M ≤ 100。

题解：记忆化搜索+剪枝

比较容易想到的是深搜，取令 n - 1 和令 m - 1 的结果相加，在此基础上有几个规则用来剪枝

用 k 来表示酒的数量：

假如 k == 0，必须有 m == n == 0，结果为 1，否则无解，因为最后一次遇到的必须是花，而且没酒时遇花是不合法的

假如 k > m, 一定无解

假如 k != 0 且 n >= m ，一定无解

假如 n == 0，必须有 k == m，结果为 1，否则无解

因为 n 和 m 最大为 100，剪枝之后 k 的值又不会大于 m，所以可以用三维数组做记忆化

（然而我比赛时用的哈希表，而且好像少判了 n == 0 时的条件……）

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

const int N = 105;

ll mp[N][N][N];

ll dfs(int n, int m, int k) {

if (k == 0) return (m == 0 && n == 0);

if (k > m || n >= m) return 0;

if (n == 0) return k == m;

if (mp[n][m][k] != -1) return mp[n][m][k];

ll ans = dfs(n, m - 1, k - 1) + dfs(n - 1, m, k + k);

ans %= MOD;

mp[n][m][k] = ans;

return ans;

}

int main() {

memset(mp, -1, sizeof mp);

int m, n;

cin >> n >> m;

cout << dfs(n, m, 2) << endl;

return 0;

}

也是可以动态规划的，不过不写了

试题J:砍竹子

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

【问题描述】

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

他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以把这一段竹子的高度都变为 [ sqrt( [H / 2] + 1 ) ] ，其中 [x] 表示对 x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。

【输入格式】

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

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

【输出格式】

一个整数表示答案。

【样例输入】

6

2 1 4 2 6 7

1

2

【样例输出】

5

1

【样例说明】

其中一种方案: 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步完成

【评测用例规模与约定】

对于20%的数据，保证 n ≤ 1000, hi ≤ 10^6。

对于100%的数据，保证 n ≤ 2 × 10^5, hi ≤ 10^18。

题解：贪心骗分

一看到成段修改就想到线段树了，但还是没有思路，而且 10^18 实在是太大了

看样例猜一个贪心，每次找最大值修改，如果连续相同的话就一起修改

然后暴力模拟，能骗两个样例就算成功

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 200005;

int n;

ll a[N], ans = 0;

int main() {

cin >> n;

for (int i = 0; i < n; i++) {

 cin >> a[i];

}

while (true) {

 int idx = 0;

 for (int i = 0; i < n; i++) {

  if (a[i] > a[idx]) idx= i;

 }

 if (a[idx] == 1) break;

 ll val = a[idx];

 for (int i = idx; a[i] == val; i++) {

  a[i] = sqrt(a[i] / 2 + 1);

 }

 ans ++;

}

cout << ans << endl;

return 0;

}

总结下来就是：寄了吗？又寄了吗？答案是寄！

这届比赛最大的变动就是填空题变成了两道，不过总体难度还是不算太高的（只说C++ B组）

感觉这次蓝桥杯是想往代码能力和思维能力上靠，但是连着这么多编程题挺消磨意志的，八道大题，到后面连题都不想读了

还有希望蓝桥杯出题再优化一下题目吧，让题意表达确切些，最好再精简一下

B题顺子日期给我的感觉就是玩了一个游戏，但让我自己来猜游戏规则是什么，而且只能玩一次