"7-31晚 单调栈和单调队列"总结

ren_gao_zu · 2025-07-31 21:35:37 · 个人记录

考试情况

错题总结（不含T8、T9）

T3:

死因：不开unsigned long long 见祖宗

错误片段：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int N=1e6+5;
using namespace std;

正确：

#include<bits/stdc++.h>
#define int unsigned long long
#define endl '\n'
const int N=1e6+5;
using namespace std;

为什么别人不开unsigned long long得25分，我不开unsigned long long得0分!!!

正确代码：

单调队列模版,唯一的就是要开unsigned long long

#include<bits/stdc++.h>
#define int unsigned long long
#define endl '\n'
const int N=1e6+5;
using namespace std;
int n,m,a[1000005],mi[1000005];
deque<int>q;
void solve();
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
solve();
return 0;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<m;i++){
while(q.size()&&a[q.back()]<=a[i])q.pop_back();
q.push_back(i);
}
for(int i=m;i<=n;i++){
while(q.size()&&a[q.back()]<=a[i]){
q.pop_back();
}
if(i>m){
if(q.size()&&q.front()==i-m)q.pop_front();
}
q.push_back(i);
cout<<q.size()<<endl;

}

}

## T4:
### 死因：只正着跑了一遍，但还要清空再倒着跑一遍
##### 错误片段：

```cpp
    for(int i=1;i<=n;i++){
        while(st.size()&&a[st.top()]>=a[i])ans+=i-st.top()+1,st.pop();
        if(st.size())ans+=st.top()-i+1;
        st.push(i);
    }
    ...
    ...
    cout<<ans*2;

正确：

    for(int i=n;i>=1;i--){
        while(st.size()&&a[i]>=a[st.top()])st.pop();
        if(st.size())ans+=st.top()-i+1;
        st.push(i);
    }
    while(st.size())st.pop();
    for(int i=1;i<=n;i++){
        while(st.size()&&a[i]>a[st.top()])st.pop();
        if(st.size())ans+=i-st.top()+1;
        st.push(i);
    }
    cout<<ans;

正确代码：

就是单调栈，但正向跑完一遍还要清空栈并反向跑一遍(先正先反都可以)

还要注意：ans加的距离不要搞错了，加错了ans加的有可能是负数。(不能加abs)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005],ans;
stack<int>st;
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i>=1;i--){
while(st.size()&&a[i]>=a[st.top()])st.pop();
if(st.size())ans+=st.top()-i+1;
st.push(i);
}
while(st.size())st.pop();
for(int i=1;i<=n;i++){
while(st.size()&&a[i]>a[st.top()])st.pop();
if(st.size())ans+=i-st.top()+1;
st.push(i);
}
cout<<ans;
return 0;
}

T5：

死因：理解错误

错误片段：

for(int i=1;i<=n;i++){
while(st1.size()&&a[st1.top()]>a[i])st1.pop(),ans++;
if(st1.size()&&a[i]!=a[st1.top()])st1.push(i);
if(i==1)st1.push(i);
}

我当时是怎么想的，怎么会写出这种东西

正确：

for(int i=1;i<=n;i++){
        while(st1.size()&&a[st1.top()]>a[i])st1.pop(),ans++;
        if(st1.size()&&a[i]==a[st1.top()])continue;
        st1.push(i);
    }

正确代码

首先，宽度没有任何作用，如果想要海报数最少，至少这堵墙可以用一张海报贴完，不可能一堵墙用两三张海报，所以宽度没用

然后维护一个单调递增的栈，如果遇到栈顶小于a[i]，就将栈顶出栈，并ans++。如果栈顶和a[i]高度相等，这两个可以合并成一堵墙，宽度为a[i]和st.top()的宽度之和，但宽度没用，所以实际上如果a[st.top()]==a[i],a[i]是不用进栈的。

最后直接输出ans+st.size()即可

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int N=1e6+5;
using namespace std;
int n,a[N],ans;
stack<int>st1;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int ffff;
cin>>ffff>>a[i];
}
for(int i=1;i<=n;i++){
while(st1.size()&&a[st1.top()]>a[i])st1.pop(),ans++;
if(st1.size()&&a[i]==a[st1.top()])continue;
st1.push(i);
}
cout<<ans+st1.size();
return 0;
}

T6:

死因：can't do it(不会做)

错误片段：

不要看了，随机数(果然不能相信随机数)

正确代码

首先把所有数据存到一个结构体数组s[]里，并按位置从小到大排序。

然后遍历s数组，用一个num数组存每一种珍珠在队列里的数量，cnt存在队列里的颜色数量。每次将进队的珍珠的颜色加1，如果这个珍珠颜色原来没有，cnt++。若颜色数量大于等于种类数，即cnt>=k，就把队首出队，如果出队的这个珍珠的颜色数量变成0了，cnt--。

minn代表彩带的最短长度，彩带长度为队尾位置-队首位置。若果minn大于彩带长度，更新minn。

最后输出minn。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int N=1e6+5;
using namespace std;
int n,k,tot,num[N],minn=1e18,cnt;
struct node{
int pos,id;
}s[N];
bool cmp(node x,node y){
return x.pos<y.pos;
}
deque<int>q;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=k;i++){
int t;
cin>>t;
while(t--){
int x;
cin>>x;
tot++;
s[tot].pos=x;
s[tot].id=i;
}
}
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++){
q.push_back(i);
int id=s[i].id;
if(num[id]==0)cnt++;
num[id]++;
while(q.size()&&cnt>=k){
int j=q.front();
q.pop_front();
int id=s[j].id;
num[id]--;
if(num[id]==0){
cnt--;
minn=min(minn,s[i].pos-s[j].pos);
}
}

}cout<<minn;
return 0;

}

## T7:
### 死因：似乎忘记怎么写了
##### 错误片段：
几乎全错
### 正确代码：
>这题有一个问题：任意两个人之间的人可以等于这两个人的较小值，导致之前的代码无法通过。
>
>我们可以定义一个结构体node，用来存储高度和数量。输入数组s和栈都是node类型。
>
>遍历数组s，如果s[i].h大于等于栈顶的高度，sum加上栈顶的数量，如果s[i].h等于栈顶的高度s[i]的数量加上栈顶的数量，然后把栈顶出栈。如果栈里面还有元素，sum++。最后将s[i]压入栈。
>
>最后输出sum。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000005];
struct node{
    int h,num;
}s[100005];
stack<node>st;
int n;
int sum;
signed main()
{

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i].h;
        s[i].num=1;
    }

    for(int i=1;i<=n;i++)
    {
        while(st.size()&&s[i].h>=st.top().h)
        {
            sum+=st.top().num;
            if(s[i].h==st.top().h){
                s[i].num+=st.top().num;
            }
            st.pop();

        }
        if(st.size()){
            sum++;
        }
        st.push(s[i]);
    }
    cout<<sum;
    return 0;
}