蓝桥杯刷题周计划（第二周）

前言

大家好！我是 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模板解题即可。

---