2022年蓝桥杯：第十三届蓝桥杯大赛软件赛省赛（全部正解做法代码 C/C++ B组）

文章目录

• • 试题 A: 九进制转十进制
  • • 问题描述
    • 问题答案
  • 试题 B: 顺子日期
  • • 问题描述
    • 问题答案
  • 试题 C: 刷题统计
  • • 问题描述
    • 问题答案(正解)
  • 试题 D: 修剪灌木
  • • 问题描述
    • 问题答案(正解)
  • 试题 E: X 进制减法
  • • 问题描述
    • 问题答案(正解)
  • 试题 F: 统计子矩阵
  • • 问题描述
    • 问题答案(暴力百分之70&正解)
  • 试题 G: 积木画
  • • 问题描述
    • 问题答案(状态压缩DP未滚动数组版本&滚动数组优化DP&优化矩阵快速幂（没写）)都可以过
  • 试题 H: 扫雷
  • • 问题描述
    • 问题答案(暴力骗分&正解)
  • 试题 I: 李白打酒加强版
  • • 问题描述
    • 问题答案(暴力百分之40 & 正解)
  • 试题 J: 砍竹子(暴力百分之20 & 堆优化 & 性质方法（最快）正解)
  • • 问题描述
    • 问题答案

试题 A: 九进制转十进制

问题描述

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

问题答案

答案为： 1478

试题 B: 顺子日期

问题描述

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

问题答案

答案为：4 或者是 14 （我填的是4以为不包含012这种情况）

试题 C: 刷题统计

问题描述

【问题描述】
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天
做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在
第几天实现做题数大于等于 n 题？
【输入格式】
输入一行包含三个整数 a, b 和 n.
【输出格式】
输出一个整数代表天数。
【样例输入】
10 20 99
【样例输出】
8
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ a, b, n ≤ 106.
对于 100% 的评测用例，1 ≤ a, b, n ≤ 1018

问题答案(正解)

数据范围为1e18,所以写法首先对一周进行取余，然后再进行判断7天就可以了。

#include <bits/stdc++.h>using namespace std;typedef long long LL;
const int N = 1e5+10;
LL a,b,n;
LL day;
void solve()
{cin>>a>>b>>n;LL sum = a*5+2*b;if(n%sum==0){day = n/sum*7;}else{day = n/sum*7; n%=sum;for(int i=1; i<=5; i++){if(n>0) n-=a,day++;}for(int i=1; i<=2; i++){if(n>0) n-=b,day++;}}cout<<day<<"\n";}int main()
{solve();return 0;
}

试题 D: 修剪灌木

问题描述

【问题描述】
爱丽丝要完成一项修剪灌木的工作。
有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌
木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，
每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开
始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的
早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
【输入格式】
一个正整数 N ，含义如题面所述。
【输出格式】
输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。
【样例输入】
3
【样例输出】
424
【评测用例规模与约定】
对于 30% 的数据，N ≤ 10.
对于 100% 的数据，1 < N ≤ 10000

问题答案(正解)

我采用的方法是打表找规律，模拟一下这个操作打表一下找规律。

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e5+10;
LL w[N];
int n;void solve()
{scanf("%d",&n);if(n==1) printf("1\n");else if(n==2){printf("2\n2\n");}else{int m;if(n%2==1){m = n-1,m+=n/2*2;for(int i=1; i<=n/2; i++){printf("%d\n",m);m-=2;}for(int i=1; i<=n/2+1; i++){printf("%d\n",m);m+=2;}}else{m = n,m+=(n/2-1)*2;for(int i=1; i<=n/2; i++){printf("%d\n",m);m-=2;}for(int i=1; i<=n/2; i++){m+=2;printf("%d\n",m);}}}}int main()
{solve();return 0;
}

试题 E: X 进制减法

问题描述

【问题描述】
进制规定了数字在数位上逢几进一。
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 的结果。

问题答案(正解)

