寫在最前面：
本文中會(huì)出現(xiàn)大量的請(qǐng)查閱.請(qǐng)自學(xué)什么的，不是我不講，本文是面向算法初學(xué)者和藍(lán)橋杯的文章，如果真的想看進(jìn)階算法的也不會(huì)來看這些題目，所以不要介意，我這里就算是拋磚引玉了，大佬勿噴，ACMEer繞道哈哈哈哈。

1.楊輝三角形

問題描述

楊輝三角形又稱Pascal三角形，它的第i+1行是(a+b)i的展開式的系數(shù)。 它的一個(gè)重要性質(zhì)是：三角形中的每個(gè)數(shù)字等于它兩肩上的數(shù)字相加。下面給出了楊輝三角形的前4行：11 11 2 1 1 3 3 1 給出n，輸出它的前n行。輸入格式 輸入包含一個(gè)數(shù)n。輸出格式 輸出楊輝三角形的前n行。每一行從這一行的第一個(gè)數(shù)開始依次輸出，中間使用一個(gè)空格分隔。請(qǐng)不要在前面輸出多余的空格。樣例輸入 4 樣例輸出 1 1 1 1 2 1 1 3 3 1數(shù)據(jù)規(guī)模與約定 1 <= n <= 34。

楊輝三角形入門的話就是考察代碼編寫，是個(gè)模擬題目，當(dāng)數(shù)據(jù)量達(dá)到一定程度之后是組合數(shù)問題，可以使用盧卡斯定理，這里是入門，暫且不提，有興趣可以去我博客數(shù)論查找！

#include <bits/stdc++.h> using namespace std; int s[1000], a[1000];void print(int source[], int ans[], int now, int target) //狀態(tài)轉(zhuǎn)移 {for (int i = 0; i < now; i++){i == 0 ? ans[i] = 1 : ans[i] = source[i] + source[i - 1];cout << ans[i] << "\t";}puts("");if (now == target)return;print(ans, source, now + 1, target); } int main() {int n;cin >> n;print(s, a, 1, n); }

2.字符串比較

問題描述給定兩個(gè)僅由大寫字母或小寫字母組成的字符串(長(zhǎng)度介于1到10之間)，它們之間的關(guān)系是以下4中情況之一：1：兩個(gè)字符串長(zhǎng)度不等。比如 Beijing 和 Hebei2：兩個(gè)字符串不僅長(zhǎng)度相等，而且相應(yīng)位置上的字符完全一致(區(qū)分大小寫)，比如 Beijing 和 Beijing3：兩個(gè)字符串長(zhǎng)度相等，相應(yīng)位置上的字符僅在不區(qū)分大小寫的前提下才能達(dá)到完全一致（也就是說，它并不滿足情況2）。比如 beijing 和 BEIjing4：兩個(gè)字符串長(zhǎng)度相等，但是即使是不區(qū)分大小寫也不能使這兩個(gè)字符串一致。比如 Beijing 和 Nanjing編程判斷輸入的兩個(gè)字符串之間的關(guān)系屬于這四類中的哪一類，給出所屬的類的編號(hào)。 輸入格式包括兩行，每行都是一個(gè)字符串 輸出格式僅有一個(gè)數(shù)字，表明這兩個(gè)字符串的關(guān)系編號(hào) 樣例輸入 BEIjing beiJing 樣例輸出 3

直接可以討論用c++的string即可，相關(guān)的string操作：1.可以判等== 2.可以比較字典序 < 或 > 3.reserve反轉(zhuǎn) 4.length()判斷長(zhǎng)度

#include <bits/stdc++.h> using namespace std; int compare(string s1,string s2) {if(s1.length()==s2.length()){if(s1==s2)return 2;for(int i=0;i<s2.length();i++){if(toupper(s1[i])!=toupper(s2[i])) return 4;}return 3;}else return 1; } int main() {string s1,s2;cin>>s1>>s2;cout<<compare(s1,s2); }

3.N皇后問題Plus

