企业官网建设流程全解析

网站运营方案 网站建设,苏州网站推广如何,专项培训网站建设方案,网站怎样绕过360认证问题描述 给定一个山脉的二维剖面#xff0c;由 NNN 个点组成#xff0c;每个点有一个海拔高度 HiH_iHi​ #xff08;单位#xff1a;厘米#xff09;。 我们需要找出所有 Ultras\texttt{Ultras}Ultras 山峰#xff0c;即那些地形突出度#xff08;topographic promine…问题描述给定一个山脉的二维剖面由NNN个点组成每个点有一个海拔高度HiH_iHi​单位厘米。 我们需要找出所有Ultras\texttt{Ultras}Ultras山峰即那些地形突出度topographic prominence\texttt{topographic prominence}topographic prominence大于等于150000150000150000厘米的山峰。地形突出度的定义对于海拔为hhh的山峰ppp其突出度定义为最大的ddd使得从ppp到任意更高山峰的任何路径都必须经过一个海拔为h−dh-dh−d的点。 如果没有更高的山峰则突出度就是hhh本身。输入格式第一行整数NNN3≤N≤1053 \leq N \leq 10^53≤N≤105表示点数。第二行NNN个整数HiH_iHi​0≤Hi≤1060 \leq H_i \leq 10^60≤Hi​≤106表示按顺序排列的各点海拔。相邻点海拔不同Hi≠Hi1H_i \neq H_{i1}Hi​Hi1​。第一个和最后一个点在海平面H1HN0H_1 H_N 0H1​HN​0。保证至少有一个Ultra\texttt{Ultra}Ultra。输出格式输出所有Ultras\texttt{Ultras}Ultras的索引按出现顺序 从111开始编号。题目分析这个问题本质上是计算每个山峰的地形突出度然后筛选出满足条件的山峰。 关键在于如何高效地计算突出度。突出度计算的核心对于位置iii的山峰海拔H[i]H[i]H[i]向左寻找找到左边第一个严格更高的山峰位置LLL。 在区间(L,i)(L, i)(L,i)中找到最低海拔点记为leftMinleftMinleftMin。 如果左边没有更高山峰则leftMin0leftMin 0leftMin0可以下降到海平面。向右寻找找到右边第一个严格更高的山峰位置RRR。 在区间(i,R)(i, R)(i,R)中找到最低海拔点记为rightMinrightMinrightMin。 如果右边没有更高山峰则rightMin0rightMin 0rightMin0。计算突出度如果左右都没有更高山峰即LLL和RRR都不存在则突出度prominenceH[i]prominence H[i]prominenceH[i]。否则突出度prominenceH[i]−max⁡(leftMin,rightMin)prominence H[i] - \max(leftMin, rightMin)prominenceH[i]−max(leftMin,rightMin)。判断 $\texttt{Ultra}如果prominence≥150000prominence \geq 150000prominence≥150000则iii是Ultra\texttt{Ultra}Ultra。算法设计要点寻找左右第一个更高山峰可以使用单调栈。 从左到右扫描维护一个单调递减栈严格来说是非递增但要注意是“严格更高”所以弹出条件是H[栈顶]≤H[i]H[栈顶] \leq H[i]H[栈顶]≤H[i]。同理从右到左扫描得到右边第一个更高山峰。查询区间最小值需要快速查询任意区间[l,r)[l, r)[l,r)的最小海拔值。由于NNN最大为10510^5105不能使用O(n2)O(n^2)O(n2)的暴力方法。可以使用RMQRange Minimum Query\texttt{RMQRange Minimum Query}RMQRange Minimum Query预处理实现O(1)O(1)O(1)查询。这里采用稀疏表Sparse Table\texttt{Sparse Table}Sparse Table实现RMQ\texttt{RMQ}RMQ预处理O(nlog⁡n)O(n \log n)O(nlogn)查询O(1)O(1)O(1)。边界处理第一个和最后一个点是海平面高度000不计入山峰。注意“严格更高”意味着海拔必须大于当前山峰相等不算。当左右都没有更高山峰时突出度等于自身高度。算法步骤读入数据。使用单调栈计算每个位置左边第一个更高山峰的位置leftHigher[i]leftHigher[i]leftHigher[i]和右边第一个更高山峰的位置rightHigher[i]rightHigher[i]rightHigher[i]。构建稀疏表用于快速查询任意区间的最小海拔值。遍历每个位置iii从111到N−2N-2N−2排除首尾海平面点查询leftMinleftMinleftMin如果leftHigher[i]≠−1leftHigher[i] \neq -1leftHigher[i]−1查询区间(leftHigher[i],i)(leftHigher[i], i)(leftHigher[i],i)的最小值否则leftMin0leftMin 0leftMin0。查询rightMinrightMinrightMin如果rightHigher[i]≠NrightHigher[i] \neq NrightHigher[i]N查询区间(i,rightHigher[i])(i, rightHigher[i])(i,rightHigher[i])的最小值否则rightMin0rightMin 0rightMin0。计算突出度。如果突出度≥150000\geq 150000≥150000记录索引。输出结果。复杂度分析单调栈扫描O(N)O(N)O(N)稀疏表构建O(Nlog⁡N)O(N \log N)O(NlogN)查询与遍历O(N)O(N)O(N)总复杂度O(Nlog⁡N)O(N \log N)O(NlogN)可以处理N≤105N \leq 10^5N≤105的数据规模。代码实现// Go up the Ultras// UVa ID: 12674// Verdict: Accepted// Submission Date: 2025-12-24// UVa Run Time: 0.100s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cinn){vectorinth(n);for(inti0;in;i)cinh[i];// 左边第一个严格更高的位置vectorintleftHigher(n,-1);stackintst;for(inti0;in;i){while(!st.empty()h[st.top()]h[i])st.pop();if(!st.empty())leftHigher[i]st.top();st.push(i);}// 右边第一个严格更高的位置while(!st.empty())st.pop();vectorintrightHigher(n,n);for(intin-1;i0;i--){while(!st.empty()h[st.top()]h[i])st.pop();if(!st.empty())rightHigher[i]st.top();st.push(i);}// 构建稀疏表RMQ用于快速查询区间最小值intlogn1;while((1logn)n)logn;vectorvectorintminTable(logn,vectorint(n));for(inti0;in;i)minTable[0][i]h[i];for(intk1;klogn;k)for(inti0;i(1k)n;i)minTable[k][i]min(minTable[k-1][i],minTable[k-1][i(1(k-1))]);// 区间最小值查询函数autorangeMin[](intl,intr){if(lr)returnINT_MAX;intk31-__builtin_clz(r-l);returnmin(minTable[k][l],minTable[k][r-(1k)]);};// 计算每个山峰的突出度并找出 Ultrasvectorintultras;for(inti1;in-1;i){intleftMin0;if(leftHigher[i]!-1)leftMinrangeMin(leftHigher[i]1,i);intrightMin0;if(rightHigher[i]!n)rightMinrangeMin(i1,rightHigher[i]);intprominence;if(leftHigher[i]-1rightHigher[i]n)prominenceh[i];elseprominenceh[i]-max(leftMin,rightMin);if(prominence150000)ultras.push_back(i1);}// 输出结果if(!ultras.empty()){coutultras[0];for(size_t i1;iultras.size();i)cout ultras[i];}cout\n;}return0;}总结本题的关键在于理解地形突出度的定义并将其转化为可计算的算法。 通过单调栈快速找到每个山峰左右第一个更高山峰再结合RMQ\texttt{RMQ}RMQ快速查询区间最小值即可高效计算出每个山峰的突出度。 算法复杂度O(Nlog⁡N)O(N \log N)O(NlogN)完全满足题目要求。需要注意的细节包括“严格更高”意味着海拔必须大于不能等于。当没有更高山峰时突出度等于自身高度。海平面点高度000不计入山峰。区间查询时注意边界处理。这个问题的解法综合运用了单调栈和稀疏表两种数据结构是一道很好的练习题目。