第十四屆藍橋杯青少年組省賽編程題真題題解

明天我就要考藍橋杯省賽了，本蒟蒻已瑟瑟發抖，所以現在寫一篇文章。

題目分別為：

1.??????B4270 [藍橋杯青少年組省賽 2023] 特殊運算符

2.B4271 [藍橋杯青少年組省賽 2023] 四葉玫瑰數

3.B4272 [藍橋杯青少年組省賽 2023] 質因數的個數

4.B4273 [藍橋杯青少年組省賽 2023] 最大的矩形紙片

……（本人只講解前四道題，后兩道是藍題，不會做了）

題解開始：

第一題：

題目描述

假定有一個運算符?>>>，它的功能如下所示：

>>>?257=25>>>?182=18>>>?933=93

給定一個正整數?N(100<N<1000)，請計算?N?(>>>?N)?的結果。

例如：N=257?時，257?(>>>?257)=257?25=232。

輸入格式

輸入一個正整數?N(100<N<1000)。

輸出格式

輸出一個整數，表示?N?(>>>?N)?的結果

輸入輸出樣例

輸入 #1復制

輸出 #1復制

這道題十分簡單，這里不多說，直接上AC代碼：

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){cin>>n;cout<<n-(n/100*10+n/10%10);return 0;
}

時間復雜度：O(1)

第二題：

題目描述

四葉玫瑰數是指一個四位數，其各位上的數字的四次方之和等于本身。

給定兩個正整數?N?和?M?，請將?N～M(1≤N≤M≤1000000)?之間（含?N?和?M）的四葉玫瑰數按從小到大的順序輸出。

例如：N=1234，M=2345?時，有一個四葉玫瑰數?1634，因為?14+64+34+44=1634，故輸出?1634。

輸入格式

第一行輸入兩個正整數?N,M(1≤N≤M≤1000000)。

輸出格式

輸出一行，包含若干個用一個空格隔開的正整數，表示?N～M?之間的四葉玫瑰數按從小到大的順序的輸出結果。

題目數據保證給定的?N～M?范圍內至少有一個四葉玫瑰數

輸入輸出樣例

輸入 #1復制

1234 2345

輸出 #1復制

這道題照樣簡單，先寫一個for循環，從N開始到M結束。每一次for循環，都求出各個數位的4次方之和，最后判斷一下是否等于i就行了。上AC代碼：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){cin>>n>>m;int sum=0;for(int i=n;i<=m;i++){if(i<=999||i>9999) continue;int t=i;sum=pow(i/1000,4)+pow(i/100%10,4)+pow(i/10%10,4)+pow(i%10,4);if(sum==t) cout<<sum<<' ';}return 0;
}

時間復雜度：O(m-n)

第三題：

題目背景

因數：又稱為約數，如果整數?a?除以整數?b(b=0)?的商正好是整數而沒有余數，我們就說?b?是?a?的因數。
質數：又稱為素數，一個大于?1?的自然數，除了?1?和它自身外，不能被其他自然數整除的數叫做質數。2?是最小的質數。
質因數：如果一個數?a?的因數?b?同時也是質數，那么?b?就是?a?的一個質因數，例如：8=2×2×2，2?就是?8?的質因數；12=2×2×3，2?和?3?就是?12?的質因數。

題目描述

給定兩個正整數?N?和?M(1≤N≤M≤107)，統計?N?到?M?之間（含?N?和?M）每個數所包含的質因數的個數，輸出其中最大的個數。

例如：當?N=6,M=10，6?到?10?之間：

6?的質因數是?2,3，共有?2?個；
7?的質因數是?7，共有?1?個；
8?的質因數是?2,2,2，共有?3?個；
9?的質因數是?3,3，共有?2?個；
10?的質因數是?2,5，共有?2?個；

6?到?10?之間的數中質因數最多的是?8，質因數有?3?個，故輸出?3。

輸入格式

輸入兩個正整數?N?和?M(1≤N≤M≤107)，兩個正整數之間用一個空格隔開。

輸出格式

輸出一個整數，表示質因數個數中的最大值。

輸入輸出樣例

輸入 #1復制

6 10

輸出 #1復制

這道題有兩種做法：

第一種：暴力

代碼：

#include<bits/stdc++.h>
using namespace std;
vector<int> gp(int x){vector<bool> p(x+1,true);p[0]=p[1]=false;for(int i=2;i<=sqrt(x);i++){if(p[i]){for(int j=i*i;j<=x;j+=i){p[j]=false;}}}vector<int> pp;for(int i=2;i<=x;i++){if(p[i]){pp.push_back(i);}}return pp;
}
int zys(int num,const vector<int>& pp){int cnt=0;for(int p:pp){if(p*p>num) break;if(num%p==0){while(num%p==0){num/=p;cnt++;}}}if(num>1){cnt++;}return cnt;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;vector<int> ppp=gp(m);int maxx=0;for(int i=n;i<=m;i++){int c=zys(i,ppp);if(c>maxx){maxx=c;}}cout<<maxx;return 0;
}

