专栏文章

P2418 yyy loves OI IV

PPop_Agoni
P2418题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minb1dh6
此快照首次捕获于
2025/12/01 23:29
3 个月前
此快照最后确认于
2025/12/01 23:29
3 个月前
查看原文

P2418 yyy loves OI IV

前言：

首先想的 DP 是这样的，记 fif_i 表示以 ii 同学为终点的最少的房间数。
很容易写出转移方程式：
fi=fj−1+1f_i=f_{j-1}+1
其中 jj 需要满足区间 [j,i][j,i] 全都只膜拜一个人，或者二者相差小于 mm。

正解：

上述时间复杂度为 O(n2)O(n^2)。
因为没有任何优化。
这个转移方程式十分常见，但是判断是否可以转移的条件略困难。
我们考虑优化。
分情况讨论。
  1. 区间 [j,i][j,i] 全部膜拜一个人。
那么我们只需要计算出对于当前的同学最前的一个膜拜跟他相同的一个同学，记录为 lstlst。
那么 ii 肯定是从 lstlst 转移过来的，在满足条件一的情况下。
  1. 区间 [j,i][j,i] 膜拜的人数相互小于等于 mm
发现只有两种的膜拜情况，又加上要时刻保持二者差值小于等于 mm。
我们可以考虑到将其转换成类似于括号匹配的问题。
我们记 sumi,1sum_{i,1} 表示前 ii 个人里膜拜第一个人的人数。
sumi,2sum_{i,2} 也是如此。
我们就可以写下式子：
−m≤(sumi,2−sumj−1,2)−(sumi,1−sumj−1,1)≤m-m\le (sum_{i,2}-sum_{j-1,2})-(sum_{i,1}-sum_{j-1,1})\le m
{sumi,2−sumj−1,2−sumi,1+sumj−1,1≤msumi,2−sumj−1,2−sumi,1+sumj−1,1≥−m\begin{cases} {sum_{i,2}-sum_{j-1,2}-sum_{i,1}+sum_{j-1,1}\le m} \\ {sum_{i,2}-sum_{j-1,2}-sum_{i,1}+sum_{j-1,1} \ge -m} \end{cases}
我们将下标相同的项放在一起，不同的项放到另一边。
{sumi,2−sumi,1−m≤sumj−1,2−sumj−1,1sumi,2−sumi,1+m≥sumj−1,2−sumj−1,1\begin{cases} {sum_{i,2}-sum_{i,1}-m\le sum_{j-1,2}-sum_{j-1,1}} \\ {sum_{i,2}-sum_{i,1}+m \ge sum_{j-1,2}-sum_{j-1,1}} \end{cases}
对于上面的这么一个条件实际上就是求一个对于 jj 的合法区间。
那么我们将 fjf_j 存在一颗线段树上，下标为 sumi,2−sumi,1sum_{i,2}-sum_{i,1}。
查询更新即可。
记得加上一段区间内所有人膜拜的人都一样的情况。
CPP
#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1) 
using namespace std;
const int N=5e5+5;
int n,m;
int a[N];
int tr[N<<4],sum[N][3],f[N],t,l,r,pos,lstc;
int query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R) return tr[x];
    int mid=(l+r)>>1,mn=1e9;
    if(L<=mid) mn=min(mn,query(ls(x),l,mid,L,R));
    if(R>mid) mn=min(query(rs(x),mid+1,r,L,R),mn);
    return mn;
}
void pushup(int x){tr[x]=min(tr[ls(x)],tr[rs(x)]);}
void build(int x,int l,int r){
    if(l==r){
        tr[x]=n+1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(x),l,mid),build(rs(x),mid+1,r);
    pushup(x);
}
void update(int x,int l,int r,int id,int val){
    if(l==r){
        tr[x]=min(tr[x],val);
        return;
    }
    int mid=(l+r)>>1;
    if(id<=mid) update(ls(x),l,mid,id,val);
    else update(rs(x),mid+1,r,id,val);
    pushup(x);
}
int main(){
    scanf("%d%d",&n,&m);
    build(1,-n,n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i][1]=sum[i-1][1]+(a[i]==1);
        sum[i][2]=sum[i-1][2]+(a[i]==2);
    }
    for(int i=1;i<=n;i++) f[i]=n+1;
    f[0]=0;
    update(1,-n,n,0,0);

    for(int i=1;i<=n;i++){
        t=sum[i][1]-sum[i][2];
        l=-m+t,r=m+t;
        l=max(-n,l),r=min(r,n);
        if(lstc!=a[i]) lstc=a[i],pos=i-1;
        f[i]=min(f[pos],query(1,-n,n,l,r))+1;
        // t=sum[i][2]-sum[i][1];
        update(1,-n,n,t,f[i]);
    }
    printf("%d\n",f[n]);
    return 0;
}
upd：“线段树”打成了“线椴树”，已改。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...