邢台网站改版制作公司小时seo百度关键词点击器

邢台网站改版制作公司,小时seo百度关键词点击器,优化方案数学必修二答案,现在学网站开发1.单调栈 1. 什么是单调栈#xff1f; 单调栈#xff0c;顾名思义#xff0c;就是具有单调性的栈。它依旧是⼀个栈结构#xff0c;只不过⾥⾯存储的数据是递增或者 递减的。这种结构是很容易实现的#xff08;如下⾯的代码#xff09;#xff0c;但重点是维护⼀个单调…1.单调栈1.什么是单调栈单调栈顾名思义就是具有单调性的栈。它依旧是⼀个栈结构只不过⾥⾯存储的数据是递增或者 递减的。这种结构是很容易实现的如下⾯的代码但重点是维护⼀个单调栈的意义是什么#include iostream #include stack using namespace std; const int N 3e6 10; int a[N], n; // 单调递增栈 void test1() { stackint st; for (int i 1; i n; i) { while (st.size() st.top() a[i]) st.pop(); st.push(a[i]); } // 输出栈内元素递增 cout 单调递增栈结果; while (!st.empty()) { cout st.top() ; st.pop(); } cout endl; } // 单调递减栈 void test2() { stackint st; for (int i 1; i n; i) { while (st.size() st.top() a[i]) st.pop(); st.push(a[i]); } // 输出栈内元素递减 cout 单调递减栈结果; while (!st.empty()) { cout st.top() ; st.pop(); } cout endl; } int main() { // 测试用例n5数组a[3,1,4,2,5] n 5; a[1] 3; a[2] 1; a[3] 4; a[4] 2; a[5] 5; test1(); // 递增栈结果1 2 5 test2(); // 递减栈结果5 4 3 return 0; }2.单调栈解决的问题单调栈能帮助我们解决以下四个问题• 寻找当前元素左侧离它最近并且⽐它⼤的元素在哪• 寻找当前元素左侧离它最近并且⽐它⼩的元素在哪• 寻找当前元素右侧离它最近并且⽐它⼤的元素在哪• 寻找当前元素右侧离它最近并且⽐它⼩的元素在哪。虽然是四个问题但是原理是⼀致的。因此只要解决⼀个举⼀反三就可以解决剩下的⼏个。3.寻找当前元素左侧离它最近并且⽐它⼤的元素在哪从左往右遍历元素构造⼀个单调递减的栈。插⼊当前位置的元素的时• 如果栈为空则左侧不存在⽐当前元素⼤的元素• 如果栈⾮空插⼊当前位置元素时的栈顶元素就是所找的元素。注意因为我们要找的是最终结果的位置。因此栈⾥⾯存的是每个元素的下标。#include iostream #include stack using namespace std; const int N 3e6 10; int a[N], n; int ret[N]; void test() { stackint st; // 单调递增栈存储下标 for (int i 1; i n; i) ret[i] 0; // 逆序遍历找右侧第一个更小的元素 for (int i n; i 1; i--) { // 弹出栈中≥当前值的下标 while (st.size() a[st.top()] a[i]) { st.pop(); } // 栈非空右侧第一个更小元素的值 if (st.size()) { ret[i] a[st.top()]; } st.push(i); } for (int i 1; i n; i) { cout ret[i] ; } cout endl; } int main() { cin n; for (int i 1; i n; i) { cin a[i]; } test(); return 0; }4.寻找当前元素左侧离它最近并且⽐它⼩的元素在哪从左往右遍历元素构造⼀个单调递增的栈。插⼊当前位置的元素的时• 如果栈为空则左侧不存在⽐当前元素⼩的元素• 如果栈⾮空插⼊当前位置元素时的栈顶元素就是所找的元素。注意因为我们要找的是最终结果的位置。因此栈⾥⾯存的是每个元素的下标。#include iostream // 输入输出头文件用来输入数字、输出结果 #include stack // 栈的头文件用来使用“栈”这个工具 using namespace std; // 定义数组最大长度3e610表示足够装下大量数字不用改 const int N 3e6 10; int a[N], n; // a[N]装输入的数字n装数字的总个数 int ret[N]; // ret[N]装最终结果每个数左边最近更小的数的下标 void test() { // 定义一个栈栈里存的是数字的“下标”抽屉编号维护单调递增的栈 stackint st; // 从第1个数字到第n个数字逐个处理 for(int i 1; i n; i) { // 核心逻辑把栈里≥当前数字的下标都弹出保证栈是递增的 // st.size()判断栈里有没有东西a[st.top()]栈顶下标对应的数字 while(st.size() a[st.top()] a[i]) { st.pop(); // 弹出栈顶扔掉不符合的下标 } // 如果栈里还有东西栈顶就是“左边最近更小的数的下标” if(st.size()) { ret[i] st.top(); } else { ret[i] 0; // 栈空没找到填0 } // 把当前数字的下标放进栈里维护栈的递增性 st.push(i); } // 输出结果从第1个到第n个逐个打印ret里的数 for(int i 1; i n; i) { cout ret[i] ; } cout endl; } int main() { // 第一步输入数字的总个数测试用例里是9 cin n; // 第二步输入n个数字依次放进a[1]到a[n]抽屉1到抽屉n for(int i 1; i n; i) { cin a[i]; } // 第三步执行找“左边最近更小数下标”的逻辑 test(); return 0; }5.寻找当前元素右侧离它最近并且⽐它⼤的元素在哪从右往左遍历元素构造⼀个单调递减的栈。插⼊当前位置的元素的时• 如果栈为空则左侧不存在⽐当前元素⼤的元素• 如果栈⾮空插⼊当前位置元素时的栈顶元素就是所找的元素。注意因为我们要找的是最终结果的位置。因此栈⾥⾯存的是每个元素的下标。#include iostream // 输入输出工具能输入数字、输出结果 #include stack // 栈工具用来找“右侧最近更大的数” using namespace std; const int N 3e6 10; // 准备足够多的“抽屉”不用改够装数字就行 int a[N], n; // a抽屉装输入的9个数字n记数字的总个数比如9 int ret[N]; // ret抽屉装最终结果每个数的答案 void test() { stackint st; // 拿出空的“栈盒子”维护单调递减只存下标 // 核心从最后一个数往第一个数遍历右→左 for(int i n; i 1; i--) { // 第一步把栈里≤当前数的下标都扔掉保证栈是递减的 // st.size()盒子里有东西吗a[st.top()]栈顶下标对应的数字 while(st.size() a[st.top()] a[i]) { st.pop(); // 扔掉不符合的下标 } // 第二步填结果 if(st.size()) { ret[i] st.top(); // 栈非空→栈顶是“右侧最近更大数的下标” } else { ret[i] 0; // 栈空→没找到填0 } // 第三步把当前数的下标放进栈里 st.push(i); } // 输出结果从第1个到第9个逐个打印ret抽屉里的数 for(int i 1; i n; i) { cout ret[i] ; } cout endl; } int main() { cin n; // 输入9告诉程序有9个数 // 把1、4、10、6、3、3、15、21、8依次放进a[1]~a[9] for(int i 1; i n; i) { cin a[i]; } test(); // 执行找“右侧最近更大数下标”的逻辑 return 0; }6.寻找当前元素右侧离它最近并且⽐它⼩的元素在哪从右往左遍历元素构造⼀个单调递增的栈。插⼊当前位置的元素的时• 如果栈为空则左侧不存在⽐当前元素⼩的元素• 如果栈⾮空插⼊当前位置元素时的栈顶元素就是所找的元素。注意因为我们要找的是最终结果的位置。因此栈⾥⾯存的是每个元素的下标。#include iostream // 输入输出工具输入数字、输出结果 #include stack // 栈工具找右侧最近更小的数 using namespace std; const int N 3e6 10; // 足够多的“抽屉”装数字和结果 int a[N], n; // a装输入的数字n数字总个数 int ret[N]; // ret装最终结果每个数的答案 void test() { stackint st; // 空栈维护单调递增只存下标 // 从最后一个数往第一个数遍历右→左 for(int i n; i 1; i--) { // 核心弹出栈里≥当前数的下标保证栈递增 // st.size()栈里有东西吗a[st.top()]栈顶下标对应的数字 while(st.size() a[st.top()] a[i]) { st.pop(); // 扔掉不符合的下标 } // 填结果栈非空找到答案栈空填0 if(st.size()) { ret[i] st.top(); } else { ret[i] 0; // 补充初始化避免随机值 } // 把当前数的下标放进栈维护递增性 st.push(i); } // 输出结果从第一个数到最后一个数打印 for(int i 1; i n; i) { cout ret[i] ; } cout endl; } int main() { cin n; // 输入数字个数比如9 // 把数字依次放进a[1]~a[n] for(int i 1; i n; i) { cin a[i]; } test(); // 执行找数逻辑 return 0; }总结• 找左侧正遍历找右侧逆遍历• ⽐它⼤单调减⽐它⼩单调增。1.1【模板】单调栈题⽬来源 洛⾕题⽬链接P5788 【模板】单调栈难度系数 ★★题目背景模板题无背景。2019.12.12 更新数据放宽时限现在不再卡常了。题目描述给出项数为 n 的整数数列 a1…n​。定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai​ 的元素的下标即 f(i)minij≤n,aj​ai​​{j}。若不存在则 f(i)0。试求出 f(1…n)。输入格式第一行一个正整数 n。第二行 n 个正整数 a1…n​。输出格式一行 n 个整数表示 f(1),f(2),…,f(n) 的值。输入输出样例输入 #1复制5 1 4 2 3 5输出 #1复制2 5 4 5 0说明/提示【数据规模与约定】对于 30% 的数据n≤100对于 60% 的数据n≤5×103 对于 100% 的数据1≤n≤3×1061≤ai​≤109。【解法】右侧离它最近并且⽐它⼤的元素• 逆序遍历数组• 构造⼀个单调递减的栈• 进栈时栈顶元素就是最终结果。【参考代码】#include iostream // 输入输出工具输入数字、输出结果 #include stack // 栈工具找右侧第一个更大的数 using namespace std; const int N 3e6 10; // 足够多的“抽屉”装数字和结果适配3e6的大数据 int n; // 数列的长度比如示例里的5 int a[N]; // a抽屉装输入的数列a[1]1, a[2]4... int ret[N]; // ret抽屉装每个数的答案右边第一个更大数的下标没找到填0 int main() { // 第一步输入数列长度和数列本身 cin n; for(int i 1; i n; i) { cin a[i]; // 把数字依次放进a[1]到a[n] } stackint st; // 空栈维护单调递减只存“下标”抽屉号 // 第二步逆序遍历从最后一个数到第一个数 for(int i n; i 1; i--) { // 核心弹出栈里≤当前数的下标保证栈是递减的 // st.size()栈里有东西吗a[st.top()]栈顶下标对应的数字 while(st.size() a[st.top()] a[i]) { st.pop(); // 扔掉不符合的下标 } // 第三步填答案 if(st.size()) { ret[i] st.top(); // 栈非空→栈顶是“右边第一个更大数的下标” } else { ret[i] 0; // 栈空→没找到填0 } // 第四步把当前数的下标放进栈维护递减性 st.push(i); } // 第五步输出结果如果要输出“值”把ret[i]改成a[ret[i]]即可 for(int i 1; i n; i) { // 示例输出是下标所以输出ret[i]若要输出值改成cout a[ret[i]] ; cout ret[i] ; } cout endl; return 0; }1.2发射站题⽬来源 洛⾕题⽬链接P1901 发射站难度系数 ★★题目描述某地有 N 个能量发射站排成一行每个发射站 i 都有不相同的高度 Hi​并能向两边两端的发射站只能向一边同时发射能量值为 Vi​ 的能量发出的能量只被两边最近的且比它高的发射站接收。显然每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受。请计算出接收最多能量的发射站接收的能量是多少。输入格式第 1 行一个整数 N。第 2 到 N1 行第 i1 行有两个整数 Hi​ 和 Vi​表示第 i 个发射站的高度和发射的能量值。输出格式输出仅一行表示接收最多能量的发射站接收到的能量值。答案不超过 32 位带符号整数的表示范围。输入输出样例输入 #1复制3 4 2 3 5 6 10输出 #1复制7说明/提示对于 40% 的数据1≤N≤5000,1≤Hi​≤105,1≤Vi​≤104。对于 70% 的数据1≤N≤105,1≤Hi​≤2×109,1≤Vi​≤104。对于 100% 的数据1≤N≤106,1≤Hi​≤2×109,1≤Vi​≤104。【解法】有了单调栈之后这道题就变成模拟题了......【参考代码】#include iostream // 输入输出工具输入发射站信息、输出结果 #include stack // 栈工具找“最近更高的站” using namespace std; typedef long long LL; // 防止能量值太大溢出比如多个能量相加超过int范围 const int N 1e6 10; // 足够多的“抽屉”装1e6个发射站的信息 int n; // 发射站的总数比如示例里的3 LL h[N], v[N]; // h装每个站的高度v装每个站的能量值 LL sum[N]; // sum装每个站接收的总能量初始都是0 int main() { // 第一步输入发射站数量和每个站的高度、能量 cin n; for(int i 1; i n; i) { cin h[i] v[i]; // 站1的h4、v2站2的h3、v5站3的h6、v10 } // 第二步找每个站“左边最近更高的站”并把能量加给这个站 stackint st; // 空栈维护单调递减只存站的下标 for(int i 1; i n; i) { // 从左到右遍历每个站 // 核心弹出栈里≤当前站高度的下标保证栈是递减的 while(st.size() h[st.top()] h[i]) { st.pop(); } // 栈非空栈顶就是“左边最近更高的站”接收当前站的能量 if(st.size()) { sum[st.top()] v[i]; // 比如站2的左边更高是站1sum[1] 5 } // 把当前站的下标放进栈维护递减性 st.push(i); } // 第三步找每个站“右边最近更高的站”并把能量加给这个站 while(st.size()) st.pop(); // 清空之前的栈 for(int i n; i 1; i--) { // 从右到左遍历每个站 // 核心弹出栈里≤当前站高度的下标保证栈是递减的 while(st.size() h[st.top()] h[i]) { st.pop(); } // 栈非空栈顶就是“右边最近更高的站”接收当前站的能量 if(st.size()) { sum[st.top()] v[i]; // 比如站1的右边更高是站3sum[3] 2 } // 把当前站的下标放进栈维护递减性 st.push(i); } // 第四步找接收能量最多的站 LL ret 0; // 存最大能量值初始0 for(int i 1; i n; i) { ret max(ret, sum[i]); // 逐个比较保留最大的 } cout ret endl; // 输出7示例 return 0; }