网站管理员后台网站建设 朝阳区

网站管理员后台,网站建设 朝阳区,网页设计培训学校,免费友链互换目录 一#xff0c;单调栈 二#xff0c;单调队列 例题一(单调栈#xff09;#xff1a;蓝桥杯官网——百亿富翁 题目描述 输入描述 输出描述 输入输出样例 示例 1 代码详解#xff1a; 解释#xff1a;计算 dpl 时 stk 的工作过程 例题二#xff08;单调队列…目录一单调栈二单调队列例题一(单调栈蓝桥杯官网——百亿富翁题目描述输入描述输出描述输入输出样例示例 1代码详解解释计算 dpl 时 stk 的工作过程例题二单调队列蓝桥杯官网——分蛋糕问题描述输入格式输出格式样例输入样例输出代码详解注本文所有题目均来自蓝桥杯官网公开真题仅做算法学习代码皆由本人做出来并附上解析一单调栈单调栈是一个时刻保证内部元素具有单调性质的栈是一种线性结构。其单调特性使得处理一些问题变得高效例如求某个点左侧或右侧第一个比它大的点的位置类似于lower_bound。单调栈的核心思想是在入栈时逐个删除所有 “更差的点”保持单调性。单调栈一般可分为单调递减栈、单调递增栈、单调不减栈、单调不增栈需要根据题意来确定。同时用数组实现的单调栈会比用 STL 实现的更灵活可以在里面进行二分LIS最长递增子序列Longest Increasing Subsequence 的 O (nlogn) 算法就需要用到单调栈 二分。二单调队列基础定义和单调栈思想类似是基于 “双端队列” 的线性数据结构内部元素保持单调性质。元素存储大多时候队列中存储的是 “下标”而非 “元素值”。核心逻辑队头是 “最优的元素”后面是候选元素入队时会直接删除 “没有价值的元素”。适用场景常用于处理固定长度的区间最值问题。例题一(单调栈蓝桥杯官网——百亿富翁题目描述已知有一排楼房一共有 N 栋编号分别为 1∼N第 ii 栋的高度为 hi​。好奇的小明想知道对于每栋楼左边第一个比它高的楼房是哪个右边第一个比它高的楼房是哪个若不存在则输出 −1。输入描述第 1 行输入一个整数 N表示楼房的数量。第 2 行输入 N 个整数相邻整数用空格隔开分别为 h1​,h2​,...,hN​表示楼房的高度。1≤N≤7×10^51≤hi​≤10^9。输出描述输出共两行。第一行输出 N 个整数表示每栋楼左边第一栋比自己高的楼的编号。第二行输出 N 个整数表示每栋楼右边第一栋比自己高的楼的编号。输入输出样例示例 1输入5 3 1 2 5 4输出-1 1 1 -1 4 4 3 4 -1 -1代码详解#include iostream using namespace std; const int N7e59; int a[N],stk[N],dpl[N],dpr[N],top; /* a[]存入原数组 stk[]存入元素编号模拟一个特殊的栈使得a[stk[1]] a[stk[2]] ... a[stk[top]]核心思想 dpl[i]表示a[i]左边第一个大于a[i]的数的编号没有就是-1 dpr[i]表示a[i]右边第一个大于a[i]的数的编号没有就是-1 */ int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n;cinn; for(int i1;in;i) cina[i]; //遍历左边 for(int i1;in;i) { //注意top的遍历方式是从上往下遍历栈弹出栈顶元素 //从栈顶开始若栈顶对应的a中的元素a[i]就出栈继续遍历栈顶下一个元素 //因为stk栈满足栈底到栈顶所对应的a[i]值依次减小然而stk中存储的又必然是for循环已遍历的元素的下标 //所以要从上往下遍历才能在栈中准确找到第一个大于a[i]的元素的下标对应的就是a[i]左边第一个大于a[i] //的元素下标 while(topa[stk[top]]a[i]) top--;//若top存在就从栈顶往下遍历top-- //看看有没有元素大于a[i],直到top0说明遍历所有都没有或找到了大于a[i]的数 dpl[i]top?stk[top]:-1;//若top不为0说明在栈中有下标元素对应的a[]值大于a[i], //则输出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] ; cout\n; for(int i1;in;i) coutdpr[i] ; return 0; }解释计算 dpl 时 stk 的工作过程dpl[i] 表示a[i] 左边第一个比它大的元素的下标遍历方向是从左到右i1 到 i5。初始状态top0栈为空stk 中没有元素。第一步i1a[1]3栈为空top0无需弹出元素。dpl[1] -1左边没有元素。将 i1 入栈stk[1]1top1。此时栈中元素下标[1]对应 a 的值[3]单调递减。第二步i2a[2]1检查栈顶a[stk[1]] a[1] 33 1不满足「小于等于」所以不弹出。dpl[2] stk[1] 1左边第一个更大元素是下标 1。将 i2 入栈stk[2]2top2。此时栈中元素[1, 2]对应 a 的值[3, 1]仍然单调递减。第三步i3a[3]4检查栈顶a[stk[2]] a[2] 11 4 --弹出top1。再检查栈顶a[stk[1]] a[1] 33 4 --弹出top0。栈为空dpl[3] -1左边没有更大元素。将 i3 入栈stk[1]3top1。此时栈中元素[3]对应 a 的值[4]单调递减。第四步i4a[4]2检查栈顶a[stk[1]] a[3] 44 2 -- 不弹出。dpl[4] stk[1] 3左边第一个更大元素是下标 3。将 i4 入栈stk[2]4top2。此时栈中元素[3, 4]对应 a 的值[4, 2]单调递减。第五步i5a[5]5检查栈顶a[stk[2]] a[4] 22 5 -- 弹出top1。再检查栈顶a[stk[1]] a[3] 44 5 -- 弹出top0。栈为空dpl[5] -1。将 i5 入栈stk[1]5top1。此时栈中元素[5]对应 a 的值[5]单调递减。例题二单调队列蓝桥杯官网——分蛋糕问题描述小蓝去蛋糕店蛋糕店有 n 个蛋糕摆在一排每个蛋糕都有一个高度 h[i]。小蓝想买 k 个蛋糕但他只买符合以下要求的蛋糕买的 k 个蛋糕必须连续摆放在一起。k 个蛋糕中的最大值与最小值之差要小于等于 x。现在小蓝想知道他任选 k 个连续摆放的蛋糕恰好符合他要求的概率是多少。由于精度问题你的输出需要对 998244353 取模。输入格式第一行输入三个整数 n,k,x为题目所表述的含义。第二行输入 n 个整数表示每个蛋糕的高度。输出格式输出一个整数表示小蓝愿意买的概率对 998244353 取模的结果。样例输入4 3 2 1 4 6 6样例输出499122177代码详解#include iostream using namespace std; using lllong long; const int N1e59; ll a[N],q[N],mi[N],mx[N]; const ll p998244353; /*给定数组 a长度 n、窗口长度 k、阈值 x 求所有长度为 k 的滑动窗口的最小值存入 mi 数组和最大值存入 mx 数组 统计满足 mx[i] - mi[i] ≤ x 的窗口数量 cnt 计算 cnt / (n-k1) 的值模 998244353除法通过逆元实现并输出。 */ //为什么需要逆元 //模运算中没有直接的除法cnt / (n-k1) mod p 等价于 cnt * inv(n-k1) mod pinv 是乘法逆元 //费马小定理若 p 是质数且 x 与 p 互质则 x^(p-1) ≡ 1 mod p → x^(p-2) ≡ x^(-1) mod p即逆元。 ll qmi(ll a,ll b) { ll res1;//永远不要忘记res初始化为1 while(b) { if(b1) resres*a%p; aa*a%p,b1; } return res; } ll inv(ll x)//这里要返回ll { return qmi(x,p-2); } int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n,k,x;cinnkx; for(int i1;in;i) cina[i]; //开始队列操作 int hh1,tt0; //求固定区间的最小值mi[i] // mi[i] 表示以i为 窗口右端点 的长度为k的窗口的最小值 for(int i1;in;i) { //步骤1弹出队头超出窗口范围的元素维护窗口左边界 //窗口左边界 i - k 1右端点i长度k队头下标 左边界 - 无效弹出 while(hhttq[hh]i-k1) hh; //步骤2弹出队尾比当前元素大的元素维护队列单调递增 //队列内下标对应的值要递增 - 队尾值 a[i] - 队尾元素不可能是当前/后续窗口的最小值直接弹出 while(hhtt a[q[tt]]a[i])tt--; //步骤3当前下标入队队尾 q[tt]i; //步骤4记录当前窗口的最小值队头就是最小值下标 mi[i]a[q[hh]]; } //求固定区间的最大值 hh1,tt0; // 重置队列 // mx[i] 表示以i为窗口右端点的长度为k的窗口的最大值 for(int i1;in;i) { //步骤1弹出队头超出窗口范围的元素和求最小值逻辑一致 while(hhttq[hh]i-k1) hh; //步骤2弹出队尾比当前元素小的元素维护队列单调递减 //队列内下标对应的值要递减 -队尾值 a[i] -队尾元素不可能是当前/后续窗口的最大值直接弹出 while(hhtt a[q[tt]]a[i])tt--; //步骤3当前下标入队 q[tt]i; //步骤4记录当前窗口的最大值队头就是最大值下标 mx[i]a[q[hh]]; } int cnt0; for(int ik;in;i)if(mx[i]-mi[i]x)cnt; coutcnt*inv(n-k1)%p\n; /*总窗口数n-k1比如 n5,k2 → 窗口数 4[1,2],[2,3],[3,4],[4,5] 只有 i≥k 时窗口才是完整的左端点 ≥1因此遍历 i 从 k 到 n 最终结果取模避免溢出且符合算法题的模数要求。*/ return 0; }