問題描述給定一個(gè)n*n的棋盤，棋盤中有一些位置不能放皇后?，F(xiàn)在要向棋盤中放入n個(gè)黑皇后和n個(gè)白皇后，使任意的兩個(gè)黑皇后都不在同一行、同一列或同一條對(duì)角線上，任意的兩個(gè)白皇后都不在同一行、同一列或同一條對(duì)角線上。問總共有多少種放法？n小于等于8。 輸入格式輸入的第一行為一個(gè)整數(shù)n，表示棋盤的大小。接下來n行，每行n個(gè)0或1的整數(shù)，如果一個(gè)整數(shù)為1，表示對(duì)應(yīng)的位置可以放皇后，如果一個(gè)整數(shù)為0，表示對(duì)應(yīng)的位置不可以放皇后。 輸出格式輸出一個(gè)整數(shù)，表示總共有多少種放法。 樣例輸入 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 樣例輸出 2 樣例輸入 4 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 樣例輸出 0

解析
N皇后問題，是一類搜索問題，這里我們使用4個(gè)數(shù)組來保證米字的形狀沒有皇后，斜線的保存我們要發(fā)現(xiàn)一條左斜線的橫坐標(biāo)減縱坐標(biāo)是相同的，同一右斜線上的點(diǎn)橫縱坐標(biāo)相加的值相同，由此我們可以推理出以下搜索策略

#include <bits/stdc++.h> using namespace std; int mp[10][10]; int hen[10], shu[10], zuo[100], you[100]; int ans = 0; void js(int len, int cen) {if (cen == len){ans++;return;}// puts("--------------------------------------------------------\n");// for (int i = 0; i < len; i++)// {// for (int j = 0; j < len; j++)// {// cout<< mp[i][j]<<" ";// }// puts("");// }for (int i = 0; i < len; i++){if (hen[i] == 0 && shu[i] == 0 && zuo[(cen + i) / 2] == 0 && you[cen - i + len] == 0 && mp[cen][i]){mp[cen][i] = 0;hen[i] = shu[i] = zuo[(cen + i + 1) / 2] = you[cen - i + len] = 1;js(len, cen + 1);mp[cen][i] = 1;hen[i] = shu[i] = zuo[(cen + i + 1) / 2] = you[cen - i + len] = 0;}}return; } int main() {int n;cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++){cin >> mp[i][j];}js(n, 0);cout << ans << endl; }

4.導(dǎo)彈攔截

問題描述某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。 輸入格式一行，為導(dǎo)彈依次飛來的高度 輸出格式兩行，分別是最多能攔截的導(dǎo)彈數(shù)與要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)樣例輸入 389 207 155 300 299 170 158 65樣例輸出 6 2

這是一類動(dòng)態(tài)規(guī)劃問題，LIS問題。
第一問是求一個(gè)數(shù)列的最長(zhǎng)下降子序列，第二問則是最長(zhǎng)的非嚴(yán)格上升子序列(如3 3 2 1，可以相等）因?yàn)樽铋L(zhǎng)上升子序列的每一個(gè)高度都需要一套攔截系統(tǒng)，彼此獨(dú)立。

#include <bits/stdc++.h> using namespace std; int h[1000]; int dp[1000][2]; map<int,int> cou; pair<int,int> Lis(int a[],int len) {int ans=0,cnt=0;for(int i=0;i<len;i++){for(int j=0;j<i;j++){if(h[j]<h[i]) dp[i][0]=max(dp[i][0],dp[j][0]+1);else dp[i][1]=max(dp[i][1],dp[j][1]+1);ans=max(ans,dp[i][0]);cnt=max(cnt,dp[i][1]);}}return make_pair(ans+1,cnt+1); } int main() {int n;cin >> n;for (int i = 0; i < n; i++)cin >> h[i];auto answ=Lis(h,n);cout<<answ.first<<" "<<answ.second <<endl;}

5.Fibonacci數(shù)列

