前言

大家好！我是 EnigmaCoder。

• 本文是我藍橋杯刷題計劃的第二周。附：藍橋杯刷題周計劃（第一周)
• 本文含有20題，刷題內容涵蓋DFS、數論相關、數據結構相關等等，每道題分為題目、代碼、題解分析三部分，且附有原題鏈接。
• 希望能幫助到大家！

題目一

原題鏈接：lanqiao1508

題目

N皇后問題

題目描述*

在 N×N的方格棋盤放置了 N 個皇后，使得它們不相互攻擊（即任意 2個皇后不允許處在同一排，同一列，也不允許處在與棋盤邊框成 45 角的斜線上。你的任務是，對于給定的 N，求出有多少種合法的放置方法。

輸入描述

輸入中有一個正整數 N≤10，表示棋盤和皇后的數量

輸出描述

為一個正整數，表示對應輸入行的皇后的不同放置數量。

輸入輸出樣例

示例 1

輸入

5

輸出

10

運行限制

• 最大運行時間：1s
• 最大運行內存: 128M

代碼

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=11;
int vis[N][N];
int n,ans=0;
void dfs(int dep){if(dep==n+1){ans++;return;}for(int i=1;i<=n;i++){if(vis[dep][i])continue;for(int _i=1;_i<=n;_i++)vis[_i][i]++;for(int _i=dep,_j=i;_i>=1&&_j>=1;_i--,_j--)vis[_i][_j]++;for(int _i=dep,_j=i;_i<=n&&_j>=1;_i++,_j--)vis[_i][_j]++;for(int _i=dep,_j=i;_i>=1&&_j<=n;--_i,++_j)vis[_i][_j]++;for(int _i=dep,_j=i;_i<=n&&_j<=n;++_i,++_j)vis[_i][_j]++;dfs(dep+1);for(int _i=1;_i<=n;_i++)vis[_i][i]--;for(int _i=dep,_j=i;_i>=1&&_j>=1;_i--,_j--)vis[_i][_j]--;for(int _i=dep,_j=i;_i<=n&&_j>=1;_i++,_j--)vis[_i][_j]--;for(int _i=dep,_j=i;_i>=1&&_j<=n;--_i,++_j)vis[_i][_j]--;for(int _i=dep,_j=i;_i<=n&&_j<=n;++_i,++_j)vis[_i][_j]--;}
}
int main()
{cin>>n;dfs(1);cout<<ans;return 0;
}

題解分析

本題為經典的DFS題，使用回溯法可以解決。

• 首先可以肯定的是，每一行必然有且僅有一個皇后（因為不可能出現兩個皇后在同一行），于是就通過枚舉每一層皇后的位置來搜索所有可能解即可。
• 每放置一個皇后就將對應的米字型區域設置為“禁區”，后面的皇后就不能放在“禁區”，回溯的時候將禁區取消掉。同時，為了正確維護“禁區”，不能使用bool數組來表示禁區，需要使用int數組，表示這個位置被“多少個皇后占用了”，當占用數為0時表示“禁區解除”。
• 層數到n+1時表示找到了一個解，不可行的解都到不了第n+1行

---

題目二

原題鏈接：lanqiao1260

題目

題目描述
給定兩個正整數A,B，求它們的最大公約數

輸入描述
第 1 行為一個整數 T，表示測試數據數量。

接下來的 T 行每行包含兩個正整數 A,B。
1≤T≤10⁵ 1≤A,B≤10⁹ 。

輸出描述
輸出共 T 行，每行包含一個整數，表示答案。

輸入輸出樣例
示例 1
輸入

5
2 4
3 7
5 10
6 8
7 9
輸出

2
1
5
2
1

運行限制

• 最大運行時間：2s
• 最大運行內存: 128M

代碼

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);
}
int main()
{int t;cin>>t;while(t--){int a,b;cin>>a>>b;cout<<gcd(a,b)<<endl;}return 0;
}

題解分析

本題考察最大公約數。

• 通過輾轉相除法和三目運算符求最大公約數。 b==0?a:gcd(b,a%b);
• 我們知道兩數相乘等于兩數最大公約數和最小公倍數，所以可以通過最大公約數求最小公倍數。return a/gcd(a,b)*b;這里先除再乘是為了減少溢出的發生。

---

題目三

原題鏈接：lanqiao3205

題目

問題描述
給定一個正整數 n，請你計算 1～n 中有多少對不同的素數，滿足它們的差也是素數。

