前言

大家好！我是 EnigmaCoder。

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

題目一

原題鏈接：lanqiao1508

題目

N皇后問題

題目描述*

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

輸入描述

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

輸出描述

為一個正整數(shù)，表示對應(yīng)輸入行的皇后的不同放置數(shù)量。

輸入輸出樣例

示例 1

輸入

5

輸出

10

運行限制

• 最大運行時間：1s
• 最大運行內(nèi)存: 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;
}

題解分析

本題為經(jīng)典的DFS題，使用回溯法可以解決。

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

---

題目二

原題鏈接：lanqiao1260

題目

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

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

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

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

輸入輸出樣例
示例 1
輸入

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

2
1
5
2
1

運行限制

• 最大運行時間：2s
• 最大運行內(nèi)存: 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;
}

題解分析

本題考察最大公約數(shù)。

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

---

題目三

原題鏈接：lanqiao3205

題目

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

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

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

樣例輸入
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;
}

題解分析

本題使用埃式篩法求素數(shù)。

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

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

• 通過bool類型的數(shù)組來記錄當(dāng)前值是否為素數(shù)，false表示為素數(shù)，true表示不為素數(shù)。

---

題目四

原題鏈接：lanqiao3199

題目

問題描述

小明又新學(xué)了一個概念，叫做完美序列。一個僅包含數(shù)字序列被稱為完美序列，當(dāng)且僅當(dāng)數(shù)字序列中每個數(shù)字出現(xiàn)的次數(shù)等于這個數(shù)字。比如 (1)，(2,2,3,3,3))?？招蛄幸菜恪，F(xiàn)在小明得到了一個數(shù)字序列，他想知道最少要刪除多少個數(shù)字才能使得這個數(shù)字序列成為一個完美序列。

輸入格式

輸入包括兩行。

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

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

輸出格式

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

樣例輸入

6
3 3 3 1 13 15 

樣例輸出

2

評測數(shù)據(jù)規(guī)模

對于所有評測數(shù)據(jù)，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容器解題。

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

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

• mp[x]++表示mp中x對應(yīng)的值加1。

---

題目五

原題鏈接：lanqiao1811

題目

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

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

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

輸出描述

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

輸入輸出樣例
示例 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 函數(shù)實現(xiàn)快速冪取模，其核心思想是將指數(shù)進行二進制拆分，減少乘法運算次數(shù)。
• 在 qmi 函數(shù)中，不斷將底數(shù)平方并對指數(shù)右移，若指數(shù)當(dāng)前位為 1 則累乘底數(shù)到結(jié)果中并取模。主函數(shù)讀取多組輸入數(shù)據(jù)，每組包含底數(shù)、指數(shù)和模數(shù)，調(diào)用 qmi 函數(shù)計算結(jié)果并輸出。
• 時間復(fù)雜度為 O(logm)，空間復(fù)雜度為 O(1)，能高效處理大規(guī)模冪運算取模。

---

題目六

原題鏈接：lanqiao504

題目

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

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

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

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

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

第二行包含一個整數(shù)，表示出現(xiàn)得最多的那個字母在單詞中出現(xiàn)的次數(shù)。

輸入輸出樣例
示例 1
輸入

lanqiao
輸出

a
2
示例 2
輸入

longlonglongistoolong

輸出

o
6

運行限制

• 最大運行時間：1s
• 最大運行內(nèi)存: 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;
}

題解分析

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

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

---

題目七

原題鏈接：lanqiao3186

題目

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

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

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

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

輸出格式
輸出滿足條件的三元組數(shù)量。

樣例輸入
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和矩陣本身，將每個字符轉(zhuǎn)換為0或1并存儲在二維數(shù)組a中。
• 然后通過三層嵌套循環(huán)遍歷所有可能的i、j、k組合（滿足i < j < k），對于每個組合，檢查a[i][j]、a[i][k]和a[j][k]是否都為1，如果是，則將答案ans加1。
• 最后輸出ans的值。

