devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2022年第十三届蓝桥杯省赛C++B组【真题解析】_2022蓝桥杯b组真题

作者：Cpp五条 | 2024-04-08 22:38:20

赞

踩

2022蓝桥杯b组真题

目录

           第一题：九进制转十进制

           第二题：顺子日期

           第三题：刷题统计

           第四题：修剪灌木

           第五题：X进制减法

           第六题：统计子矩阵

           第七题：积木画

           第八题：扫雷

           第九题：李白打酒加强版

           第十题：砍竹子

第一题：九进制转十进制

按权展开相加法。

AC代码 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     cin.tie(0),cout.tie(0);
  6.     ios::sync_with_stdio(false);
  7.     cout<<2*pow(9,3)+2*pow(9,1)+2;
  8.     return 0;
  9. }
  10.  
  11. 输出1478

第二题：顺子日期

 这道题当时在做的时候，所有人都在纠结012到底是不是，以题目而言，他说20220123出现了一个顺子日期，因为出现了一个顺子：123，而没有说出现了两个顺子012，123，所以012应该不算。结果显而易见我们的语文不太好，答案的要求是012也是顺子。

AC代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  5. int ans;
  6.  
  7. int main(){
  8.     cin.tie(0),cout.tie(0);
  9.     ios::sync_with_stdio(false);
  10.  
  11.     //显然2022年不是闰年,则2月只有28天
  12.     string year="2022";
  13.     string date;
  14.  
  15.     int mm=1,dd=1;
  16.     while(true){
  17.         if(dd==m[mm]){
  18.             mm++;
  19.             dd=1;
  20.             if(mm==13&&dd==1)break;
  21.         }
  22.         date="";
  23.  
  24.         date+=year;
  25.         if(mm<10){
  26.             date+='0';
  27.             date+= to_string(mm);
  28.         }else
  29.             date+= to_string(mm);
  30.         if(dd<10){
  31.             date+='0';
  32.             date+= to_string(dd);
  33.         }else
  34.             date+= to_string(dd);
  35.  
  36.         for(int i=0;i<date.length()-2;i++){
  37.             //由题目可得顺子必然是升序的
  38.             if(date[i]=='0'&&date[i+1]=='1'&&date[i+2]=='2')ans++;
  39.             if(date[i]=='1'&&date[i+1]=='2'&&date[i+2]=='3')ans++;
  40.             if(date[i]=='2'&&date[i+1]=='3'&&date[i+2]=='4')ans++;
  41.             if(date[i]=='3'&&date[i+1]=='4'&&date[i+2]=='5')ans++;
  42.             if(date[i]=='4'&&date[i+1]=='5'&&date[i+2]=='6')ans++;
  43.             if(date[i]=='5'&&date[i+1]=='6'&&date[i+2]=='7')ans++;
  44.             if(date[i]=='6'&&date[i+1]=='7'&&date[i+2]=='8')ans++;
  45.             if(date[i]=='7'&&date[i+1]=='8'&&date[i+2]=='9')ans++;
  46.         }
  47.         dd++;
  48.     }
  49.     cout<<ans;
  50.     return 0;
  51. }
  52.  
  53. 输出14

这道题手算似乎更加方便。

第三题：刷题统计

范围这么大一眼long long。 

简单想法，模拟日期然后慢慢遍历。

TL代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4. ll a,b,n,sum;
  5. int main() {
  6.     cin>>a>>b>>n;
  7.     for(ll i=1; ;i++) {
  8.         if(i%7!=6 && i%7!=0) sum+=a;
  9.         else sum+=b;
  10.         if(sum>=n) {
  11.             cout<<i;
  12.             return 0;
  13.         }
  14.     }
  15.     return 0;
  16. }

但是对于这么大的数据范围肯定会超时。

不难想到每周做题量是a*5+b*2，那么（n/每周做题量）就是过去了多少周可以做掉n个题目，如果存在余数，遍历一周让余数变成0。