輸入格式
共一行，包含一個正整數 n(2≤n≤10⁵ )。

輸出格式
共一行，包含一個正整數，表示答案。

樣例輸入
5
樣例輸出
2
樣例輸入
20
樣例輸出
8

代碼

#include <bits/stdc++.h>
using ll=long long;
const int N=1e5+10;
using namespace std;
vector<int>primes;
bool vis[N];void init(int n){vis[0]=vis[1]=true;for(ll i=2;i<=n;i++){if(!vis[i]){primes.push_back(i);for(int j=2*i;j<=n;j+=i)vis[j]=true;}}
}
int main()
{int n,ans=0;cin>>n;init(n);for(int i=0;i<primes.size();i++){for(int j=0;j<i;j++){if(!vis[primes[i]-primes[j]])ans++;}}cout<<ans<<endl;return 0;
}

題解分析

本題使用埃式篩法求素數。

• 埃式篩法，即埃拉托斯特尼篩法，是一種用于求一定范圍內所有素數的高效算法。其原理是：從2開始，將每個素數的倍數都標記為合數并篩去，剩下的未被篩去的數就是素數。

• 例如求100以內的素數，先將2標記為素數，篩去其倍數4、6、8等；接著3未被篩去，標記為素數，篩去6、9、12等；依此進行。該算法簡單直觀，時間復雜度為O(n\log\log n)，相比暴力枚舉效率更高，能快速篩選出大量素數，在數論和密碼學等領域應用廣泛。

• 通過bool類型的數組來記錄當前值是否為素數，false表示為素數，true表示不為素數。

---

題目四

原題鏈接：lanqiao3199

題目

問題描述

小明又新學了一個概念，叫做完美序列。一個僅包含數字序列被稱為完美序列，當且僅當數字序列中每個數字出現的次數等于這個數字。比如 (1)，(2,2,3,3,3))。空序列也算。現在小明得到了一個數字序列，他想知道最少要刪除多少個數字才能使得這個數字序列成為一個完美序列。

輸入格式

輸入包括兩行。

第一行一個整數 n，表示數字序列中數字的個數。

第二行，包括 n個整數，是數字序列中具體的每個數字。

輸出格式

輸出一個整數，表示最少要刪除的數字個數。

樣例輸入

6
3 3 3 1 13 15 

樣例輸出

2

評測數據規模

對于所有評測數據，1≤n≤10⁵,ai≤10⁹。

代碼

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
int main()
{int n,x;cin>>n;map<int ,int>mp;while(n--){cin>>x;mp[x]++;}int ans=0;for(auto pair:mp){int key=pair.first;int value=pair.second;if(value>=key)ans+=value-key;else ans+=value;}cout<<ans;return 0;
}

題解分析

本題使用map容器解題。

• 代碼通過讀取整數數量 n 及 n 個整數，用 map 統計每個整數出現次數。之后遍歷 map 中的鍵值對，鍵為整數，值為該整數出現次數。根據值與鍵的大小關系計算累加結果：若值大于等于鍵，累加差值；若值小于鍵，累加值本身。最終輸出累加結果。整體時間復雜度為 O(nlogn)。

• pair.first是pair的鍵，pair.second是pair的值。

• mp[x]++表示mp中x對應的值加1。

---

題目五

原題鏈接：lanqiao1811

題目

題目描述
給定三個正整數 N,M,P，求 N^Mmodp。

輸入描述
第 1 行為一個整數 T，表示測試數據數量。

接下來的 T行每行包含三個正整數
N,M,P。
1≤T≤10⁵ 1≤N,M,P≤10⁹

輸出描述

輸出共 T 行，每行包含一個整數，表示答案。

輸入輸出樣例
示例 1
輸入

3
2 3 7
4 5 6
5 2 9
輸出

1
4
7

代碼

#include <bits/stdc++.h>
using namespace std;
using ll=long long;ll qmi(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p,b>>=1;}return res;
}int main()
{int t;cin>>t;while(t--){ll n,m,p;cin>>n>>m>>p;cout<<qmi(n,m,p)<<endl;}return 0;
}

題解分析

這道題主要是利用快速冪取模算法解決多組冪運算取模問題。

• 代碼通過 qmi 函數實現快速冪取模，其核心思想是將指數進行二進制拆分，減少乘法運算次數。
• 在 qmi 函數中，不斷將底數平方并對指數右移，若指數當前位為 1 則累乘底數到結果中并取模。主函數讀取多組輸入數據，每組包含底數、指數和模數，調用 qmi 函數計算結果并輸出。
• 時間復雜度為 O(logm)，空間復雜度為 O(1)，能高效處理大規模冪運算取模。