但是只得90分，要想進入國賽，這道題必須拿下（除非你會做后面3題）。所以：

第二種做法：DP優化

代碼：

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[10000005],ans=0;
bool vis[10000005];
int main(void){cin>>n>>m;for(int i=2;i<=m;i++){if(vis[i]) continue;dp[i]=1;for(int j=2;j<=m/i;j++){vis[i*j]=true;dp[i*j]=dp[j]+1;}}for(int i=n;i<=m;i++){ans=max(ans,dp[i]);}cout<<ans;return 0;
}

時間復雜度：O(m log m)

第四題：

題目描述

一張半邊參差不齊的網格紙（網格邊長均為?1），有一邊是完整沒有破損的。現要從中剪出一片面積最大的矩形紙片。

給定網格紙中完整邊的長度?N（1≤N≤1000000），以及網格中每一列殘存部分的高度（1≤?高度?≤10000），輸出能夠剪出的最大矩形紙片面積。

輸入格式

第一行輸入一個正整數?N（1≤N≤1000000），表示紙片完整邊的長度。

第二行輸入?N?個正整數（1≤?正整數?≤10000），表示每列格子殘存部分的高度，兩個正整數之間用一個空格隔開。

輸出格式

輸出一個正整數，表示能夠剪出的最大矩形紙片面積。

輸入輸出樣例

輸入 #1復制

6
3 2 1 4 5 2

輸出 #1復制

先讀題，給定?n?個寬為?1?的矩形，每個矩形的高各不相同。將它們拼在一起，要求在從中剪出一塊最大的矩形紙片。
我們很自然可以想到枚舉左右起始位置，在枚舉中間的位置來計算當前區間內的最大矩形長度，再來更新答案。

#include<bits/stdc++.h>
using namespace std;
int h[1000001];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>h[i];}int maxn=0;for(int i=1;i<=n;i++){int m=1e9+1;for(int j=i;j<=n;j++){for(int k=i;k<=j;k++){m=min(m,h[k]);} maxn=max(maxn,m*(j-i+1));}}cout<<maxn<<endl;return 0;
}

結果……30?分
我們可以發現該解法的時間復雜度為?O(n3)。所以我們得換一種方法來寫。我們可以先假設矩形長度遞增，那么我們該如何做？
很顯然，我們可以嘗試將當前的矩形的高度作為最后矩形的高度，并將該矩形的寬一直延伸到右邊界，再算出矩形的面積用來更新答案。
所以我們看回這道題，我們可以利用上面的結論，如果下一個矩形的高度比上一個小，那么該矩形想與前面的矩形拼成一個更大的矩形，那么之前的矩形高于當前矩形的面積就沒有任何用處了(如下圖中打叉的部分)。

所以我們就可以用到一種算法來解決這種問題————單調棧。
我們只需要建立一個棧，用來維護一個高度始終單調的序列，這樣我們就可以解決這個問題了。
我們先從左到右依次掃描每個矩形，如果當前的矩形高度高于棧頂矩形，就讓其進棧；否則就不斷取出棧頂，直至棧為空或棧頂矩形的高度比當前矩形小。出棧過程中我們累加彈出矩形的寬度，并且在每次彈出時，就用其高度乘以累加的寬度去更新答案。出棧結束后，我們再把一個高度為當前矩形高度、寬度為累加值的矩形入棧。注意，結束后，要將棧中剩下的矩形依次彈出，采用上面相同的方法來更新答案。所以我們可以增加一個高度為?0?的矩形，避免再掃描結束后有剩余矩形。

AC代碼1——數組模擬：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[1000001];
int s[1000001];
int w[1000001];
int n;
signed main(){int p=0,ans=0;cin>>n;for(int i=1;i<=n;i++) cin>>a[i]; a[n+1]=0; for(int i=1;i<=n+1;i++){if(a[i]>s[p]){s[++p]=a[i];w[p]=1;}else{int width=0;while(s[p]>a[i]){width+=w[p];ans=max(ans,(long long)width*s[p]);p--;}s[++p]=a[i];w[p]=width+1;}}cout<<ans<<endl;return 0;
}

AC代碼2——STL：

#include<bits/stdc++.h>
using namespace std;
struct node{int h,w;
};
stack<node>s;
long long a[1000001];
long long ans=0;
int main(){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];a[n+1]=0;for(int i=1;i<=n+1;i++){long long width=0;while(!s.empty() && a[i]<s.top().h){//單調遞增width=width+s.top().w;ans=max(ans,width*s.top().h);s.pop();}s.push( (node){a[i],width+1} );}cout<<ans<<endl;return 0;
}

好了寶子們，今天的題解就到這里，我們明天再會！

制作不易，點個關注再走叭！