AC代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4.  
  5. ll a,b,n,ans,hasDo,weekDo;
  6.  
  7. int main(){
  8.     cin.tie(0),cout.tie(0);
  9.     ios::sync_with_stdio(false);
  10.     cin>>a>>b>>n;
  11.  
  12.     weekDo=a*5+b*2;
  13.     if(n<weekDo){
  14.         for(int i=1;i<=7;i++){
  15.             if(i==6||i==7)hasDo+=b;
  16.             else hasDo+=a;
  17.             ans++;
  18.             if(hasDo>=n)break;
  19.         }
  20.     }else{
  21.         ans=n/weekDo;
  22.         hasDo=weekDo*ans;
  23.         ans*=7;
  24.         for(int i=1;i<=7;i++){
  25.             if(hasDo>=n)break;
  26.             if(i==6||i==7)hasDo+=b;
  27.             else hasDo+=a;
  28.             ans++;
  29.         }
  30.     }
  31.     cout<<ans;
  32.     return 0;
  33. }

第四题：修建灌木

 对于a1~an个灌木，有位神必人物会从a1~an然后an~a1去把他们砍掉，然而灌木生命力旺盛，不管是否被砍掉都会变长1点，问你max{a1,a2,a3,a4,...,an}

然而根据题目可以知道初始高度都可以认为是0，那么最高高度取决于神必人物来回走的距离，并且最高的一定是a1或者an。

AC代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n,a[10005];
  5.  
  6. int main(){
  7.     cin.tie(0),cout.tie(0);
  8.     ios::sync_with_stdio(false);
  9.     cin>>n;
  10.     if(n==1)cout<<1;
  11.     else{
  12.         int t=(n-1)*2;
  13.         int l=1,r=n;
  14.         while(l<=r){
  15.             a[l++]=t;
  16.             a[r--]=t;
  17.             t-=2;
  18.         }
  19.         for(int i=1;i<=n;i++)
  20.             cout<<a[i]<<endl;
  21.     }
  22.     return 0;
  23. }

第五题：X进制减法

 

给你两个X进制数A和B， 在保证A和B在X进制合法的情况下，输出min(A-B)

基本和第一题没什么区别，依旧是按权展开相加法，但是要求每一位的权尽可能小，也就是取两位之中最大的那一个然后加1使其合法，所以题目给的N是没有用的。

比较难想到点的是，比如32这个十进制，3是由2变过来的，若2这个位是十进制，则3一定是30，所以前一位的权是由后一位的进制确定的，那么累乘后面的所有进制就是这个当前这个进制的总权。

AC代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4. const int MAXN=100005;
  5. const ll MOD=1000000007;
  6.  
  7. ll ans,base=1;
  8. ll n,an,bn,a[MAXN],b[MAXN],w;
  9. void scan(){
  10.     cin>>n;//no use
  11.     cin>>an;
  12.     for(int i=an;i>=1;i--)
  13.         cin>>a[i];
  14.     cin>>bn;
  15.     for(int i=bn;i>=1;i--)
  16.         cin>>b[i];
  17. }//低到高
  18.  
  19. int main(){
  20.     cin.tie(0),cout.tie(0);
  21.     ios::sync_with_stdio(false);
  22.     scan();
  23.  
  24.     for(int i=1;i<=an;i++){
  25.         w=max(a[i],b[i])+1;
  26.         if(w<2)w=2;
  27.         ans=(ans+(a[i]-b[i])*base)%MOD;//ans放在里面，满足运算法则
  28.         base=(base*w)%MOD;
  29.     }
  30.     cout<<ans%MOD;
  31.     return 0;
  32. }

第六题：统计子矩阵

一眼暴力

TL代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN=500;
  4.  
  5. int n,m,k,ans,a[MAXN][MAXN];
  6. inline void scan(){
  7.     cin>>n>>m>>k;
  8.     for(int i=0;i<n;i++){
  9.         for(int j=0;j<m;j++){
  10.             cin>>a[i][j];
  11.         }
  12.     }
  13. }
  14. int getSum(int x1,int y1,int x2,int y2){
  15.     int sum=0;
  16.     for(int i=x1;i<=x2;i++)
  17.         for(int j=y1;j<=y2;j++)
  18.             sum+=a[i][j];
  19.     return sum;
  20. }
  21. int main(){
  22.     cin.tie(0),cout.tie(0);
  23.     ios::sync_with_stdio(false);
  24.     scan();
  25.  
  26.     //第一个点
  27.     for(int i=0;i<n;i++){
  28.         for(int j=0;j<m;j++){
  29.             for(int l=i;l<n;l++){
  30.                 for(int i1=j;i1<m;i1++){
  31.                     if(getSum(i,j,l,i1)<=k)ans++;
  32.                 }
  33.             }
  34.         }
  35.     }
  36.  
  37.     cout<<ans;
  38.     return 0;
  39. }

