中山市建设局安全监督站网站东莞南城网站开发公司电话

当前位置： 首页 > news >正文

中山市建设局安全监督站网站,东莞南城网站开发公司电话,企业营销策划合同范本,客户关系管理系统名词解释目录 前言题目一题目代码题解分析 题目二题目代码题解分析 题目三题目代码题解分析 题目四题目代码题解分析 题目五题目代码题解分析 题目六题目代码题解分析 题目七题目代码题解分析 题目八题目题解分析 题目九题目代码题解分析 题目十题目代码题解分析 题目十一题目代码题解分… 目录 前言题目一题目代码题解分析 题目二题目代码题解分析 题目三题目代码题解分析 题目四题目代码题解分析 题目五题目代码题解分析 题目六题目代码题解分析 题目七题目代码题解分析 题目八题目题解分析 题目九题目代码题解分析 题目十题目代码题解分析 题目十一题目代码题解分析 题目十二题目代码题解分析 题目十三题目代码题解分析 题目十四题目代码题解分析 题目十五题目代码题解分析 题目十六题目代码题解分析 题目十七题目代码题解分析 题目十八题目代码题解分析 题目十九题目代码题解分析 题目二十题目代码题解分析 前言 大家好我是 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 lllong long; const int N11; int vis[N][N]; int n,ans0; void dfs(int dep){if(depn1){ans;return;}for(int i1;in;i){if(vis[dep][i])continue;for(int _i1;_in;_i)vis[_i][i];for(int _idep,_ji;_i1_j1;_i–,_j–)vis[_i][_j];for(int _idep,_ji;_in_j1;_i,_j–)vis[_i][_j];for(int _idep,_ji;_i1_jn;–_i,_j)vis[_i][_j];for(int _idep,_ji;_in_jn;_i,_j)vis[_i][_j];dfs(dep1);for(int _i1;_in;_i)vis[_i][i]–;for(int _idep,_ji;_i1_j1;_i–,_j–)vis[_i][_j]–;for(int _idep,_ji;_in_j1;_i,_j–)vis[_i][_j]–;for(int _idep,_ji;_i1_jn;–_i,_j)vis[_i][_j]–;for(int _idep,_ji;_in_jn;_i,_j)vis[_i][_j]–;} } int main() {cinn;dfs(1);coutans;return 0; }题解分析 本题为经典的DFS题使用回溯法可以解决。 首先可以肯定的是每一行必然有且仅有一个皇后因为不可能出现两个皇后在同一行于是就通过枚举每一层皇后的位置来搜索所有可能解即可。每放置一个皇后就将对应的米字型区域设置为“禁区”后面的皇后就不能放在“禁区”回溯的时候将禁区取消掉。同时为了正确维护“禁区”不能使用bool数组来表示禁区需要使用int数组表示这个位置被“多少个皇后占用了”当占用数为0时表示“禁区解除”。层数到n1时表示找到了一个解不可行的解都到不了第n1行 题目二 原题链接lanqiao1260 题目 题目描述 给定两个正整数A,B求它们的最大公约数 输入描述 第 1 行为一个整数 T表示测试数据数量。 接下来的 T 行每行包含两个正整数 A,B。 1≤T≤105 1≤A,B≤109 。 输出描述 输出共 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 b0?a:gcd(b,a%b); } int main() {int t;cint;while(t–){int a,b;cinab;coutgcd(a,b)endl;}return 0; }题解分析 本题考察最大公约数。 通过辗转相除法和三目运算符求最大公约数。 b0?a:gcd(b,a%b);我们知道两数相乘等于两数最大公约数和最小公倍数所以可以通过最大公约数求最小公倍数。return a/gcd(a,b)*b;这里先除再乘是为了减少溢出的发生。 题目三 原题链接lanqiao3205 题目 问题描述 给定一个正整数 n请你计算 1∼n 中有多少对不同的素数满足它们的差也是素数。 输入格式 共一行包含一个正整数 n(2≤n≤105 )。 输出格式 共一行包含一个正整数表示答案。 样例输入 5 样例输出 2 样例输入 20 样例输出 8 代码 #include bits/stdc.h using lllong long; const int N1e510; using namespace std; vectorintprimes; bool vis[N];void init(int n){vis[0]vis[1]true;for(ll i2;in;i){if(!vis[i]){primes.push_back(i);for(int j2*i;jn;ji)vis[j]true;}} } int main() {int n,ans0;cinn;init(n);for(int i0;iprimes.size();i){for(int j0;ji;j){if(!vis[primes[i]-primes[j]])ans;}}coutansendl;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≤105,ai≤109。 代码 #include bits/stdc.h using namespace std; using lllong long; const int N1e510; int main() {int n,x;cinn;mapint ,intmp;while(n–){cinx;mp[x];}int ans0;for(auto pair:mp){int keypair.first;int valuepair.second;if(valuekey)ansvalue-key;else ansvalue;}coutans;return 0; }题解分析 本题使用map容器解题。 代码通过读取整数数量 n 及 n 个整数用 map 统计每个整数出现次数。之后遍历 map 中的键值对键为整数值为该整数出现次数。根据值与键的大小关系计算累加结果若值大于等于键累加差值若值小于键累加值本身。最终输出累加结果。整体时间复杂度为 O(nlogn)。 pair.first是pair的键pair.second是pair的值。 mp[x]表示mp中x对应的值加1。 题目五 原题链接lanqiao1811 题目 题目描述 给定三个正整数 N,M,P求 NMmodp。 输入描述 第 1 行为一个整数 T表示测试数据数量。 接下来的 T行每行包含三个正整数 N,M,P。 1≤T≤105 1≤N,M,P≤109 输出描述 输出共 T 行每行包含一个整数表示答案。 输入输出样例 示例 1 输入 3 2 3 7 4 5 6 5 2 9 输出 1 4 7 代码 #include bits/stdc.h using namespace std; using lllong long;ll qmi(ll a,ll b,ll p){ll res1;while(b){if(b1)resres*a%p;aa*a%p,b1;}return res; }int main() {int t;cint;while(t–){ll n,m,p;cinnmp;coutqmi(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;cins;mapchar,intmp;for(int i0;is.size();i){mp[s[i]];}int ans-1;char c;for(auto pair:mp){char keypair.first;int valuepair.second;if(valueans){ckey;ansvalue;}}coutcendl;coutansendl;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,ja j,i 。同时(1,2,3),(3,2,1) 这种视作同一个三元组且 i≠j,j≠k,i≠kij,jk,i\k。 输入格式 第一行输入一个数字 n表示矩阵大小。(1≤n≤800) 接来下 n 行每行一个长度为 n 的 01 串。 输出格式 输出满足条件的三元组数量。 样例输入 4 0011 0011 1101 1110 样例输出 2 代码 #include bits/stdc.h using namespace std; using lllong long;
int a[2010][2010];
int main() {string s;int n;cinn;for(int i1;in;i){cins;for(int j1;jn;j){a[i][j]s[j-1]-0;}} long long ans0;for(int i1;in;i){for(int ji1;jn;j){for(int kj1;kn;k){if(a[i][j]1a[i][k]1a[j][k]1)ans;}}}coutans;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;cinn;string s,t,e;mapstring,intmp;int i0;while(n–){cins;if(sfind){cint;coutmp[t]endl;}if(sadd){cinet;mp[t];}}return 0; }题解分析 本题使用map容器解题。 分为find和add两种情况讨论。auther为键对应书的数量为值。每一次find输出当前作者的书的数量即可。 题目九 原题链接lanqiao4567 题目 问题描述 小蓝有一个长度为 n 的数组 a 现在对于每一个 ai 小蓝可以选择下面三种操作之一 aiai-1aiaiaiai1 小蓝想知道当她把每一个 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 lllong long; const int N1e510; ll a[N]; int main() {int n;cinn;for(int i1;in;i)cina[i];mapll,llmp;for(int i1;in;i){mp[a[i]];mp[a[i]-1];mp[a[i]1];}ll ans0;for(int i1;in;i){ansmax(ans,mp[a[i]]);}coutans;return 0; }题解分析 本题仍然使用map容器解题。 题中有三种操作可以对应到map容器中的三个键通过枚举数组中的每一个数对其三种情况进行计数。使用max库函数最大众数。 题目十 原题链接lanqiao3272 题目 问题描述 小蓝是一位有名的漆匠他的朋友小桥有一个漆房里面有一条长长的走廊走廊两旁有许多相邻的房子每间房子最初被涂上了一种颜色。 小桥来找小蓝想让他把整个走廊都涂成同一个颜色。小蓝告诉小桥他每天只能涂一段长度为 k 的区间。对于每个区间他可以选择将其中的房子重新涂上任何一种颜色或者保持原来的颜色不变。 小桥想知道小蓝至少要涂几天才能让整个走廊变得美丽。 请帮助小桥解决这个问题。 输入格式 第一行包含一个整数 t(1≤100表示测试用例的数量。 每个测试用例的第一行包含两个整数 n 和 k1≤k≤n≤104 第二行包含 n 个整数 a1,a2,⋯,ana 1 ,a 2 ,⋯,a n 1≤ai≤60分别表示每个房子最初的颜色。 保证所有测试用例中 n 的总和不超过 10 4 。 输出格式 对于每个测试用例输出一个整数表示小蓝需要涂漆的最少天数。 样例输入 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 N1e410; int a[N],b[N]; int main() {int t;cint;int cut;while(t–){int n,k;cinnk;for(int i1;in;i)cina[i];int ans(131)-1;for(int i1;i60;i){int cut0;for(int j1;jn;j){b[j]a[j];}for(int j1;jn;j){if(b[j]!i){for(int hj;hjk-1;h){b[h]i;}cut;jjk-1;}}ansmin(ans,cut);}coutansendl;}return 0; }题解分析 本题核心思路是枚举所有可能的目标值从1到60并对每个目标值模拟操作过程计算所需的操作次数最终取最小值。 枚举目标值遍历所有可能的目标值i1到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 N110; int a[N][N],dp[N][N]; int main() {int n;cinn;for(int i1;in;i){for(int j1;ji;j){cina[i][j];}}for(int in;i1;i–){for(int j1;ji;j){dp[i][j]a[i][j]max(dp[i1][j],dp[i1][j1]);}}coutdp[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 级台阶但他不能踩到坏了的台阶上。请问他有多少种不踩坏了的台阶到达顶端的方案数由于方案数很大请输出其对 1097 取模的结果。 输入格式 第一行包含两个正整数 N(1≤N≤10 5 和 M0≤M≤N表示楼梯的总级数和坏了的台阶数。 样例输入 6 1 3 样例输出 4 代码 #include bits/stdc.h using namespace std; using lllong long; const int N1e59; const ll p1e97; ll dp[N]; bool broken[N];int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,m;cinnm;for(int i1;im;i){int x;cinx;broken[x]true;}dp[0]1;if(!broken[1])dp[1]1;for(int i2;in;i){if(broken[i])continue;dpi%p;}coutdp[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 个空位隔开现在小蓝想知道有多少种放置油桶的方案你可以编写一个程序帮助他吗 由于这个结果很大你的输出结果需要对 1097 取模。 输入格式 第一行包含两个正整数 nk分别表示 n 个空位与 k 个隔开的空位。 输出格式 输出共 1 行包含 1 个整数表示放置的方案数对 1097 取模。 样例输入 4 2 样例输出 6 说明 用 0 代表不放1 代表放6 种情况分别为 000010000100001000011001。 代码 #include bits/stdc.h using namespace std; using lllong long; const ll N1e69,p1e97;ll dp[N],prefix[N];int main() {int n,k;cinnk;dp[0]prefix[0]1;for(int i1;in;i){if(i-k-11)dp[i]1;else dp[i]prefix[i-k-1];prefixi%p;}coutprefix[n]endl;return 0; }题解分析 本题使用线性DP解题。 设状态dp[i]表示以位置结尾的方案总数。状态转移方程为dp[i]dp[j]从j1到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 N105; char stk[N],s[N]; int top; int main() {int n;cinn;cins1;for(int i1;in;i){if(s[i])){if(topstktop{top–;continue;}}stk[top]s[i];}if(top)coutNoendl;else coutYes;return 0; }题解分析 本题使用栈解题。 每次将(入栈当遇到)时检测栈顶是否可以匹配与其掉如果不行也入栈最后检查栈是否为空。 题目十五 原题链接lanqiao511 题目 题目描述 小晨的电脑上安装了一个机器翻译软件他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单它只是从头到尾依次将每个英文单词用对应的中文含义来替换。对于每个英文单词软件会先在内存中查找这个单词的中文含义如果内存中有软件就会用它进行翻译如果内存中没有软件就会在外存中的词典内查找查出单词的中文含义然后翻译并将这个单词和译义放入内存以备后续的查找和翻译。 假设内存中有 M 个单元每单元能存放一个单词和译义。每当软件将一个新单词存入内存前如果当前内存中已存入的单词数不超过 M−1软件会将新单词存入一个未使用的内存单元若内存中已存入 M 个单词软件会清空最早进入内存的那个单词腾出单元来存放新单词。 假设一篇英语文章的长度为 N 个单词。给定这篇待译文章翻译软件需要去外存查找多少次词典假设在翻译开始前内存中没有任何单词。 输入描述 输入共 2 行。每行中两个数之间用一个空格隔开。 第一行为两个正整数 M 和 N代表内存容量和文章的长度。 第二行为 N 个非负整数按照文章的顺序每个数大小不超过 1000代表一个英文单词。文章中两个单词是同一个单词当且仅当它们对应的非负整数相同。 其中0M≤1000N≤1000。 输出描述 输出共 1 行包含一个整数为软件需要查词典的次数。 输入输出样例 示例 1 输入 3 7 1 2 1 5 4 4 1 输出 5 代码 #include bits/stdc.h using namespace std; const int N2e39; int q[N],hh1,tt0; int main() {int m,n;cinmn;int ans0;for(int i1;in;i){int x;cinx;bool tagfalse;for(int jhh;jtt;j)if(q[j]x)tagtrue;if(tag)continue;if(tt-hh1m)hh;q[tt]x;ans;}coutansendl;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 lllong long; const int N1e69; bool vis[N]; ll prefix[N]; void euler(ll n){vectorllprimes;vis[0]vis[1]true;for(ll i2;in;i){if(!vis[i])primes.push_back(i);for(ll j0;jprimes.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;cinnq;euler(n);for(int i1;in;i){prefix[i]prefixi-1(!vis[i]!vis[i/2]);}while(q–){int l,r;cinlr;coutprefix[r]-prefix[l-1]endl;}return 0; }题解分析 本题使用欧拉筛法解题。 先用欧拉筛法筛除[1n]的所有质数再通过对于每个数字0(1)判断是否是“好数”再对判断结果进行前缀和每次0(1)回答询问。总时间复杂度为0(ng)。使用前缀和可以防止超时。 题目十七 原题链接lanqiao1140 题目 最小质因子之和(Hard Version) 题目描述 定义 F(i) 表示整数 i 的最小质因子。现给定一个正整数 N请你求出 ∑2nF(i) 。 输入描述 第 1 行为一个整数 T表示测试数据数量。 接下来的 T 行每行包含一个正整数 N1≤T≤10 6 2≤N≤2×10 7 。 输出描述 输出共 T 行每行包含一个整数表示答案。 输入输出样例 示例 1 输入 3 5 10 15 输出 12 28 59 代码 #include bits/stdc.h using namespace std; using lllong long; const int N2e79; bool vis[N]; ll prefix[N]; ll minp[N]; void euler(ll n){vectorllprimes;vis[0]vis[1]true;for(ll i2;in;i){if(!vis[i])primes.push_back(i),minp[i]i;for(ll j0;jprimes.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;cinq;euler(2e79);for(int i1;i2e79;i){prefix[i]prefix[i-1]minp[i];}while(q–){ll k;cink;coutprefix[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≤109 。 输出描述 输出共两行。 第一行输出 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 N7e59; 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;cinn;for(int i1;in;i)cina[i];for(int i1;in;i){while(topa[stk[top]]a[i])top–;dpl[i]top?stk[top]:-1;stk[top]i;}top0;for(int in;i1;i–){while(topa[stk[top]]a[i])top–;dpr[i]top?stk[top]:-1;stk[top]i;}for(int i1;in;i)coutdpl[i] ;coutendl;for(int i1;in;i)coutdpr[i] ;return 0; }题解分析 本题依照题意使用单调栈解题即可。 题目十九 原题链接lanqiao3707 题目 问题描述 小蓝去蛋糕店买蛋糕了蛋糕店有 n 个蛋糕摆在一排每个蛋糕都有一个高度 h[i]。小蓝想买 k 个蛋糕但是小蓝有强迫症他只买符合以下要求的蛋糕 买的 k 个蛋糕必须连续摆放在一起。k 个蛋糕中的最大值与最小值之差要小于等于 x。 现在小蓝想知道他任选 k 个连续摆放的蛋糕恰好符合他要求的概率是多少。 由于精度问题你的输出需要对 998244353 取模。 输入格式 第一行输入三个整数 n,k,x为题目所表述的含义。 第二行输入 n 个整数表示每个蛋糕的高度。 输出格式 输出一个整数表示小蓝愿意买的概率对 998244353 取模的结果。 令M998244353 可以证明所求概率可以写成既约分数 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≤105,2≤k≤n,1≤h[i]≤109,1≤x≤109 。 代码 #include bits/stdc.h using namespace std; typedef long long ll; const ll N1e59,p998244353; ll a[N],q[N],mi[N],ma[N]; ll qmi(ll a,ll b) {ll res1;while(b){if(b1)resres*a%p;aa*a%p,b1;}return res; } ll inv(ll x) {return qmi(x,p-2);} int main() {ll n,k,x;cinnkx;for(ll i1;in;i)cina[i];ll hh1,tt0;for(ll i1;in;i){while(hhttq[hh]i-k1)hh;while(hhtta[q[tt]]a[i])tt–;q[tt]i;mi[i]a[q[hh]];}hh1,tt0;for(ll i1;in;i){while(hhttq[hh]i-k1)hh;while(hhtta[q[tt]]a[i])tt–;q[tt]i;ma[i]a[q[hh]];}int ans0;for(int ik;in;i)if(ma[i]-mi[i]x)ans;coutans*inv(n-k1)%pendl;return 0; }题解分析 本题使用单调队列并结合逆元解题。 用单调队列分别处理出固定长度区问的最大值和最小值然后用遍历区间[k, n]计算有多少个区间的最值之差X总区间个数为n -k 1, 再结合逆元计算即可。
题目二十 原题链接lanqiao2047 题目 题目描述: 小 Z 同学每天都喜欢斤斤计较今天他又跟字符串杠起来了。 他看到了两个字符串 S1 S2 他想知道 S1 在 S2 中出现了多少次。 现在给出两个串 S1S2(只有大写字母)求 S1 在 S2 中出现了多少次。 输入描述 共输入两行第一行为 S1第二行为 S2。 1len(s1)len(s2)106 字符只为大写字母或小写字母。 输出描述 输出一个整数表示 S1 在 S2 中出现了多少次。 输入输出样例 示例1 输入 LQYK LQYK 输出 1 代码 #includebits/stdc.h using namespace std; const int N1e610; char s[N],p[N];int nex[N];int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinp1;int mstrlen(p1);cins1;int nstrlen(s1);nex[0]nex[1]0;for(int i2,j0;im;i){while(jp[i]!p[j1]) jnex[j];if(p[i]p[j1]) j;nex[i]j;}int ans0;for(int i1,j0;in;i){while(js[i]!p[j1]) jnex[j];if(s[i]p[j1]) j;if(jm) ans;} coutansendl; return 0; }题解分析 本题使用KMP模板解题即可。