問題描述Fibonacci數(shù)列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1。當(dāng)n比較大時(shí)，Fn也非常大，現(xiàn)在我們想知道，Fn除以10007的余數(shù)是多少。 輸入格式 輸入包含一個(gè)整數(shù)n。 輸出格式 輸出一行，包含一個(gè)整數(shù)，表示Fn除以10007的余數(shù)。說明：在本題中，答案是要求Fn除以10007的余數(shù)，因此我們只要能算出這個(gè)余數(shù)即可，而不需要先計(jì)算出Fn的準(zhǔn)確值，再將計(jì)算的結(jié)果除以10007取余數(shù)，直接計(jì)算余數(shù)往往比先算出原數(shù)再取余簡(jiǎn)單。 樣例輸入 10 樣例輸出 55 樣例輸入 22 樣例輸出 7704 數(shù)據(jù)規(guī)模與約定 1 <= n <= 1,000,000。

因?yàn)槭侨腴T，藍(lán)橋杯也考不了這么難，這里寫遞推。如果有興趣進(jìn)階的話，可以研究下，矩陣快速冪，和母函數(shù)的做法，我博客里應(yīng)該都有！

#include <bits/stdc++.h> using namespace std; const int MOD=10007; int f[100000]; int init(int n) {f[1]=f[2]=1;for(int i=3;i<=n;i++)f[i]=f[i-1]+f[i-2]%MOD; } int main() {int n;cin>>n;init(n);cout<<f[n]<<endl; }

6.校門外的樹

問題描述某校大門外長(zhǎng)度為L(zhǎng)的馬路上有一排樹，每?jī)煽孟噜彽臉渲g的間隔都是1米。我們可以把馬路看成一個(gè)數(shù)軸，馬路的一端在數(shù)軸0的位置，另一端在L的位置；數(shù) 軸上的每個(gè)整數(shù)點(diǎn)，即0，1，2，……，L，都種有一棵樹。由于馬路上有一些區(qū)域要用來建地鐵。這些區(qū)域用它們?cè)跀?shù)軸上的起始點(diǎn)和終止點(diǎn)表示。已 知任一區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)都是整數(shù)，區(qū)域之間可能有重合的部分。現(xiàn)在要把這些區(qū)域中的樹（包括區(qū)域端點(diǎn)處的兩棵樹）移走。你的任務(wù)是計(jì)算將這些樹 都移走后，馬路上還有多少棵樹。輸入格式輸入文件的第一行有兩個(gè)整數(shù)L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長(zhǎng)度，M代表區(qū)域的數(shù)目，L和M之間用一個(gè)空格隔開。接下來的M行每行包含兩個(gè)不同的整數(shù)，用一個(gè)空格隔開，表示一個(gè)區(qū)域的起始點(diǎn) 和終止點(diǎn)的坐標(biāo)。 輸出格式輸出文件包括一行，這一行只包含一個(gè)整數(shù)，表示馬路上剩余的樹的數(shù)目。樣例輸入 500 3 150 300 100 200 470 471 樣例輸出 298數(shù)據(jù)規(guī)模和約定對(duì)于20%的數(shù)據(jù)，區(qū)域之間沒有重合的部分；對(duì)于其它的數(shù)據(jù)，區(qū)域之間有重合的情況。

這道題很簡(jiǎn)單是簽到題，就是考察的模擬，會(huì)不會(huì)處理區(qū)間重疊情況，這道題的進(jìn)階做法是差分，有興趣的可以查閱，我們這里只是藍(lán)橋杯和入門

#include <bits/stdc++.h> using namespace std; int a[1000000]; int main() {int n,m;cin>>n>>m;for(int i=0;i<m;i++){int l,r;cin>>l>>r;for(int j=l;j<=r;j++){a[j]=-1;}}int ans=0;for(int i=0;i<=n;i++)if(a[j]==0) ans++;cout<<ans<<endl;}

7.奪寶奇兵

算法提高 奪寶奇兵 時(shí)間限制：1.0s 內(nèi)存限制：512.0MB[題目描述]在一座山上,有很多很多珠寶,它們散落在山底通往山頂?shù)拿織l道路上,不同道路上的珠寶的數(shù)目也各不相同.下圖為一張藏寶地圖:73 88 1 02 7 4 44 5 2 6 5”奪寶奇兵”從山下出發(fā),到達(dá)山頂,如何選路才能得到最多的珠寶呢?在上圖所示例子中,按照5->7->8->3->7的順序,將得到最大值30[輸入]第一行正整數(shù)N(100>=N>1),表示山的高度接下來有N行非負(fù)整數(shù),第i行有i個(gè)整數(shù)(1<=i<=N),表示山的第i層上從左到右每條路上的珠寶數(shù)目[輸出]一個(gè)整數(shù),表示從山底到山頂?shù)乃艿玫降闹閷毜淖畲髷?shù)目. [樣例輸入] 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5[樣例輸出]30