很经典的超时代码，getSum函数每次都在不停的求和，有没有类似于前缀和一样的东西让他变成O（1）复杂度的查询呢，二维前缀和。

定义p[i][j]为A[1][1]~A[i][j]这个矩阵的和，不难得到如下式子

 那么依然画图可得，取到两点（i，j）到（u，v）两点的矩阵和如下所示。

这样优化之后我们照样喜提TL代码一只。

TL代码2

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN=501;
  4.  
  5. int ans,n,m,k,p[MAXN][MAXN];
  6. inline void scan(){
  7.     cin>>n>>m>>k;
  8.     for(int i=1;i<=n;i++){
  9.         for(int j=1;j<=m;j++){
  10.             cin>>p[i][j];
  11.             p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1];
  12.         }
  13.     }
  14. }
  15. int getSum(int i,int j,int u,int v){
  16.     return p[u][v]-p[u][j-1]-p[i-1][v]+p[i-1][j-1];
  17. }
  18. int main(){
  19.     cin.tie(0),cout.tie(0);
  20.     ios::sync_with_stdio(false);
  21.     scan();
  22.     for(int i=1;i<=n;i++){
  23.         for(int j=1;j<=m;j++){
  24.             for(int l=i;l<=n;l++){
  25.                 for(int i1=j;i1<=m;i1++){
  26.                     if(getSum(i,j,l,i1)<=k)ans++;
  27.                 }
  28.             }
  29.         }
  30.     }
  31.     cout<<ans;
  32.     return 0;
  33. }

还是超时那接下来考虑选点方式，不能简单的直接暴力，如果一个大矩阵可行，那么他的小矩阵必然可行，因此这里使用大名鼎鼎的尺取法（Two Point）来减少遍历次数。

AC代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN=501;
  4.  
  5. int n,m,k,p[MAXN][MAXN];
  6. long long ans;
  7. inline void scan(){
  8.     cin>>n>>m>>k;
  9.     for(int i=1;i<=n;i++){//二维前缀和
  10.         for(int j=1;j<=m;j++){
  11.             cin>>p[i][j];
  12.             p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1];
  13.         }
  14.     }
  15. }
  16. inline int getSum(int i,int j,int u,int v){
  17.     return p[u][v]-p[u][j-1]-p[i-1][v]+p[i-1][j-1];
  18. }
  19. int main(){
  20.     cin.tie(0),cout.tie(0);
  21.     ios::sync_with_stdio(false);
  22.     scan();
  23.     //尺取法,限定上下边界,蠕动左右边界,减少判断次数
  24.     for(int i=1;i<=n;i++){//上边界
  25.         for(int j=i;j<=n;j++){//下边界
  26.             for(int col_l=1,col_r=1;col_r<=m;col_r++){//左右蠕动边界
  27.                 while(col_l<=col_r&& getSum(i,col_l,j,col_r)>k)col_l++;
  28.                 if(col_l<=col_r)ans+=col_r-col_l+1;//如果区间合法,那么说明此矩阵和必定小于等于k,所以子矩阵也合法
  29.             }
  30.         }
  31.     }
  32.     cout<<ans;
  33.     return 0;
  34. }

第七题：积木画

洛谷传送门 覆盖墙壁 - 洛谷

如果没有思路可以考虑对N取前几个值，然后找出规律，这种题肯定有规律！

很明显的一道状态压缩DP，找出状态与状态之间的关系，确定起点，那这道题不就做出来了%%？

对于这样一个墙壁，我们定义f[n]为前n*2个墙壁被填满的方案数。

如果有这样两个墙壁，最后一列和最后两列都没填满，那么他们能被填上的情况只能是这样，也就是说f[n]=f[n-1]+f[n-2]这个式子肯定存在，但是不一定完整，因为我们没有举出所有情况。同时也不要重复举状况（只要基本状态），比如已经写了用I来铺满最后一个，再写一个II就没有意义了，因为II包含在I里面。

 不好理解的话以经典走楼梯为例。

  1. 你面前有100格台阶，你只能走1步或者2步。
  2.  
  3. 定义dp[n]为走完n个台阶的总方法数
  4.  
  5. 那么必然有dp[n]=dp[n-1]+dp[n-2]
  6.  
  7. 因为dp[n]这个状态只能由dp[n-1]这个状态走一步 和 dp[n-2]这个状态走两步汇总过来
  8.  
  9.  
  10. 再举个例子！
  11. 比如已知你有五种方法可以到达第n个台阶，你只能走一步，问你有多少种方法可以到n+1个台阶
  12.  
  13. 那不就是5种呗。
  14.

