2022 ICPC南京 B

84 阅读 0 评论 56 点赞

我是靠谱客的博主迅速火龙果，最近开发中收集的这篇文章主要介绍2022 ICPC南京 B，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一眼前缀DP+后缀DP，中间枚举之后用某种数据结构处理出来区间最值

然后选择了复杂度多了个log并常数非常大的线段树，写起来很麻烦，但debug时间不是很长，好在还是卡过去了

不知道是gym的机子太垃，还是我实现的太垃，但总之是过了

以下放置两个代码，一个我的，一个dls的

请越过我的答辩，欣赏dls的简洁的高手做法

下面是我的答辩

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll init_val=1e18;
const int N=5e5+10;
struct segment
{
    struct Node
    {
        int l,r; ll val;
        bool is_dot(){return l==r;}
        int mid(){return l+r>>1;}
        bool in(int L,int R){return (L<=l)&&(r<=R);}
    }tr[N<<2];
    void build(int u,int l,int r)
    {
        tr[u]={l,r,init_val};
        if(l==r)return ;
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    }
    void pushup(int u)
    {
        if(tr[u].is_dot())return ;
        tr[u].val=min(tr[u<<1].val,tr[u<<1|1].val);
    }
    ll query(int u,int l,int r)
    {
        Node &rt=tr[u];
        if(rt.in(l,r)){return tr[u].val;}
        int mid=rt.mid();
        ll rs=init_val;
        if(l<=mid)rs=min(rs,query(u<<1,l,r));
        if(r>mid)rs=min(rs,query(u<<1|1,l,r));
        return rs;
    }
    void update(int u,int pos,ll val)
    {
        Node &rt=tr[u];
        if(rt.is_dot()){rt.val=val;return ;}
        int mid=rt.mid();
        if(pos<=mid)update(u<<1,pos,val);
        else update(u<<1|1,pos,val);
        pushup(u);
    }
}pr_seg,sf_seg;
ll pr_dp[N],sf_dp[N];
int a[N],pr[N],sf[N];
ll f[N][22],g[N][22];
char str[N];
int lg[N];
ll query2(int l,int r) {
	int p=lg[r-l+1];
	return min(g[l][p],g[r-(1<<p)+1][p]);
}
ll calc(int l,int r,int p,int n,int k)
{
    ll rs=1e18;
    for(int i=r;i>=l;--i)
    {
        if(sf[i]-i<=k){rs=min(pr_dp[i]+sf_dp[sf[i]],rs);}
        else if(p+1<=min(i+k,n))
        rs=min(pr_dp[i]+query2(p+1,min(i+k,n)),rs);

        if(str[i]=='1')break;
    }
    return rs;
}
void solve()
{
    int n,k;scanf("%d%d",&n,&k);
    n+=2;
    for(int i=2;i<n;++i)scanf("%d",&a[i]);
    a[1]=a[n]=0;
    scanf("%s",str+2);str[1]=str[n]='1';str[n+1]=0;
    // pre_DP
    pr[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(str[i-1]=='1')pr[i]=i-1;
        else pr[i]=pr[i-1];
    }
    pr_seg.build(1,1,n);
    pr_seg.update(1,1,0);
    pr_dp[1]=0;
    for(int i=2;i<=n;++i)
    {
        if(i-pr[i]<=k)
        {
            pr_dp[i]=pr_dp[pr[i]]+a[i];
        }
        else 
        {
            int l=max(i-k,1);
            pr_dp[i]=pr_seg.query(1,l,i-1)+a[i];
        }
        pr_seg.update(1,i,pr_dp[i]);
    }
    
    //suf_DP
    sf[n]=n;
    for(int i=n-1;i;--i)
    {
        if(str[i+1]=='1')sf[i]=i+1;
        else sf[i]=sf[i+1];
    }
    sf_seg.build(1,1,n);
    sf_dp[n]=0;sf_seg.update(1,n,0);
    for(int i=n-1;i;--i)
    {
        if(sf[i]-i<=k)
        {
            sf_dp[i]=sf_dp[sf[i]]+a[i];
        }
        else
        {
            int r=min(n,i+k);
            sf_dp[i]=a[i]+sf_seg.query(1,i+1,r);
        }
        sf_seg.update(1,i,sf_dp[i]);
    }
    //st表
    // init st
    for(int i=1;i<=n;++i)f[i][0]=pr_dp[i]; 
    
    for(int j=1;j<=20;++j)
   for(int i=1;i+(1<<j)-1<=n;++i)
    f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
    
    for(int i=1;i<=n;++i)g[i][0]=sf_dp[i];
    
    for(int j=1;j<=20;++j)
    for(int i=1;i+(1<<j)-1<=n;++i)
    g[i][j]=min(g[i][j-1],g[i+(1<<j-1)][j-1]);
    int q;scanf("%d",&q);
    while(q--)
    {
        int p,v;scanf("%d%d",&p,&v);++p;
        if(str[p]=='1'){printf("%lldn",pr_dp[n]+v-a[p]);continue;}
        ll rs=v;
        if(p-pr[p]<=k)rs+=pr_dp[pr[p]];
        else 
        {
            rs+=pr_seg.query(1,p-k,p-1);
        }
        if(sf[p]-p<=k)rs+=sf_dp[sf[p]];
        else 
        {
            rs+=sf_seg.query(1,p+1,p+k);
        }
        printf("%lldn",min(calc(max(1,p-k+1),p-1,p,n,k),rs));
    }
}
int main()
{
    lg[0]=-1;
	for(int i=1;i<N;i++)lg[i]=lg[i/2]+1;
    int T;scanf("%d",&T);
    while(T--)solve();
}

