码蹄集部分题目（2024OJ赛16期；单调栈集训+差分集训）

🧀🧀🧀单调栈集训

🥪单调栈

单调递增栈伪代码：

stack<int> st;
for(遍历数组)
{while(栈不为空&&栈顶元素大于当前元素)//单调递减栈就是把后方判断条件变为小于等于即可{栈顶元素出栈;//同时进行其他需要的数据记录}当前数据入栈;
}

推荐这篇：[数据结构]——单调栈-CSDN博客

🥪单调栈vs单调队列

单调栈和单调队列都是用于记录一个单增或单减区间的工具，其主要区别有以下几点：

• 单调栈的数据结构是栈，单调队列的数据结构是队列

• 单调栈是一端操作，单调队列是双端操作

• 单调栈适用于需要寻找左右第一个比当前元素大或小的位置的问题，而单调队列适用于需要在滑动窗口中维护最值的问题

1🐋🐋矩形覆盖（钻石；单调栈）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例

🐚备注

🐟题目思路

这道题目不同于《刷墙》的是，这道题目的矩形大小是任意的。

本题中，建筑物的宽度无用，只需要看高度。

n栋楼最多就需要n张海报，那么怎么减少海报数量，当出现“低高低”并且“低”的两栋建筑一样高的情况时，就可以减少一张海报了。（“高低高”的情况无法减少海报数，因为不能贴出建筑物范围）

所以我们考虑模拟单调栈，当出现上述情况时就可以将ans（可以减少的海报数量）++了。

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
int n,ans,d,w;
stack<int> st;
int main( )
{cin>>n;for(int i=1;i<=n;i++){cin>>d>>w;while(!st.empty()&&w<=st.top())//模拟单调递增栈{if(st.top()==w) ans++;st.pop();//将不满足单调递增的元素pop出来}st.push(w);}cout<<n-ans<<endl;return 0;
}

2🐋🐋多项式变换求值（钻石；单调栈）

时间限制：1秒

占用内存：64M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例

🐚备注

🐟题目思路

题目明确给出将ai换成比ai小的第一个数，根据前边我们对单调栈和单调队列的对比，可以看出，这很明显是单调栈解决的问题。

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
#define ll long long
const int MOD=99887765;
const int N=5e6+10;
stack<int> st;
int n,x,a[N],b[N];//a用来记录所有元素，b用来记录i的后方比i小的第一个元素的大小
ll ans;
int main( )
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>x;for(int i=1;i<=n+1;i++){cin>>a[i];while(!st.empty()&&a[i]<a[st.top()])//单调递增栈{b[st.top()]=a[i];//我就是比要出来的这些元素小的第一个元素，记录st.pop();}st.push(i);}for(int i=1;i<=n+1;i++)//计算{ans=ans*x+b[i];ans=(ans%MOD+MOD)%MOD;//直接取余会出现复数的情况，直接加上MOD取余又会出现超出数据类型范围的情况，所以要这样写}cout<<ans<<endl;return 0;
}

3🐋🐋这项目我小码哥投了（星耀；单调栈）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例

🐚备注

🐟题目思路

这道题目就是求最大的全是G的矩形的大小，然后乘以利润10即可，也就是求最大子矩形面积的问题。

这里，我们将每一行及其上方所有行的一列列1看作类似建筑，然后使用单调栈操作：

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
const int N=1e3+10;
int n,m,a[N][N],ans;
char ch;
​
int maxRec(int x)
{int ret=0;stack<int> st;st.push(0);for(int i=1;i<=m+1;i++){while(a[x][i]<a[x][st.top()])//单调递增栈{//每次需要pop的时候都要计算最大子矩形面积int h=a[x][st.top()];st.pop();int w=i-1-st.top();//以h为高的最大子矩形宽度ret=max(ret,w*h);}st.push(i);}return ret;
}
​
int main( )
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>ch;if(ch=='G') a[i][j]=1;//G标记为1}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]) a[i][j]+=a[i-1][j];//注意，这里不是前缀和，如果某一条的底下(a[i][j])为0了，那么这一列1的数量重置为0}}for(int i=1;i<=n;i++) ans=max(ans,maxRec(i));cout<<ans*10<<endl;return 0;
}

4🐋🐋山脉（钻石；单调栈）

时间限制：1秒

占用内存：64M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例

🐚备注

🐟题目思路

翻译一下题目，就是遍历所有山，找到当前山右边第一个高于或与我同高的山，计算两山之间山的数量，最后将这些山的数量进行累加，很典型的单调栈问题。

使用单调栈就可以在遍历一遍数组的时间内完成任务。

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
#define int long long
int n,num,sum;
stack<int>st;
signed main( )
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);//这两句是用来提高输入输出性能cin>>n;for(int i=1;i<=n;i++){cin>>num;while(!st.empty()&&st.top()<=num) st.pop();//构建单调递减栈sum+=st.size();//如果top元素被pop掉了，这里每次的累加也都记录下来了st.push(num);}cout<<sum<<endl;return 0;
}