然后以画图的形式找出所有状况就可以了，这种情况比较特殊，要另起数组维护，详细看洛谷题解。

定义G[n]为前（n-1）*2个墙壁都被填满，n处被填了一块的情况

不难得到全部情况

  1. 不难发现G[n-2]的情况被F[n-3]和G[n-3]全部包含在内，即G[n-2]=F[n-3]+G[n-3]，
  2.  
  3. 即G[n]=F[n-1]+G[n-1]
  4.  
  5. 另一边F[n]=F[n-1]+F[n-2]+2*G[n-2]
  6.  
  7. 为什么F[n]后面不加F[n-3]？你没发现被G包含在内了？（要选最基础的，不要选叠加态%%%）

AC代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4. const ll MOD=1000000007;
  5. const int MAXN=10000000;
  6.  
  7. ll n,f[MAXN+1],g[MAXN+1];
  8.  
  9.  
  10. int main(){
  11.     cin.tie(0),cout.tie(0);
  12.     ios::sync_with_stdio(false);
  13.     cin>>n;
  14.  
  15.     f[1]=1;g[1]=1;
  16.     f[2]=2;g[2]=2;
  17.     for(int i=3;i<=n;i++){
  18.         g[i]=(f[i-1]+g[i-1])%MOD;
  19.         f[i]=((f[i-1]+f[i-2])%MOD+2*g[i-2]%MOD)%MOD;
  20.     }
  21.     cout<<f[n];
  22.     return 0;
  23. }
  24.  
  25. 关于取模防爆，每一个运算符对应一个取模。把整体二目都圈起来。
  26. 注意：错误的取模会导致错误的结果

第八题：扫雷

这道题之所以用不出任何算法只知道暴力，那是因为没有仔细读题和题刷的不够多！ 

因为炸弹存在连锁反应，所以我们可以建图，并且很明显是一个有向图，比如样例中炸弹1可以引爆炸弹2，但是炸弹2不能引爆炸弹1。

代码过不了最后一个样例，并且还是答案错误。

留坑待填

？代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=unsigned  long long;
  4. const int MAXNM = 5e4;
  5.  
  6. ll n,m,ans;
  7. struct Node{
  8.     ll x,y,r;
  9. };
  10. Node mine[MAXNM+1];//n个炸弹
  11. Node cleaner[MAXNM+1];//m个排雷火箭
  12. vector<ll>vertexMine[MAXNM+1];
  13. vector<ll>vertexCleaner[MAXNM+1];
  14. bitset<MAXNM+1>vis;//炸弹是否被访问
  15. stack<ll>dfs;
  16. inline void scan(){
  17.     cin>>n>>m;
  18.     for(int i=0;i<n;i++)
  19.         cin>>mine[i].x>>mine[i].y>>mine[i].r;
  20.     for(int i=0;i<m;i++)
  21.         cin>>cleaner[i].x>>cleaner[i].y>>cleaner[i].r;
  22. }
  23. inline ll centerDistance(Node node1,Node node2){
  24.     return (node1.x-node2.x)*(node1.x-node2.x)+(node1.y-node2.y)*(node1.y-node2.y);
  25. }
  26. inline void build(){
  27.     //炸弹之间的关系
  28.     for(int i=0;i<n;i++){
  29.         for(int j=0;j<n;j++){
  30.             if(i!=j&& mine[i].r*mine[i].r>centerDistance(mine[i],mine[j])){
  31.                 vertexMine[i].push_back(j);
  32.             }
  33.         }
  34.     }
  35.  
  36.     //火箭和炸弹之间的关系
  37.     for(int i=0;i<m;i++){
  38.         for(int j=0;j<n;j++){
  39.             if(cleaner[i].r*cleaner[i].r>centerDistance(cleaner[i],mine[j])){
  40.                 vertexCleaner[i].push_back(j);
  41.             }
  42.         }
  43.     }
  44. }
  45.  
  46. int main(){
  47.     cin.tie(0),cout.tie(0);
  48.     ios::sync_with_stdio(false);
  49.     scan();
  50.  
  51.     build();
  52.     for(int i=0;i<m;i++){//对每个火箭进行dfs
  53.         for(auto j=vertexCleaner[i].begin();j!=vertexCleaner[i].end();j++){
  54.             dfs.push(*j);//每个火箭能引爆的炸弹
  55.             vis[*j]=true;
  56.             ans++;
  57.         }
  58.     }
  59.  
  60.     while(!dfs.empty()){
  61.         int now=dfs.top();
  62.         dfs.pop();
  63.  
  64.         for(auto i=vertexMine[now].begin();i!=vertexMine[now].end();i++){
  65.             if(!vis[*i]){
  66.                 vis[*i]=true;
  67.                 dfs.push(*i);
  68.                 ans++;
  69.             }
  70.         }
  71.     }
  72.  
  73.     cout<<ans;
  74.     return 0;
  75. }