---

題目六

原題鏈接：lanqiao504

題目

題目描述
小藍正在學習一門神奇的語言，這門語言中的單詞都是由小寫英文字母組成，有些單詞很長，遠遠超過正常英文單詞的長度。小藍學了很長時間也記不住一些單詞，他準備不再完全記憶這些單詞，而是根據單詞中哪個字母出現得最多來分辨單詞。

現在，請你幫助小藍，給了一個單詞后，幫助他找到出現最多的字母和這 個字母出現的次數。

輸入描述
輸入一行包含一個單詞，單詞只由小寫英文字母組成。

對于所有的評測用例，輸入的單詞長度不超過 1000。

輸出描述
輸出兩行，第一行包含一個英文字母，表示單詞中出現得最多的字母是哪 個。如果有多個字母出現的次數相等，輸出字典序最小的那個。

第二行包含一個整數，表示出現得最多的那個字母在單詞中出現的次數。

輸入輸出樣例
示例 1
輸入

lanqiao
輸出

a
2
示例 2
輸入

longlonglongistoolong

輸出

o
6

運行限制

• 最大運行時間：1s
• 最大運行內存: 256M

代碼

#include <bits/stdc++.h>
using namespace std;
int main()
{string s;cin>>s;map<char,int>mp;for(int i=0;i<s.size();i++){mp[s[i]]++;}int ans=-1;char c;for(auto pair:mp){char key=pair.first;int value=pair.second;if(value>ans){c=key;ans=value;}}cout<<c<<endl;cout<<ans<<endl;return 0;
}

題解分析

本題需要記錄字符串中出現最多的字母和這個字母出現的次數，我們可以使用map容器解題，其中鍵是字母，值是字母出現的次數。

• 由題意，如果有多個字母出現的次數相等，輸出字典序最小的那個。所以，題解中必須是value大于ans,否則輸出的不是字典序最小的那個。
• map容器只能通過鍵找到值，而無法通過值找到鍵。所以，可以定義一個與相同類型的變量跟隨ans進行變化，從而找到值對應的鍵。

---

題目七

原題鏈接：lanqiao3186

題目

問題描述
wzy 給你了一個 n×n 的 01 矩陣 a，你需要求一下滿足 a i,j =a i,k =a j,k =1的三元組 (i,j,k) 的個數。

注：給定的矩陣一定滿足ai,j=a j,i 。同時，(1,2,3),(3,2,1) 這種視作同一個三元組，且 i≠j,j≠k,i≠ki=j,j=k,i\=k。

輸入格式
第一行輸入一個數字 n，表示矩陣大小。(1≤n≤800)

接來下 n 行，每行一個長度為 n 的 01 串。

輸出格式
輸出滿足條件的三元組數量。

樣例輸入
4
0011
0011
1101
1110

樣例輸出
2

代碼

#include <bits/stdc++.h>
using namespace std;
using ll=long long;        
int a[2010][2010];                                                                                                                                          
int main()
{string s;int n;cin>>n;for(int i=1;i<=n;i++){cin>>s;for(int j=1;j<=n;j++){a[i][j]=s[j-1]-'0';}}
long long ans=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){for(int k=j+1;k<=n;k++){if(a[i][j]==1&&a[i][k]==1&&a[j][k]==1)ans++;}}}cout<<ans;return 0;
}

題解分析

本題使用暴力枚舉的方式解題。

• 首先讀取矩陣的大小n和矩陣本身，將每個字符轉換為0或1并存儲在二維數組a中。
• 然后通過三層嵌套循環遍歷所有可能的i、j、k組合（滿足i < j < k），對于每個組合，檢查a[i][j]、a[i][k]和a[j][k]是否都為1，如果是，則將答案ans加1。
• 最后輸出ans的值。

題目八

原題鏈接：lanqiao11097

題目

問題描述
小藍是一個熱愛閱讀的年輕人，他有一個小型圖書館。為了能夠管理他的書籍庫存，他需要一個程序來記錄圖書的信息并執行兩種操作：添加圖書 add 和查找作者 find。

初始小藍沒有書，給出 n 個操作。add 操作給出兩個字符串 bookname,author，表示添加的圖書圖書名和作者；find 操作給出一個字符串 author，你需要輸出小藍的圖書館里這個author 有多少本圖書。

