7-26作业/重写ren_gao_zu

ren_gao_zu · 2025-07-27 10:48:05 · 个人记录

作业

U514895 ١١(❛ᴗ❛)【单调栈】-左侧第一个较小值（不重复）

#include<bits/stdc++.h>
#define int  long long
using namespace std;
const int N =1e6+5;
int n;
int a[N],b[N];
stack<int> st;
int to=0;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=0;i<=1e6;i++)
        b[i]=-1;
    for(int i=1;i<=n;i++)
    {
        while(st.size()&&a[i]<=a[st.top()])
        {
            st.pop();
        }
        if(st.size())
        {
            b[i]=st.top();
            //if(b[i]!=-1)

        }
        st.push(i);
    }
    for(int i=2;i<=n;i++)
        to^=b[i];
    if(n>1000)
    {
        cout<<to;
        return 0;
    }
    for(int i=1;i<=n;i++)
        cout<<b[i]<<" ";
    return 0;
}

U514949 ١١(❛ᴗ❛)【单调栈】-左右两侧第一小于值（存在重复情况）

#include<bits/stdc++.h>
#define int  long long
using namespace std;
const int N = 1e6 + 5;
int n;
int a[N],b1[N],b2[N];
stack<int>st1,st2;
int to=0;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=0;i<=1e6;i++)
        b1[i]=-1,b2[i]=-1;
    for(int i=n;i>=1;i--)
    {
        while(st2.size()&&a[i]<=a[st2.top()])
        {
            st2.pop();
        }
        if(st2.size())
        {
            b2[i]=st2.top();
        }
        st2.push(i);
    }
    for(int i=1;i<=n;i++)
    {
        while(st1.size()&&a[i]<=a[st1.top()])
        {
            st1.pop();
        }
        if(st1.size())
        {
            b1[i]=st1.top();

        }
        st1.push(i);
    }

    for(int i=1;i<=n;i++)
        cout<<b1[i]<<" "<<b2[i]<<endl;
    return 0;
}

P1901 发射站

#include<bits/stdc++.h>
#define int  long long
using namespace std;
const int N = 1e6 + 5;
int n;
int a[N],b1[N],b2[N],v[N];
stack<int>st1,st2;
int to=0,tong[N];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>v[i];
    for(int i=0;i<=1e6;i++)
        b1[i]=-1,b2[i]=-1;
    for(int i=n;i>=1;i--)
    {
        while(st2.size()&&a[i]>=a[st2.top()])
        {
            st2.pop();
        }
        if(st2.size())
        {
            b2[i]=st2.top();
        }
        st2.push(i);
    }
    for(int i=1;i<=n;i++)
    {
        while(st1.size()&&a[i]>=a[st1.top()])
        {
            st1.pop();
        }
        if(st1.size())
        {
            b1[i]=st1.top();

        }
        st1.push(i);
    }

    for(int i=1;i<=n;i++)
    {
        if(b1[i]!=-1)
            tong[b1[i]]+=v[i];
        if(b2[i]!=-1)
            tong[b2[i]]+=v[i];
    }
    int maxn=0;
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,tong[i]);
    }
    cout<<maxn;

    return 0;
}

重写

无