7.31错题总结

wangyichenawm · 2025-08-02 16:55:42 · 个人记录

T3(B3667 求区间所有后缀最大值的位置)

考试思路：单调模板题

考试代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005],m;
deque<int>q;
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&q.front()+m<=i)
            q.pop_front();
        while(!q.empty()&&a[q.back()]<=a[i])
            q.pop_back();
        q.push_back(i);
        if(i>=m)
            cout<<q.size()<<'\n';
    }
    return 0;
}

错误原因：第二个while循环不用刷掉和a[i]相同的

正确思路：还是单调模板题

正确代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005],m;
deque<int>q;
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&q.front()+m<=i)
            q.pop_front();
        while(!q.empty()&&a[q.back()]<a[i])
            q.pop_back();
        q.push_back(i);
        if(i>=m)
            cout<<q.size()<<'\n';
    }
    return 0;
}

T6(P2564 [SCOI2009] 生日礼物)

考试思路：二分查找

考试代码：

  #include<bits/stdc++.h>
#define int long long
using namespace std;
struct N
{
    int id,wz;
}a[1000005];
int n,k,ans;
map<int,int>mp;
bool cmp(N x,N y)
{
    return x.wz<y.wz;
}
bool check(int x)
{
    mp.clear();
    int sum=0;
    for(int i=1;i<x;i++)
    {
        mp[a[i].wz]++;
        if(mp[a[i].wz]==1)
            sum++;
    }
    for(int i=x;i<=n;i++)
    {
        mp[a[i].wz]++;
        if(mp[a[i].wz]==1)
            sum++;
        if(i!=x)
        {
            mp[a[i-x].wz]--;
            if(mp[a[i-x].wz]==0)
                sum--;
        }
        if(sum==k)
        {
            ans=min(ans,x);
            return 1;
        }
    }
    return 0;
}
deque<int>q;
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        int x;
        cin>>x;
        for(int j=1;j<=x;j++)
        {
            int z;
            cin>>z;
            a[++ans].id=x;
            a[ans].wz=z;
        }
    }
    sort(a+1,a+n+1,cmp);
    ans=1e9;
    int l=1-1,r=n+1;
    while(l+1<r)
    {
        int mid=(l+r)/2;
        if(check(mid)==1)
            r=mid;
        else
            l=mid;
    }
    cout<<ans;
    return 0;
}

错误原因：时间爆炸了

正确思路：不二分了，直接模拟单调队列

正确代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N
{
    int id,wz;
}a[1000005];
bool cmp(N x,N y)
{
    return x.wz<y.wz;
}
map<int,int>mp;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k,l=1,mn=INT_MAX,cnt=0,sum=0;
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        int x;
        cin>>x;
        for(int j=1;j<=x;j++)
        {
            int y;
            cin>>y;
            a[++cnt]={i,y};
        }
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        mp[a[i].id]++;
        if(mp[a[i].id]==1)
            sum++;
        while(i!=l&&mp[a[l].id]>1)
        {
            mp[a[l].id]--;
            l++;
        }
        if(sum==k)
            mn=min(a[i].wz-a[l].wz,mn);
    }
    cout<<mn<<'\n';
    return 0;
}