輸入格式
第一行一個整數 n，表示有 n 個操作。之后 n 行，給出操作及后面的參數，如題所述。

給出的字符串長度 len 不超過10。

輸出格式
對每一個find 操作，你需要輸出這個作者在小藍的圖書館有多少本書，注意是書的數量，不是不同書的數量，同時不同作者可能出現同名的書。

樣例輸入
7
find author1
add book1 author1
find author1
add book1 author1
find author1
add book1 author2
find author2

樣例輸出
0
1
2
1

評測數據規模
1≤n≤1000,1≤len≤10。

#include <bits/stdc++.h>
using namespace std;
int a[1010];
int main()
{int n;cin>>n;string s,t,e;map<string,int>mp;int i=0;while(n--){cin>>s;if(s=="find"){cin>>t;cout<<mp[t]<<endl;}if(s=="add"){cin>>e>>t;mp[t]++;}}return 0;
}

題解分析

本題使用map容器解題。

• 分為find和add兩種情況討論。
• auther為鍵，對應書的數量為值。每一次find輸出當前作者的書的數量即可。

---

題目九

原題鏈接：lanqiao4567

題目

問題描述
小藍有一個長度為 n 的數組 a ，現在對于每一個 ai ，小藍可以選擇下面三種操作之一：

• ai=ai-1
• ai=ai
• ai=ai+1

小藍想知道當她把每一個 ai都操作之后，數組眾數的數目最大是多少。但是小藍并不擅長這個問題，請你幫小藍計算所有操作完成之后數組眾數的最大數目。

輸入格式
第一行輸入一個整數，代表n 。

第二行輸入 n 個整數，代表 a1,a2,a3…,an 。

輸出格式
輸出一行一個整數，代表眾數的最大數目。

樣例輸入
3
1 2 3

樣例輸出
3

說明
對于樣例，將 a1加一，a3 減一，a2 不變，此時三個數都是2 ，而其他操作得到的結果眾數數目都小于3 ，所以最終答案是 3 。

代碼

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
ll a[N];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];map<ll,ll>mp;for(int i=1;i<=n;i++){mp[a[i]]++;mp[a[i]-1]++;mp[a[i]+1]++;}ll ans=0;for(int i=1;i<=n;i++){ans=max(ans,mp[a[i]]);}cout<<ans;return 0;
}

題解分析

本題仍然使用map容器解題。

• 題中有三種操作，可以對應到map容器中的三個鍵，通過枚舉數組中的每一個數，對其三種情況進行計數。
• 使用max庫函數最大眾數。

題目十

原題鏈接：lanqiao3272

題目

問題描述
小藍是一位有名的漆匠，他的朋友小橋有一個漆房，里面有一條長長的走廊，走廊兩旁有許多相鄰的房子，每間房子最初被涂上了一種顏色。

小橋來找小藍，想讓他把整個走廊都涂成同一個顏色。小藍告訴小橋，他每天只能涂一段長度為 k 的區間。對于每個區間，他可以選擇將其中的房子重新涂上任何一種顏色，或者保持原來的顏色不變。

小橋想知道小藍至少要涂幾天，才能讓整個走廊變得美麗。

請幫助小橋解決這個問題。

輸入格式
第一行包含一個整數 t(1≤100），表示測試用例的數量。

每個測試用例的第一行包含兩個整數 n 和 k（1≤k≤n≤10⁴ ），第二行包含 n 個整數 a1,a2,?,ana 1 ,a 2 ,?,a n （1≤ai≤60），分別表示每個房子最初的顏色。

保證所有測試用例中 n 的總和不超過 10 ⁴ 。

輸出格式
對于每個測試用例，輸出一個整數，表示小藍需要涂漆的最少天數。

樣例輸入
2
5 2
1 1 2 2 1
6 2
1 2 2 3 3 3

樣例輸出
1
2

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N],b[N];
int main()
{int t;cin>>t;int cut;while(t--){int n,k;cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];int ans=(1<<31)-1;for(int i=1;i<=60;i++){int cut=0;for(int j=1;j<=n;j++){b[j]=a[j];}for(int j=1;j<=n;j++){if(b[j]!=i){for(int h=j;h<=j+k-1;h++){b[h]=i;}cut++;j=j+k-1;}}ans=min(ans,cut);}cout<<ans<<endl;}return 0;
}

題解分析

本題核心思路是枚舉所有可能的目標值（從1到60），并對每個目標值模擬操作過程，計算所需的操作次數，最終取最小值。