題目八

原題鏈接：lanqiao11097

題目

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

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

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

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

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

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

樣例輸出
0
1
2
1

評測數(shù)據(jù)規(guī)模
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為鍵，對應(yīng)書的數(shù)量為值。每一次find輸出當(dāng)前作者的書的數(shù)量即可。

---

題目九

原題鏈接：lanqiao4567

題目

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

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

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

輸入格式
第一行輸入一個整數(shù)，代表n 。

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

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

樣例輸入
3
1 2 3

樣例輸出
3

說明
對于樣例，將 a1加一，a3 減一，a2 不變，此時三個數(shù)都是2 ，而其他操作得到的結(jié)果眾數(shù)數(shù)目都小于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容器解題。

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

題目十

原題鏈接：lanqiao3272

題目

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

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

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

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

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

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

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

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

樣例輸入
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;
}

題解分析

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

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

題目十一

原題鏈接：lanqiao1536

題目

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

輸入描述

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

輸出描述
輸出一個整數(shù)，表示答案。

輸入輸出樣例
示例
輸入

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解題。

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

題目十二

原題鏈接：lanqiao3367

題目

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

輸入格式

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

樣例輸入
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解題。

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

題目十三

原題鏈接：lanqiao3423

題目

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

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

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

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

輸出格式
輸出共 1 行，包含 1 個整數(shù)，表示放置的方案數(shù)對 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解題。

• 設(shè)狀態(tài)dp[i]表示以位置結(jié)尾的方案總數(shù)。狀態(tài)轉(zhuǎn)移方程為dp[i]=dp[j]從j=1到i-k-1的和。

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

• 同時，記得取模。

題目十四

原題鏈接：lanqiao2490

題目

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

合法括號序列：

• 空串是合法括號序列。

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

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

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

輸入格式
第一行包含一個正整數(shù) 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;
}

題解分析

本題使用棧解題。

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

題目十五

原題鏈接：lanqiao511

題目

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

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

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

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

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

第一行為兩個正整數(shù) M 和 N，代表內(nèi)存容量和文章的長度。

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

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

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

輸入輸出樣例
示例 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;
}

題解分析

本題使用隊列解題。

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

題目十六

原題鏈接：lanqiao3714

題目

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

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

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

輸出格式
對于每次查詢，輸出區(qū)間好數(shù)的數(shù)量。

樣例輸入
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]的所有質(zhì)數(shù)，再通過對于每個數(shù)字0(1)判斷是否是“好數(shù)”，再對判斷結(jié)果進行前綴和，每次0(1)回答詢問?？倳r間復(fù)雜度為0(n+g)。
• 使用前綴和可以防止超時。

題目十七

原題鏈接：lanqiao1140

題目

最小質(zhì)因子之和(Hard Version)

題目描述
定義 F(i) 表示整數(shù) i 的最小質(zhì)因子?，F(xiàn)給定一個正整數(shù) N，請你求出 ∑2nF(i) 。

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

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

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

輸入輸出樣例
示例 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

題目

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

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

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

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

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

輸出描述
輸出共兩行。

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

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

輸入輸出樣例
示例 1
輸入

5
3 1 2 5 4

輸出

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

運行限制

• 最大運行時間：2s
• 最大運行內(nèi)存: 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;
}

題解分析

本題依照題意使用單調(diào)棧解題即可。

題目十九

原題鏈接：lanqiao3707

題目

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

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

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

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

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

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

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

樣例輸入
4 3 2
1 4 6 6

樣例輸出
499122177

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

評測數(shù)據(jù)規(guī)模
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;
}

題解分析

本題使用單調(diào)隊列并結(jié)合逆元解題。

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

  ---

題目二十

原題鏈接：lanqiao2047

題目

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

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

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

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

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

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

輸出描述
輸出一個整數(shù)，表示 S1 在 S2 中出現(xiàn)了多少次。

輸入輸出樣例
示例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模板解題即可。

---