NOIP2023游记

· · 个人记录

坐标广东，暂估分 214，估计（肯定）进不了队，不知道能拿几等。

upd:分数200（暴力打挂），压线一等！

第一题很简单，由于字典序是全序，所以用先算出串最小和最大的可能的字典序（我们一般称之为：排序），然后用计排算出排名来，然后随便判断就可以了。

第二题一眼并查集，对每个变量建两个点，分别代表 x_i,\neg x_i，再建三个点分别表示 T,F,U。连边表示相等。如果 x_i 和 \neg x_i 在一个集合里，那么它们都是 U，得再连一下 U。然后算出来 U 所在集合的大小就可以了。

第三题、第四题只打了暴力。。。(听说T3是原，T4是简单的线段树优化DP？？？)

第二题一开始没有特判 i=j 的情况，导致大样例过不了，调了好久。

赛前在看算导和黑书（疯狂安利黑书！）。不过学的全都没考，考了也全都不会就是了

总结：如果没有秒切，也要多给思考的时间

T4题解

T4是DP！！！

使用离散化，于是 n 和 m 同阶。

Part 0

各种指数算法。

Part 1

DP。令 f_i 表示，考虑到 i 的最大收益。

f_{i}=\max_{\max(i-k,0)\le j\le i}(f_{j-1}-(i-j)d+\sum_{j<l_p\le r_p\le i}v_p)

这样我们就得到了 O(n^2m) 的朴素算法。

或者离散化的版本

f_i=\max\{f_{i-1},\max_{ t_i-k+1\le t_j,j\le i}(f_{\max\{k|t_k<t_j-1\}}+\sum_{t_j\le l_p\le r_p\le t_i}v_p-(t_i-t_j+1)d)\}

时间复杂度 O(m^3)

Part 2

用单调队列优化掉那个 \sum ，时间复杂度 O(n^2)。

Part 3

在Part 1的基础上，用线段树实时维护 f 的决策。

观察到决策分为三部分：

然后就没有然后了，区间 \max 更新。

时间复杂度 O(m\log m)。

T4

//调了半天才发现多测没清线段树。
#include<cstdio>
#include<algorithm>
#include<cstring>
const int N=2e5+10;
typedef long long ll;
ll f[N];
struct interval{int l,r,v;}a[N];
bool operator<(const interval &a,const interval &b){return a.r<b.r;}
struct node{ll max,plus;}t[N*4];int m2;
int d;int fm[N];
void pushup(int p){t[p].max=std::max(t[p<<1].max,t[p<<1|1].max);}
void pushdown(int p)
{
    if(t[p].plus)
    {
        t[p<<1].plus+=t[p].plus;
        t[p<<1].max+=t[p].plus;
        t[p<<1|1].plus+=t[p].plus;
        t[p<<1|1].max+=t[p].plus;
        t[p].plus=0;
    }
}
int time[N];
void build(int l=1,int r=m2,int o=1)
{
    t[o].plus=0;
    if(l==r)
    {
        t[o].max=1ll*time[l]*d;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,o<<1);
    build(mid+1,r,o<<1|1);
    pushup(o);
}
void add(const int &L,const int &R,const ll &v,int l=1,int r=m2,int o=1)
{
    if(L<=l&&r<=R){t[o].max+=v;t[o].plus+=v;return;}
    int mid=l+r>>1;
    pushdown(o);
    if(L<=mid) add(L,R,v,l,mid,o<<1);
    if(mid<R) add(L,R,v,mid+1,r,o<<1|1);
    pushup(o);
}
ll max(const int &L,const int &R,int l=1,int r=m2,int o=1)
{
    if(L<=l&&r<=R) return t[o].max;
    int mid=l+r>>1;ll ret=0;
    pushdown(o);
    if(L<=mid) ret=max(L,R,l,mid,o<<1);
    if(mid<R) ret=std::max(ret,max(L,R,mid+1,r,o<<1|1));
    return ret;
}
int main()
{
    freopen("run.in","r",stdin);
    freopen("run.out","w",stdout);
    int c,T;scanf("%d%d",&c,&T);
    while(T--)
    {
        int n,m,k;scanf("%d%d%d%d",&n,&m,&k,&d);
        for(int i=1,y;i<=m;i++)
        {
            scanf("%d%d%d",&a[i].r,&y,&a[i].v),a[i].l=a[i].r-y+1;
            time[i*2-1]=a[i].l;time[i*2]=a[i].r;
        }
        std::sort(time+1,time+m*2+1);
        m2=0;
        for(int i=1;i<=m*2;i++)
        {
            if(i==1||time[i]!=time[i-1])
            time[++m2]=time[i];
        }
        std::sort(a+1,a+m+1);
        memset(f,0,sizeof f);
        memset(fm,0,sizeof fm);
        int j=1;build();
        for(int i=1;i<=m2;i++)
        {
            for(;j<=m&&a[j].r<=time[i];j++) add(1,std::upper_bound(time+1,time+m2+1,a[j].l)-1-time,a[j].v);
            f[i]=std::max(f[i-1],-1ll*(time[i]+1)*d+max(std::lower_bound(time+1,time+m2+1,time[i]-k+1)-time,i));
            if(i==std::upper_bound(time+1,time+m2+1,time[i+1]-2)-1-time&&f[i]>fm[i+1]) add(i+1,i+1,f[i]-fm[i+1]),fm[i+1]=f[i];
            if(i==std::upper_bound(time+1,time+m2+1,time[i+2]-2)-1-time&&f[i]>fm[i+2]) add(i+2,i+2,f[i]-fm[i+2]),fm[i+2]=f[i];
        }
        printf("%lld\n",f[m2]);
    }
}