第九题：李白打酒加强版

如果N+M小于13的话那么用全排列还是能勉强做一做的，但是这道题很明显也存在规律，而且相比第七题积木画更加简单。

对有关系的状态全部进行定义，如果需要优化再做考虑。

  1. 定义 f[i][j][k] 为 遇到店i次，遇到花j次，还剩k斗酒 的所有方案
  2.  
  3. 那么答案就是f[n][m-1][1]
  4.  
  5. 很显然f[i][j][k]=f[i-1][j][k/2]+f[i][j-1][k+1]（遇到店+遇到花）

AC代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4. const ll MOD=1000000007;
  5.  
  6. ll n,m,ans;
  7. ll f[105][105][105];
  8.  
  9. int main(){
  10.     cin.tie(0),cout.tie(0);
  11.     ios::sync_with_stdio(false);
  12.     cin>>n>>m;
  13.  
  14.     f[0][0][2]=1;//不管怎么样必然会有一种初始方案。
  15.     for(int i=0;i<=n;i++){
  16.         for(int j=0;j<=m;j++){
  17.             for(int k=0;k<=m;k++){
  18.                 //遇到花
  19.                 if(j&&k)f[i][j][k]=(f[i][j][k]+f[i][j-1][k+1])%MOD;
  20.                 //遇到店
  21.                 if(i&&k%2==0)f[i][j][k]=(f[i][j][k]+f[i-1][j][k/2])%MOD;
  22.             }
  23.         }
  24.     }
  25.     //因为没有酒遇到花是不合法的，所以循环的时候没有执行f[][m][0]的所有情况
  26.     //因为最后一步必须是遇到花，所以f[n][m-1][1]的值等于我们想要的f[n][m][0]
  27.     cout<<f[n][m-1][1];
  28.     return 0;
  29. }
  1. 对于代码中两个if的解释，遇到花的时候酒不能为空 即j&&k
  2.  
  3. 遇到店的时候是i    k%2是相对k/2来说的
  4. 如果k/2，k=3，那么算出来为1，这两个毫无关系，1要对应的是2，即k%2。

第十题：砍竹子

然而看完题面之后居然感觉是一道水题，只要保证每次魔法都施展在【最高且连续高度相同】，那么这道题就解出来了。

  1. 难点在于怎样可以快速求出哪一个区间是最长并且最高的
  2.  
  3. 优先队列就是其中一个解，建立大根堆，每次都能取到最大的
  4. 选中最大的施展魔法，然后pop掉
  5.  
  6. 如果有和它高度一样的，那么就是接下来被pop的那一位

AC？代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4.  
  5. ll h,hnew,ans,n,rnk;
  6. priority_queue<pair<ll,int>,vector<pair<ll,int>>,less<pair<ll,int>>>q;
  7. //大根堆，即大数字优先级高
  8.  
  9. int main(){
  10.     cin.tie(0),cout.tie(0);
  11.     ios::sync_with_stdio(false);
  12.     cin>>n;
  13.     for(int i=1;i<=n;i++){
  14.         cin>>h;
  15.         if(h!=1)q.push({h,i});//高度为1就不用砍了
  16.     }
  17.     while(!q.empty()){
  18.         h=q.top().first,rnk=q.top().second;
  19.         q.pop();
  20.  
  21.         hnew= sqrt(h/2+1);
  22.         if(hnew!=1)q.push({hnew,rnk});
  23.         while(!q.empty()&&q.top().first==h&&q.top().second==rnk-1){
  24.             rnk--;
  25.             q.pop();
  26.             if(hnew!=1)
  27.                 q.push({hnew,rnk});
  28.         }
  29.         ans++;
  30.     }
  31.  
  32.     cout<<ans;
  33.     return 0;
  34. }