以下是dls的优秀做法

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=501000;
ll dp[N],dpr[N],tmp[N];
char s[N];
int n,k,a[N],q[N];
void solve() {
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%s",s+1);
	int h=0,t=-1;
	dp[0]=0;
	q[++t]=0;
	a[0]=a[n+1]=0;
	rep(i,1,n+2) {
		while (h<=t&&i-q[h]>k) ++h;
		dp[i]=a[i]+dp[q[h]];
		if (s[i]=='1') while (h<=t) ++h;
		while (h<=t&&dp[i]<dp[q[t]]) --t;
		q[++t]=i;
		//printf("%d %lldn",i,dp[i]);
	}
	dpr[n+1]=0;
	h=0; t=-1; q[++t]=n+1;
	per(i,0,n+1) {
		while (h<=t&&q[h]-i>k) ++h;
		dpr[i]=a[i]+dpr[q[h]];
		if (s[i]=='1') while (h<=t) ++h;
		while (h<=t&&dpr[i]<dpr[q[t]]) --t;
		q[++t]=i;
		//printf("val %d %lldn",i,dpr[i]);
		//rep(c,h,t+1) printf("%d ",q[c]); puts("");
	}
	int Q;
	scanf("%d",&Q);
	rep(_,0,Q) {
		int p,v;
		scanf("%d%d",&p,&v);
		int L=max(p-k,0);
		h=0; t=-1;
		rep(j,L,p) {
			tmp[j]=dp[j];
			if (s[j]=='1') while (h<=t) ++h;
			while (h<=t&&tmp[j]<tmp[q[t]]) --t;
			q[++t]=j;
		}
		int R=min(p+k,n+1);
		ll ans=1ll<<60;
		rep(j,p,R+1) {
		while (h<=t&&j-q[h]>k) ++h;
			tmp[j]=(j==p?v:a[j])+tmp[q[h]];
			ans=min(ans,tmp[j]+dpr[j]-a[j]);
			if (s[j]=='1') while (h<=t) ++h;
			while (h<=t&&tmp[j]<tmp[q[t]]) --t;
			q[++t]=j;
		}
		printf("%lldn",ans);
	}
}

int _;
int main() {
	for (scanf("%d",&_);_;_--) {
		solve();
	}
}