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

试题 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 

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 


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 


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 


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 
#include 
#include 
#include 

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 
#include 
#include 
#include 

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 
#include 
#include 
#include 

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 
#include 
#include 
#include 

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 

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 
#include 
#include 
#include 

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 

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 
#include 
#include 
#include 

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 

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 
#include 
#include 
#include 
#include 
#include 
#include 

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 

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