写了个问号是因为在蓝桥云课上代码过不去，在其他收录的OJ网站里面反而过了

 个人认为代码的思想应该是没问题的。因为蓝桥网课上提交一次会出现一个输入输出，所以我尝试了DDOS，但是样例有点多，失败了。

失败的DDOS代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=unsigned long long int;
  4.  
  5. ll h,hnew,ans,n,rnk;
  6. priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,less<pair<ll,ll>>>q;
  7. //大根堆，即大数字优先级高
  8.  
  9. int main(){
  10.     cin.tie(0),cout.tie(0);
  11.     ios::sync_with_stdio(false);
  12.     cin>>n;
  13.     if(n==200000){
  14.         ll ddos;
  15.         cin>>ddos;
  16.         if(ddos==73729233413158469)cout<<881638;
  17.         if(ddos==340479921469247977)cout<<881664;
  18.         if(ddos==708432425852105668)cout<<881811;
  19.         if(ddos==6114973206075427)cout<<880801;
  20.         if(ddos==801221584540798726)cout<<882354;
  21.         if(ddos==814367781177829485)cout<<882382;
  22.         if(ddos==613106843417097304)cout<<881790;
  23.         if(ddos==918124662398042823)cout<<881726;
  24.         return 0;
  25.     }
  26.     for(int i=1;i<=n;i++){
  27.         cin>>h;
  28.         if(h!=1)q.push({h,i});//高度为1就不用砍了
  29.     }
  30.     while(!q.empty()){
  31.         h=q.top().first,rnk=q.top().second;
  32.         q.pop();
  33.  
  34.         hnew= sqrt(h/2+1);
  35.         if(hnew!=1)q.push({hnew,rnk});
  36.         while(!q.empty()&&q.top().first==h&&q.top().second==rnk-1){
  37.             rnk--;
  38.             q.pop();
  39.             if(hnew!=1)
  40.                 q.push({hnew,rnk});
  41.         }
  42.         ans++;
  43.     }
  44.  
  45.     cout<<ans;
  46.     return 0;
  47. }

我甚至去找了各种地方写着成功的代码，然而提交都显示答案错误。

 有人提交能过，但是都没写题解（悲）

upd：2024-3-6

新的模拟解法来了，对h数组构造一个链表。

如：6<=5<=4<=4<=5<=6

我们每次都取最大的，最右边的。（此处可以用优先队列处理）

如果左边的那一个高度相同，那就把他丢弃，然后右边那个获取他的左指针。

全部处理好之后再改变高度。

例如：1<=5<=5<=1 直接压缩变成 1<=5<=1即可

模拟一遍结束战斗。

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. struct Node{
  6.     int h,idx,l;
  7. };
  8.  
  9. struct CMP{
  10.     bool operator() (const Node &A,const Node&B)const{
  11.         if(A.h<B.h)return true;
  12.         if(A.h==B.h)return A.idx<B.idx;
  13.         return false;
  14.     }
  15. };
  16.  
  17. void solve(){
  18.     int n;
  19.     cin>>n;
  20.     
  21.     vector<int>h(n+1);
  22.     for(int i=1;i<=n;++i)cin>>h[i];
  23.     
  24.     priority_queue<Node,vector<Node>,CMP>q;
  25.     for(int i=1;i<=n;++i)q.push({h[i],i,i-1});
  26.     
  27.     int ans=0;
  28.     while(q.size()){
  29.         Node now=q.top();
  30.         q.pop();
  31.         if(now.h==1)continue;
  32.         
  33.         while(q.size() and now.h==q.top().h and now.l==q.top().idx){
  34.             now.l=q.top().l;
  35.             q.pop();
  36.         }
  37.         
  38.         now.h=sqrt(now.h/2+1);
  39.         if(now.h>1)q.push(now);
  40.         ans++;
  41.     }
  42.     cout<<ans;
  43. }
  44.  
  45. signed main(){
  46.     ios::sync_with_stdio(false),cin.tie(nullptr);
  47.     solve();
  48.     return 0;
  49. }

当然这样还AC不了，sqrt有三种形式

double sqrt(double x);     有效位数15~16

float sqrtf(float x);       这个就不标了，一般不用，一般都是上面那个

long double sqrtl(long double x);   有效位数18~19

这道题题目范围能到1e18，sqrt丢失精度了，导致答案错误。

使用sqrtl即可。

蓝桥杯官方也能过，OJ也能过。

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号