• 枚舉目標值：遍歷所有可能的目標值i（1到60），假設最終數組的所有元素都變為i。
• 模擬操作：對于每個目標值i，復制原數組到臨時數組b，然后遍歷b數組。當遇到不等于i的元素時，執行一次操作，將從該位置開始的連續k個元素變為i，并增加操作次數。同時，跳過接下來的k-1個元素，避免重復操作。
• 更新最小值：記錄每個目標值i所需的操作次數，并更新全局最小值。

題目十一

原題鏈接：lanqiao1536

題目

上圖給出了一個數字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數加起來可以得到一個和，你的任務就是找到最大的和（路徑上的每一步只可沿左斜線向下或右斜線向下走）。

輸入描述

輸入的第一行包含一個整數 N (1≤N≤100)，表示三角形的行數。下面的 N 行給出數字三角形。數字三角形上的數都是 0 至99 之間的整數。

輸出描述
輸出一個整數，表示答案。

輸入輸出樣例
示例
輸入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸出

30

代碼

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

題解分析

本題使用線性DP解題。

• 設狀態dp[i][j]表示從第i行第j列的元素往下走的所有路徑當中最大的和。
• 狀態轉移方程為dp[i][j] = max(dp[i + 1][i], dp[i +1][j + 1]);
• 因為這里需要用下面的狀態更新上面的，所以我們應該從下往上進行狀態轉移。最后輸出dp[1][1]。

題目十二

原題鏈接：lanqiao3367

題目

問題描述
小藍來到了一座高聳的樓梯前，樓梯共有 N 級臺階，從第 0 級臺階出發。小藍每次可以邁上 1 級或 2 級臺階。但是，樓梯上的第 a 1級第a 2級、第a3級，以此類推，共 M 級臺階的臺階面已經壞了，不能踩上去。現在，小藍想要到達樓梯的頂端，也就是第 N 級臺階，但他不能踩到壞了的臺階上。請問他有多少種不踩壞了的臺階到達頂端的方案數由于方案數很大，請輸出其對 10⁹+7 取模的結果。

輸入格式

第一行包含兩個正整數 N(1≤N≤10 ⁵ ）和 M（0≤M≤N），表示樓梯的總級數和壞了的臺階數。

樣例輸入
6 1
3
樣例輸出
4

代碼

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
const ll p=1e9+7;
ll dp[N];
bool broken[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int x;cin>>x;broken[x]=true;}dp[0]=1;if(!broken[1])dp[1]=1;for(int i=2;i<=n;i++){if(broken[i])continue;dp[i]=(dp[i-1]+dp[i-2])%p;}cout<<dp[n]<<endl;return 0;
}

題解分析

本題使用線性DP解題。

• 設狀態dp[i]表示走到第級合階的方案數。
• 狀態轉移方程為dp[i]] = dp[i- 1] + dp[i-2]，如果為破損的，則dp[i] =0。
• 可以用一個桶來記錄哪些位置是破損的。從前往后更新，最后輸出dp[n]。
• 注意：站在原地也算一種方案，所以dp[0]=1;

題目十三

原題鏈接：lanqiao3423

題目

問題描述
小藍是工廠里的安全工程師，他負責安放工廠里的危險品。

工廠是一條直線，直線上有 n 個空位，小藍需要將若干個油桶放置在 n 個空位上，每 2 個油桶中間至少需要 k 個空位隔開，現在小藍想知道有多少種放置油桶的方案，你可以編寫一個程序幫助他嗎？

由于這個結果很大，你的輸出結果需要對 10⁹+7 取模。

輸入格式
第一行包含兩個正整數 n，k，分別表示 n 個空位與 k 個隔開的空位。

輸出格式
輸出共 1 行，包含 1 個整數，表示放置的方案數對 10⁹+7 取模。

樣例輸入
4 2

樣例輸出
6

說明
用 0 代表不放，1 代表放，6 種情況分別為：

0000，1000，0100，0010，0001，1001。

代碼

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e6+9,p=1e9+7;ll dp[N],prefix[N];int main()
{int n,k;cin>>n>>k;dp[0]=prefix[0]=1;for(int i=1;i<=n;i++){if(i-k-1<1)dp[i]=1;else dp[i]=prefix[i-k-1];prefix[i]=(prefix[i-1]+dp[i])%p;}cout<<prefix[n]<<endl;return 0;
}

題解分析

本題使用線性DP解題。