經(jīng)典DP算法，可以自下而上也可以從上向下，每次只保留最優(yōu)的選擇方案，狀態(tài)轉(zhuǎn)移方程為：
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + mountain[i][j];

#include <bits/stdc++.h> using namespace std; int mountain[MAXN][MAXN]; int dp[MAXN + 1][MAXN + 1];int main() {cin>>n;for (int i = 0; i < N; ++i){for (int j = 0; j <= i; ++j)cin>>mountain[i][j];}for (int i = N - 1; i >= 0; --i){for (int j = 0; j <= i; ++j){dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + mountain[i][j];}}cout<<dp[0][0]<<endl; }

8.質(zhì)因數(shù)分解

基礎(chǔ)練習(xí) 分解質(zhì)因數(shù) 時(shí)間限制：1.0s 內(nèi)存限制：512.0MB問題描述求出區(qū)間[a,b]中所有整數(shù)的質(zhì)因數(shù)分解。 輸入格式輸入兩個(gè)整數(shù)a，b。 輸出格式每行輸出一個(gè)數(shù)的分解，形如k=a1*a2*a3...(a1<=a2<=a3...，k也是從小到大的)(具體可看樣例) 樣例輸入 3 10 樣例輸出 3=3 4=2*2 5=5 6=2*3 7=7 8=2*2*2 9=3*3 10=2*5 提示先篩出所有素?cái)?shù)，然后再分解。 數(shù)據(jù)規(guī)模和約定2<=a<=b<=10000

因?yàn)槭菍?duì)區(qū)間進(jìn)行分解，那么質(zhì)因數(shù)將會(huì)用到很多次，我們不能每一次都進(jìn)行試除法，所以預(yù)先達(dá)標(biāo)保留，我這里只用了一次試除法，每次對(duì)求出小于右端點(diǎn)的所有質(zhì)因子，這里用了一個(gè)小優(yōu)化，一個(gè)數(shù)的一對(duì)因子不可能都大于他開根號(hào)，對(duì)于質(zhì)數(shù)的篩法有埃式篩法和線性篩法我博客里也有可以去看，寫到這里真的用不著，時(shí)間給的很充足。

#include <bits/stdc++.h> using namespace std; int prime[10000], cnt = 0; void init(int n) {for (int i = 2; i < n; i++){int flag = 0;for (int j = 2; j * j <= i; j++){if (i % j == 0){flag = 1;break;}}if (flag == 1)continue;else{prime[++cnt] = i;}} } void fj(int n) {cout << n << "=";int flag = 0;for (int i = 1; prime[i] <= n; i++){while (n % prime[i] == 0){if (!flag){flag = 1;}elsecout << "*";cout << prime[i];n /= prime[i];}}puts(""); } int main() {int l, r;cin >> l >> r;init(r);for (int i = l; i <= r; i++){fj(i);} }

寫在最后：
我叫風(fēng)骨散人，名字的意思是我多想可以不低頭的自由生活，可現(xiàn)實(shí)卻不是這樣。家境貧寒，總得向這個(gè)世界低頭，所以我一直在奮斗，想改變我的命運(yùn)給親人好的生活，希望同樣被生活綁架的你可以通過自己的努力改變現(xiàn)狀，深知成年人的世界里沒有容易二字。目前是一名在校大學(xué)生，預(yù)計(jì)考研，熱愛編程，熱愛技術(shù)，喜歡分享，知識(shí)無界，希望我的分享可以幫到你！
如果有什么想看的，可以私信我，如果在能力范圍內(nèi)，我會(huì)發(fā)布相應(yīng)的博文！
感謝大家的閱讀！😘你的點(diǎn)贊、收藏、關(guān)注是對(duì)我最大的鼓勵(lì)！

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯--算法入门级题目及答案解析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。