本质就是贪心，从低位到高位枚举max（{a+1,b+1，2}）的进制，并把进制乘进去。
举一个例子，就是你求2的1次方到2的10次方的和一样，不过这个乘的进制不是固定的变化而已。题意比较坑，看懂了还是好理解的。

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e5+10,mod = 1000000007;
LL ar[N],br[N];
LL n,a,b;void solve()
{scanf("%lld",&n);scanf("%lld",&a);for(int i=1; i<=a; i++) scanf("%lld",&ar[i]);reverse(ar+1,ar+1+a);scanf("%lld",&b);for(int i=1; i<=b; i++) scanf("%lld",&br[i]);reverse(br+1,br+1+b);int i = 1,j = 1;LL res = 1,sum = 0;while(i<=a||j<=b){LL x=0,y=0,cnt=2;if(i<=a) x = ar[i],i++;if(j<=b) y = br[j],j++;cnt = max(max(x,y)+1,cnt);sum = (sum+(x-y)*res)%mod;res = res*cnt%mod;}sum = (sum%mod+mod)%mod;printf("%lld\n",sum);}int main()
{solve();return 0;
}

试题 F: 统计子矩阵

问题描述

【问题描述】
给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大
N × M) 满足子矩阵中所有数的和不超过给定的整数 K?
【输入格式】
第一行包含三个整数 N, M 和 K.
之后 N 行每行包含 M 个整数，代表矩阵 A.
【输出格式】
一个整数代表答案。
【样例输入】
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
【样例输出】
19

问题答案(暴力百分之70&正解)

是一个二维前缀和，不过需要优化，我没有想到直接4维暴力，骗百分之70的分。

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e3+10,mod = 1000000007;
LL ar[N][N];
LL s[N][N];
LL n,m,k,ans;void check(int x,int y)
{for(int i=x; i<=n; i++){for(int j=y; j<=m; j++){LL sum = ar[i][j] - ar[i-x][j] - ar[i][j-y]+ar[i-x][j-y];if(sum<=k) ans++;}}
}void solve()
{scanf("%lld%lld%lld",&n,&m,&k);for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){scanf("%lld",&ar[i][j]);ar[i][j] = ar[i][j]+ar[i-1][j]+ar[i][j-1]-ar[i-1][j-1];}}for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){check(i,j);}}printf("%lld",ans);}int main()
{solve();return 0;
}

本题的方法为一维前缀和 + 双指针（可能会卡常 所以尽量使用int啦 快读等等）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;
const int N = 510;
int n,m,K;
int s[N][N];
/*
本题做法是把竖着的每个区间进行双指针算法
小细节优化常数，本题只有结果会超过int的所以其他的数都有int进行存储。
比如说竖着的矩阵为  1 2 3 4 5 6 而k的值为6
那么我们双指针的过程就是
1 <= k   r初始值为 1 ，l 也为1 满足的子矩阵为1
1 + 2 <=k r变为2，l还为1 那么符合的矩阵有 1 2， 和2  r-l+1 = 2
1 +2 + 3 <=k 增加满足的矩阵就是3  1 2 3,2 3,3 三种
1 + 2 + 3 + 4 >k的时候动第一个指针，l 值变为4才小于等于 k 所以 r-l+1 = 1
如果当前的某个值大于k了那么 l 会一直加到 变成r+1  那么 r- l+1 = 0不会有答案*/
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;}printf("%lld\n",res);return 0;
}

试题 G: 积木画

问题描述

【问题描述】
小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2
个单位面积）和 L 型（大小为 3 个单位面积）：
同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构
成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？
积木可以任意旋转，且画布的方向固定。
【输入格式】
输入一个整数 N，表示画布大小。
【输出格式】
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取
模后的值
【样例输入】
3
【样例输出】
5

问题答案(状态压缩DP未滚动数组版本&滚动数组优化DP&优化矩阵快速幂（没写）)都可以过

未加滚动数组版本。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long LL;const int N = 1e7+10,mod = 1e9+7;  int g[4][4]={{1,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,0},};  /// f[i][j]表示已经操作完前 i-1项 且第 i 到的状态为 j 的方案的集合
int f[N][4];
int n;
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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long LL;const int N = 1e7+10,mod = 1e9+7;  int g[4][4]={{1,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,0},};  /// f[i][j]表示已经操作完前 i-1项 且第 i 到的状态为 j 的方案的集合
int f[2][4];
int n;
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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long LL;const int N = 1e7+10,mod = 1e9+7;  int g[4][4]={{1,1,1,1},{0,0,1,1},{0,1,0,1},{1,0,0,0},};  /// f[i][j]表示已经操作完前 i-1项 且第 i 到的状态为 j 的方案的集合
int f[2][4];
int n;
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])//只有当g[j][k]为1的时候才会加 优化常数版本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;
}

试题 H: 扫雷

问题描述