• 設狀態dp[i]表示以位置結尾的方案總數。狀態轉移方程為dp[i]=dp[j]從j=1到i-k-1的和。

• 注意：直接去求和肯定會超時，所以我們需要利用前綴和來優化時間復雜度。

• 同時，記得取模。

題目十四

原題鏈接：lanqiao2490

題目

問題描述
小藍有一個長度為 n 的括號串，括號串僅由字符 ( 、 ) 構成，請你幫他判斷一下該括號串是否合法，合法請輸出 Yes ，反之輸出 No。

合法括號序列：

• 空串是合法括號序列。

• 若 s 是合法括號序列，則 ( s ) 也是合法括號序列。

• 若 s,t 都是合法括號序列，則 st 也是合法括號序列。

例如 ()() ， (()) ， (())() 均為合法括號序列。

輸入格式
第一行包含一個正整數 n ，表示括號串的長度。

第二行包含一個長度為 n 的括號串。

輸出格式
輸出共 1 行，若括號串合法請輸出 Yes ，反之輸出 No 。

樣例輸入1
10
(()(()))()
樣例輸出1
Yes

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=105;
char stk[N],s[N];
int top;
int main()
{int n;cin>>n;cin>>s+1;for(int i=1;i<=n;i++){if(s[i]==')'){if(top&&stk[top]=='('){top--;continue;}}stk[++top]=s[i];}if(top)cout<<"No"<<endl;else cout<<"Yes";return 0;
}

題解分析

本題使用棧解題。

• 每次將(入棧，當遇到)時檢測棧頂是否可以匹配與其掉，如果不行也入棧，最后檢查棧是否為空。

題目十五

原題鏈接：lanqiao511

題目

題目描述
小晨的電腦上安裝了一個機器翻譯軟件，他經常用這個軟件來翻譯英語文章。

這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應的中文含義來替換。對于每個英文單詞，軟件會先在內存中查找這個單詞的中文含義，如果內存中有，軟件就會用它進行翻譯；如果內存中沒有，軟件就會在外存中的詞典內查找，查出單詞的中文含義然后翻譯，并將這個單詞和譯義放入內存，以備后續的查找和翻譯。

假設內存中有 M 個單元，每單元能存放一個單詞和譯義。每當軟件將一個新單詞存入內存前，如果當前內存中已存入的單詞數不超過 M?1，軟件會將新單詞存入一個未使用的內存單元；若內存中已存入 M 個單詞，軟件會清空最早進入內存的那個單詞，騰出單元來，存放新單詞。

假設一篇英語文章的長度為 N 個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設在翻譯開始前，內存中沒有任何單詞。

輸入描述
輸入共 2 行。每行中兩個數之間用一個空格隔開。

第一行為兩個正整數 M 和 N，代表內存容量和文章的長度。

第二行為 N 個非負整數，按照文章的順序，每個數（大小不超過 1000）代表一個英文單詞。文章中兩個單詞是同一個單詞，當且僅當它們對應的非負整數相同。

其中，0<M≤100，0<N≤1000。

輸出描述
輸出共 1 行，包含一個整數，為軟件需要查詞典的次數。

輸入輸出樣例
示例 1
輸入

3 7
1 2 1 5 4 4 1
輸出

5

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+9;
int q[N],hh=1,tt=0;
int main()
{int m,n;cin>>m>>n;int ans=0;for(int i=1;i<=n;i++){int x;cin>>x;bool tag=false;for(int j=hh;j<=tt;j++)if(q[j]==x)tag=true;if(tag)continue;if(tt-hh+1==m)hh++;q[++tt]=x;ans++;}cout<<ans<<endl;return 0;
}

題解分析

本題使用隊列解題。

• 用一個隊列表示“內存”，每次遇到一個新單詞x，就循環掃描這個隊列，如果里面已經保存過x了就直接跳過，否則判斷內存是否需要釋放并將x入隊。
• hh++表示出隊，q[++tt]=x;表示入隊。

題目十六

原題鏈接：lanqiao3714

題目

問題描述
如果一個數
x 是素數，且 ?x/2? 也是素數，則稱 x 是好數，例如 5,7,11 都是好數。現在給定你一個正整數 n，有 q 組查詢，每組查詢給出一個區間 [l,r]，1≤l≤r≤n，詢問該區間內有多少個好數。

素數：如果一個數的約數只有 1 和本身，則為素數。

輸入格式
第一行二個整數 n,q，表示區間上界和查詢數。接下來 q 行，每行一對[l,r] 表示查詢的區間。

