"蔚来杯"2022牛客暑期多校训练营6 赛后总结

比赛成绩

AC：5

RANK：168

试题订正

A.Array

难度：medium

虽然是道构造题，但考场确实没想到构造方案，于是枚举+强优化硬生生卡过了（80ms）。

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pa;
const int MAXN=1e5+5;
pa a[MAXN];
int c[MAXN],pre[MAXN],nxt[MAXN];
void unlock(int j)
{
    int pr=pre[j],nx=nxt[j];
    nxt[pr]=nx,pre[nx]=pr;
}
int main()
{
    int n,m;
    cin>>n;
    m=1e5;
    for(int i=1;i<=n;++i) scanf("%d",&a[i].first),a[i].second=i;
    sort(a+1,a+n+1);
    for(int i=0;i<=m+1;++i) pre[i]=i-1,nxt[i]=i+1;
    for(int i=1;i<=n;++i)
    {
        int first=0,fa=0;
        for(int j=nxt[0];j<=m;j=nxt[j])
        {
            if(!first)
            {
                first=fa=j;
                c[j]=a[i].second;
                unlock(j);
                if(j+a[i].first>m) break;
                continue;
            }
            if(nxt[j]-fa>a[i].first)
            {
                fa=j;
                c[j]=a[i].second;
                unlock(j);
                if(j+a[i].first>m) break;
            }
        }
        if(first+m-fa<=a[i].first) continue;
        for(int j=pre[m+1];j>fa;j=pre[j])
        {
            if(first+m-pre[j]>a[i].first)
            {
                c[j]=a[i].second;
                unlock(j);
                break;
            }
        }
    }
    int tmp=0;
    for(int i=nxt[0];i<=m;i=nxt[i])
    {
        c[i]=a[++tmp].second;
        if(tmp==n) tmp=0;
    }
    cout<<m<<endl;
    for(int i=1;i<=m;++i) 
        printf("%d ",c[i]);
    return 0;
}

B.Eezie and Pie

难度：medium-easy

这个树剖应该不难想吧，线段树的话维护区间和（）

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pa;
const int MAXN=1e5+5;
pa a[MAXN];
int c[MAXN],pre[MAXN],nxt[MAXN];
void unlock(int j)
{
    int pr=pre[j],nx=nxt[j];
    nxt[pr]=nx,pre[nx]=pr;
}
int main()
{
    int n,m;
    cin>>n;
    m=1e5;
    for(int i=1;i<=n;++i) scanf("%d",&a[i].first),a[i].second=i;
    sort(a+1,a+n+1);
    for(int i=0;i<=m+1;++i) pre[i]=i-1,nxt[i]=i+1;
    for(int i=1;i<=n;++i)
    {
        int first=0,fa=0;
        for(int j=nxt[0];j<=m;j=nxt[j])
        {
            if(!first)
            {
                first=fa=j;
                c[j]=a[i].second;
                unlock(j);
                if(j+a[i].first>m) break;
                continue;
            }
            if(nxt[j]-fa>a[i].first)
            {
                fa=j;
                c[j]=a[i].second;
                unlock(j);
                if(j+a[i].first>m) break;
            }
        }
        if(first+m-fa<=a[i].first) continue;
        for(int j=pre[m+1];j>fa;j=pre[j])
        {
            if(first+m-pre[j]>a[i].first)
            {
                c[j]=a[i].second;
                unlock(j);
                break;
            }
        }
    }
    int tmp=0;
    for(int i=nxt[0];i<=m;i=nxt[i])
    {
        c[i]=a[++tmp].second;
        if(tmp==n) tmp=0;
    }
    cout<<m<<endl;
    for(int i=1;i<=m;++i) 
        printf("%d ",c[i]);
    return 0;
}