【问题描述】
小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下，
在一个二维平面上放置着 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
【样例输出】
2

问题答案(暴力骗分&正解)

想用队列入射发射的炮弹，然后如果可以炸到某个雷然后将雷在进行入队，进行暴力，可能我实现的有问题，在代码源上只对了一个样例。

#include <bits/stdc++.h>using namespace std;typedef long long LL;
const int N = 1e5+10,mod = 1000000007;
vector<vector<int> > p;
int n,m;
struct node
{int a,b,c;
}ar[N];
void solve()
{scanf("%d%d",&n,&m);int ans = 0;for(int i=1; i<=n; i++){int a,b,c; scanf("%d%d%d",&a,&b,&c);ar[i] = {a,b,c};}queue<node> q;for(int i=1; i<=m; i++){int a,b,c; scanf("%d%d%d",&a,&b,&c);node z = {a,b,c};q.push(z);}while(!q.empty()){node x = q.front(); q.pop();for(int i=1; i<=n; i++){if(ar[i].c>10) continue;double x1 = x.a,y1 = x.b;double x2 = ar[i].a,y2 = ar[i].b;double r1 = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);int r2 = sqrt(r1);if(r2<=x.c) q.push(ar[i]),ar[i].c = 11,ans++;}}printf("%d\n",ans);}int main()
{solve();return 0;
}