輸出格式
對于每次查詢，輸出區間好數的數量。

樣例輸入
20 3
1 9
7 20
11 17
樣例輸出
2
2
1

代碼

#include <bits/stdc++.h>
using namespace std;
using  ll=long long;
const int N=1e6+9;
bool vis[N];
ll prefix[N];
void euler(ll n){vector<ll>primes;vis[0]=vis[1]=true;for(ll i=2;i<=n;i++){if(!vis[i])primes.push_back(i);for(ll j=0;j<primes.size()&&i*primes[j]<=n;j++){vis[i*primes[j]]=true;if(i%primes[j]==0)break;}}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n,q;cin>>n>>q;euler(n);for(int i=1;i<=n;i++){prefix[i]=prefix[i-1]+(int)(!vis[i]&&!vis[i/2]);}while(q--){int l,r;cin>>l>>r;cout<<prefix[r]-prefix[l-1]<<endl;}return 0;
}

題解分析

本題使用歐拉篩法解題。

• 先用歐拉篩法篩除[1，n]的所有質數，再通過對于每個數字0(1)判斷是否是“好數”，再對判斷結果進行前綴和，每次0(1)回答詢問。總時間復雜度為0(n+g)。
• 使用前綴和可以防止超時。

題目十七

原題鏈接：lanqiao1140

題目

最小質因子之和(Hard Version)

題目描述
定義 F(i) 表示整數 i 的最小質因子。現給定一個正整數 N，請你求出 ∑2nF(i) 。

輸入描述
第 1 行為一個整數 T，表示測試數據數量。

接下來的 T 行每行包含一個正整數 N1≤T≤10 6 ，2≤N≤2×10 ⁷ 。

輸出描述
輸出共 T 行，每行包含一個整數，表示答案。

輸入輸出樣例
示例 1
輸入

3
5
10
15
輸出

12
28
59

代碼

#include <bits/stdc++.h>
using namespace std;
using  ll=long long;
const int N=2e7+9;
bool vis[N];
ll prefix[N];
ll minp[N];
void euler(ll n){vector<ll>primes;vis[0]=vis[1]=true;for(ll i=2;i<=n;i++){if(!vis[i])primes.push_back(i),minp[i]=i;for(ll j=0;j<primes.size()&&i*primes[j]<=n;j++){vis[i*primes[j]]=true;minp[i*primes[j]]=primes[j];if(i%primes[j]==0)break;}}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll q;cin>>q;euler(2e7+9);for(int i=1;i<=2e7+9;i++){prefix[i]=prefix[i-1]+minp[i];}while(q--){ll k;cin>>k;cout<<prefix[k]<<endl;}return 0;
}

題解分析

本題仍然使用歐拉篩法解題。

• 與上題大致一樣，改變一些條件即可。

題目十八

原題鏈接：lanqiao1142

題目

題目描述
這天小明買彩票中了百億獎金，興奮的他決定買下藍橋公司旁的一排連續的樓房。

已知這排樓房一共有 N 棟，編號分別為 1～N，第 i 棟的高度為 h i。

好奇的小明想知道對于每棟樓，左邊第一個比它高的樓房是哪個，右邊第一個比它高的樓房是哪個（若不存在則輸出 ?1）。但由于樓房數量太多，小明無法用肉眼直接得到答案，于是他花了 1 個億來請你幫他解決問題，你不會拒絕的對吧？

輸入描述
第 1 行輸入一個整數 N，表示樓房的數量。

第 2 行輸入 N 個整數（相鄰整數用空格隔開），分別為 h1h2,…,hN，表示樓房的高度。1≤N≤7×10 1≤hi≤10⁹ 。

輸出描述
輸出共兩行。

第一行輸出 N 個整數，表示每棟樓左邊第一棟比自己高的樓的編號。

第二行輸出 N 個整數，表示每棟樓右邊第一棟比自己高的樓的編號。

輸入輸出樣例
示例 1
輸入

5
3 1 2 5 4

輸出

-1 1 1 -1 4
4 3 4 -1 -1

運行限制

• 最大運行時間：2s
• 最大運行內存: 256M

代碼

#include <bits/stdc++.h>
using namespace std;const int N=7e5+9;
int a[N],dpl[N],dpr[N];
int stk[N],top;int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){while(top&&a[stk[top]]<=a[i])top--;dpl[i]=top?stk[top]:-1;stk[++top]=i;}top=0;for(int i=n;i>=1;i--){while(top&&a[stk[top]]<=a[i])top--;dpr[i]=top?stk[top]:-1;stk[++top]=i;}for(int i=1;i<=n;i++)cout<<dpl[i]<<' ';cout<<endl;for(int i=1;i<=n;i++)cout<<dpr[i]<<' ';return 0;
}