🥪C/C++输入输出性能优化

ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

• ios::sync_with_stdio(false);: 默认情况下，C++ 的输入输出流与 C 标准 I/O 是同步的，这意味着它们共享底层的文件描述符。但是，当你使用 C++ 的输入输出流时，可能会导致性能下降，因为每次输入或输出时，都需要同步 C 的标准 I/O。通过设置 sync_with_stdio(false)，你告诉 C++ 不要与 C 的标准 I/O 同步，这样可以提高输入输出的速度。

• cin.tie(0), cout.tie(0);: cin 和 cout 都是 C++ 的标准输入输出流对象。默认情况下，它们是关联的，意味着在使用 cin 进行输入时，cout 的缓冲区会被刷新，这可能会导致性能下降。通过 cin.tie(0) 和 cout.tie(0)，你告诉 C++ 不要在 cin 和 cout 之间建立关联，从而避免缓冲区刷新，提高性能。

🧀🧀🧀差分集训

🥪差分思想

对[l,r]区间，区间中每个数加上m，就变成了：

• b[l]+=m

• b[r+1]-=m

每次更新的只有b数组中l和r+1这两个位置的数

差分算法适用情况：

• 总结而言，就是：序列数据+区间修改/查询

• 序列数据变化较小: 差分算法适用于序列中的变化较小的情况。如果序列中的大部分元素保持不变，只有少数元素发生了变化，差分算法能够高效地捕捉到这些变化，并且可以在较小的存储空间和时间复杂度下进行处理。

• 差分序列具有规律性: 如果序列中的变化具有某种规律性，例如周期性变化、递增或递减变化等，那么差分算法可以更好地捕捉到这种规律，从而简化问题的处理。

• 需要高效地处理增量变化: 在一些场景中，我们只关注序列中的增量变化，而不需要完整的历史数据。差分算法可以帮助我们高效地处理这种增量变化，而不必维护完整的原始数据序列。

• 需要高效地进行序列操作: 差分算法可以用于高效地进行序列操作，例如区间修改、区间查询等操作。通过预处理原始序列并构建差分序列，可以在一定程度上简化问题的处理，并且减少每次操作的时间复杂度。

推荐这篇：差分算法介绍-CSDN博客

5🐋🐋区间修改（黄金；差分）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例

🐚备注

🐟题目思路

对序列数据的区间进行加或减操作，典型的使用差分算法的问题。

工资都相同，也就是说差分数组b全部为0。由于差分变换每次只修改两个数，也就是说，每次变换可以让正负的两个数各减加1，比如[-1,1,1]，经过一次变换就可以变成[0,1,0]。

这道题目就是给出a数组，求sub数组并进行顺带数据处理的。

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
const int N=1e5+10;
int n,a[N],sub[N],num1,num2;
int main( )
{int ans=0;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=2;i<=n;i++){sub[i]=a[i]-a[i-1];//构建差分数组if(sub[i]>0) num1+=sub[i];//所有正的差值else num2+=sub[i];//所有负的差值}//每次操作都可以让一对正负分别减加1，所以大的那个数是需要额外操作的，结果就是大的这个数cout<<max(num1,-num2)<<endl;return 0;
}

6🐋🐋相对马高（黄金；差分）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例

输入：

20 1000 6
5 14
16 20
9 11
17 18
6 7
2 4

输出：

1000
1000
999
1000
1000
999
999
999
999
998
999
999
999
1000
1000
1000
999
999
999
1000

🐚备注

🐟题目思路

最大可能身高，那么就是比我矮的我认为就比我矮1（多次比较自然会出现一匹马比另一匹马矮很多的情况）。

也就是说，对序列数据做减法，区间内的马身高都减一，典型的利用差分算法的问题。

由于是左右区间开端操作，所以1号马的身高一定是最高的那个数，所以将g[0]和g[1]设为h，sub[1]设为0即可。

这道题目就是给出了差分数组sub和a数组的第一个数，求完整的a数组。我们知道，sub的前缀和就是a。

🐟代码

#include<bits/stdc++.h> 
​
using namespace std;
const int N=1e4+10;
int n,h,f,g[N],sub[N],a,b;
int main( )
{cin>>n>>h>>f;sub[1]=h;while(f--){cin>>a>>b;if(a==b||b==a+1) continue;if(a>b) swap(a,b);//这里注意不是对l和r+1操作了，因为是小括号，不是中括号，是左右端开端操作，所以是对l+1和r操作sub[a+1]-=1;sub[b]+=1;//这里不用担心超出最高身高，因为前边已经减过了，累加后就抵消了，所以最多只会出现局部高低差的情况，不会超出最高身高}for(int i=1;i<=n;i++){g[i]=g[i-1]+sub[i];//累加得到结果cout<<g[i]<<endl;}return 0;
}

有问题我们随时评论区见~

⭐点赞收藏不迷路~