因为雷和雷之间的爆炸是一条有向边，导弹到雷也相当于是一条有向边，所以可以采用图的遍历的算法。难点，如何建图。需要手写哈希表。建立边的索引关系。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;
const int N = 5e4+10,M = 999997; 
int n,m;
struct node
{int x,y,r;
}cir[N];
LL h[M];   // 哈希表的大小  哈希表手写的话数组开的越大越好（规定内存下）
int id[M];
bool st[M];LL get(int x,int y)
{return x*1000000001ll+y;  // 后面加的ll就是转化成longlong
}int find(int x,int y)   /// 数据结构模拟哈希的那个散列表
{LL key = get(x,y);int t = (key%M+M)%M;     // 负数取模是负数 这样转化可以避免负数的情况while(h[t] != -1&& h[t]!=key)if(++t==M) t = 0;return t;
}
int sqr(int x)
{return x*x;
}void dfs(int x,int y,int r)   /// dfs图的遍历
{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()
{ios::sync_with_stdio(false); cin.tie(0);memset(h, -1, sizeof h); // 表示每个哈希表的位置都未被用过cin>>n>>m;for(int i=1; i<=n; i++){int x,y,r;  cin>>x>>y>>r;cir[i] = {x,y,r};int t = find(x,y);if(h[t]==-1) h[t] = get(x,y);  //存储哈希值if(!id[t]||cir[id[t]].r<r) id[t] = i;  //如果多个点在同一点存最大的半径}while(m--){int x,y,r; cin>>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)) // 判断是否在圆内{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++) // 枚举所有雷{int x = cir[i].x, y= cir[i].y;if(st[find(x,y)]) res++;}cout<<res<<"\n";return 0;
}

试题 I: 李白打酒加强版

问题描述

【问题描述】
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花，
他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇
花是不合法的。
【输入格式】
第一行包含两个整数 N 和 M.
【输出格式】
输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。
【样例输入】
5 10
【样例输出】
14

问题答案(暴力百分之40 & 正解)

当时做题没时间了，暴力骗分百分之四十。

#include <bits/stdc++.h>using namespace std;typedef long long LL;
const int N = 1e5+10,mod = 1000000007;
int n,m;
LL ans=0;void solve()
{cin>>n>>m;m--;for(int i=0; i<1<<n+m; i++){int flag = 0;int dian = n,hua = m;LL res = 2;for(int j=0; j<n+m; j++){if(i>>j&1){if(dian<=0) {flag = 1;break;}else dian--,res*=2;}else{if(hua<=0) {flag=1; break;}else hua--,res--;if(res<0) {flag =1; break;}}}if(!flag&&res==1) ans++;}cout<<ans<<"\n";
}int main()
{solve();return 0;
}

赛后写的正解，简单的线性转移dp，状态方程还是很好写的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 110,mod = 1e9+7;
LL f[N][N][N];
int main()
{int n,m; cin>>n>>m;f[0][0][2] = 1; m--;for(int i=0; i<=n; i++)for(int j=0; j<=m; j++)for(int k=0; k<=m; k++){if(i>=1){if(k%2==0){f[i][j][k] += f[i-1][j][k/2];f[i][j][k] %= mod;}}if(j>=1){f[i][j][k] += f[i][j-1][k+1];f[i][j][k] %= mod;}}cout<<f[n][m][1]<<"\n";return 0;
}

试题 J: 砍竹子(暴力百分之20 & 堆优化 & 性质方法（最快）正解)

问题描述

【问题描述】
这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的
高度为 hi.
他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一
段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以
把这一段竹子的高度都变为 ⌊ √⌊ H2 ⌋ + 1⌋，其中 ⌊x⌋ 表示对 x 向下取整。小明想
知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。
【输入格式】
第一行为一个正整数 n，表示竹子的棵数。
第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。
【输出格式】
一个整数表示答案。
【样例输入】
6
2 1 4 2 6 7
【样例输出】
5

问题答案

这道题的思路还是比较好想的，就是先从高到底进行砍竹子，数据范围是2*1e5，如何优化到logn级别，由于我前面做题较慢，我后面都是直接暴力骗分，本题我直接用优先队列维护区间最大进行暴力，可以骗百分之20的分。

#include <bits/stdc++.h>using namespace std;typedef long long LL;
const int N =2e5+10,mod = 1000000007;
int n;
LL ar[N],br[N],ans;
priority_queue<LL> q;
void solve()
{scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%lld",&ar[i]);if(ar[i]>1) q.push(ar[i]);}while(!q.empty()){LL x = q.top(); q.pop();LL z = sqrt(x/2+1);if(z>1) q.push(z);for(int i=1; i<=n; i++){if(ar[i]==x&&ar[i]==ar[i-1]) continue;if(ar[i]==x) ans++;}for(int i=1; i<=n; i++) if(ar[i]==x) ar[i]=z;}printf("%lld\n",ans);}int main()
{solve();return 0;
}

解法我们用优先队列维护期区间时间复杂度为 21e510*logn。
为什么是10 左右的，极限为1e18的时候其实我们假设都是开平方
1e18，1e9,1e5,1e3,1e2,1e1,5,2,1。这里直接随便算的，理解了都可以了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <cmath>using namespace std;const int N = 2e5+10;
typedef long long LL;struct node 
{LL l,r,w;    
};
bool operator< (node a,node b) 
{  if(a.w==b.w) return a.l>b.l; return a.w<b.w;
}
priority_queue<node> q;
int n;
LL w[N],ans;
int main()
{ios::sync_with_stdio(false); cin.tie(0);cin>>n;for(int i=1; i<=n; i++) cin>>w[i];for(int i=1,j = 1; i<=n; i++){while(w[j]==w[i]) j++;if(w[i]<=1) {i = j-1; continue;}node s = {i,j-1,w[i]};q.push(s);i = j-1;}LL l1 = 0,r1 = 0,cnt = -1,z = 0;while(!q.empty()){node t = q.top(); q.pop();if(cnt!=t.w){ans++;l1 = t.l,r1 = t.r,cnt = t.w;z = sqrt(cnt/2+1);if(z>1) {node xx  = {l1,r1,z};q.push(xx);}}else{if(t.l<=r1+1) {r1 = t.r;if(z>1) {node xx  = {t.l,r1,z};q.push(xx);}}else{ans++;l1 = t.l,r1 = t.r,cnt = t.w;if(z>1) {node xx  = {l1,r1,z};q.push(xx);}}}}cout<<ans<<"\n";return 0;
}

找性质

#include <bits/stdc++.h>using namespace std;typedef long long LL;
const int N = 2e5+10;
LL f[N][10];
LL w[N];
LL ar[10];
int n;
int main()
{   scanf("%d",&n);int mx = 0,cnt = 0;for(int i=1; i<=n; i++)  scanf("%lld",&w[i]);for(int i=1; i<=n; i++){cnt = 0;while(w[i]>1){ar[++cnt] = w[i];w[i] = w[i]/2+1;w[i] = sqrt(w[i]);}mx = max(mx,cnt);for(int j=1,k=cnt; j<=cnt; j++,k--) f[i][j]=ar[k];}LL res = 0;for(int i=1; i<=mx; i++){for(int j=1; j<=n; j++){if(f[j][i]!=f[j-1][i]&&f[j][i]>0) res++;}}printf("%lld\n",res);return 0;
}