題解分析

本題依照題意使用單調棧解題即可。

題目十九

原題鏈接：lanqiao3707

題目

問題描述
小藍去蛋糕店買蛋糕了，蛋糕店有 n 個蛋糕擺在一排，每個蛋糕都有一個高度 h[i]。小藍想買 k 個蛋糕，但是小藍有強迫癥，他只買符合以下要求的蛋糕：

買的 k 個蛋糕必須連續擺放在一起。k 個蛋糕中的最大值與最小值之差要小于等于 x。
現在小藍想知道，他任選 k 個連續擺放的蛋糕，恰好符合他要求的概率是多少。

由于精度問題，你的輸出需要對 998244353 取模。

輸入格式
第一行輸入三個整數 n,k,x，為題目所表述的含義。

第二行輸入
n 個整數，表示每個蛋糕的高度。

輸出格式
輸出一個整數，表示小藍愿意買的概率對 998244353 取模的結果。

令M=998244353 ，可以證明所求概率可以寫成既約分數 p/q的形式，其中 p,q 均為整數且 q≡?0(modM)q\≡0(mod M)。輸出的整數當是 p×q?1(modM)p×q ?1 (mod M) 。

樣例輸入
4 3 2
1 4 6 6

樣例輸出
499122177

說明
根據題意一共有兩組連續 k 個蛋糕，分別是 1 4 6,4 6 6。
4 6 6 是小藍想買的蛋糕，因此概率為1/ 2，對 998244353 取模的結果為 499122177。

評測數據規模
3≤n≤10⁵,2≤k≤n,1≤h[i]≤10⁹,1≤x≤10⁹ 。

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+9,p=998244353;
ll a[N],q[N],mi[N],ma[N];
ll qmi(ll a,ll b)
{ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p,b>>=1;}return res;
}
ll inv(ll x)
{return qmi(x,p-2);}
int main()
{ll n,k,x;cin>>n>>k>>x;for(ll i=1;i<=n;i++)cin>>a[i];ll hh=1,tt=0;for(ll i=1;i<=n;i++){while(hh<=tt&&q[hh]<i-k+1)hh++;while(hh<=tt&&a[q[tt]]>a[i])tt--;q[++tt]=i;mi[i]=a[q[hh]];}hh=1,tt=0;for(ll i=1;i<=n;i++){while(hh<=tt&&q[hh]<i-k+1)hh++;while(hh<=tt&&a[q[tt]]<a[i])tt--;q[++tt]=i;ma[i]=a[q[hh]];}int ans=0;for(int i=k;i<=n;i++)if(ma[i]-mi[i]<=x)ans++;cout<<ans*inv(n-k+1)%p<<endl;return 0;
}

題解分析

本題使用單調隊列并結合逆元解題。

• 用單調隊列分別處理出固定長度區問的最大值和最小值，然后用遍歷區間[k, n]，計算有多少個區間的最值之差<=X，總區間個數為n -k+ 1, 再結合逆元計算即可。

  ---

題目二十

原題鏈接：lanqiao2047

題目

題目描述:
小 Z 同學每天都喜歡斤斤計較，今天他又跟字符串杠起來了。

他看到了兩個字符串 S1 S2 ，他想知道 S1 在 S2 中出現了多少次。

現在給出兩個串 S1，S2(只有大寫字母)，求 S1 在 S2 中出現了多少次。

輸入描述
共輸入兩行，第一行為 S1，第二行為 S2。

1<len(s1)<len(s2)<10⁶

，字符只為大寫字母或小寫字母。

輸出描述
輸出一個整數，表示 S1 在 S2 中出現了多少次。

輸入輸出樣例
示例1
輸入

LQYK
LQYK

輸出

1

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N],p[N];int nex[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>p+1;int m=strlen(p+1);cin>>s+1;int n=strlen(s+1);nex[0]=nex[1]=0;for(int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1]) j=nex[j];if(p[i]==p[j+1]) j++;nex[i]=j;}int ans=0;for(int i=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1]) j=nex[j];if(s[i]==p[j+1]) j++;if(j==m) ans++;}
cout<<ans<<endl;
return 0;
}

題解分析

本題使用KMP模板解題即可。

---