526互联

Contest 23-04-18

发布时间 2023-04-18 22:56:03作者: 月光幻影

#D.糖果镇

思路

  • \(m=3\)时整个路径有两个拐点,分别是\(m=1 \to m=2,m=2 \to m=3\)

  • 设拐点\(1\)在第\(i\)列,拐点\(2\)在第\(j\)列,则路径上的数字总和为\((front[1][i])+(front[2][j]-front[2][i-1])+(back[j])\)(\(front[i][j]\)表示第i行\(1 \to j\)的前缀和,\(back[j]\)表示第\(3\)行\(j \to n\)的后缀和)

  • 把带有\(i\)和\(j\)的项分开,设\(f[i]=(front[1][i]-front[2][i-1]),g[j]=(front[2][j]+ba[j])\),则\(res=max_{1 \to n}(res,f[i]+g[j])\)

  • 所以只要枚举\(i,j\)就可以

数据点分治

m=1

  • 只能一直往前走,累加即可;
    //m=1
if(m==1){
    ans=0;
    for(int i=1;i<=n;i++) ans=(ans+in[1][i])%p;
    cout<<ans%p<<"\n";
    return 0;
}

m=2

  • 预处理\(f[i],g[i]\),暴力枚举一个拐点即可(两行只有一个拐点)
    //m=2
else if(m==2){
    ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,(front[1][i]+front[2][n]-front[2][i-1])%p);
    cout<<ans%p<<"\n";
    return 0;
}

所有\(a_i\)的和\(<\)模数\(p\)

  • 按照正常DP来做就可以
  • 为什么模数会对结果有影响:
    • 如果\(f[i]+g[j]\)恰好等于\(p+1\)而\(f[x]+g[y]\)等于\(p-1\),那么同时模\(p\)后第一个的结果小于第二个,常规DP得到的却是第一个大于第二个,所以只有在取模对原结果无影响(原结果小于模数)时才能用常规DP
    //sum<p
else if(sum<p){
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+in[i][j];
        }
    }
    cout<<dp[m][n]<<"\n";
    return 0;
}

m=3

  • 按照上面的思路,\(f[i]\)的\(i \le g[j]\)的\(j\),所以要按照一定顺序,把下标大于等于当前\(i\)的\(g[i]\)找出来,和\(f[i]\)区和,求最大值

  • 求\(f[i],g[i]\)的时候一步一取模,使得\(f[i],g[i] \le p-1\),所以\(f[i]+g[j]\)有\(>p\)和\(<p\)两种情况,对于给定的\(f[i]\)

    • \(f[i]+g[j]>p \to g[i]\)属于\([p-f[i],p-1]\)
    • \(f[i]+g[j]<p \to g[i]\)属于\([0,p-1-f[i]]\)

值域线段树

  • 和普通线段树类似,不过改成了动态开点
  • 用值域线段树维护区间\([0,p)\)中各个子区间内\(g[i]\)的最大值
  • 这里按照倒序(正序也可以)往线段树里插入\(g[i]\),再用前文分类讨论的两个区间区\(g[i]\)的最大值与\(f[i]\)想加,取最大值作为结果
    //线段树
struct Node{
    int l,r;
    int lc,rc;
    int maxn;
}t[40*N];
int cnt=1;

void Push_up(int id){
    t[id].maxn=-INF;
    if(t[id].lc) t[id].maxn=max(t[t[id].lc].maxn,t[id].maxn);
    if(t[id].rc) t[id].maxn=max(t[t[id].rc].maxn,t[id].maxn);
}

void Modify(int id,int pos){
    if(t[id].l==t[id].r){
        t[id].maxn=pos;
        return;
    }
    int mid=(t[id].l+t[id].r)/2;
    if(pos<=mid){
        if(!t[id].lc){
            t[id].lc=++cnt;
            t[cnt].l=t[id].l; t[cnt].r=mid;
            t[cnt].lc=0; t[cnt].rc=0;
            t[cnt].maxn=-INF;
        }
        Modify(t[id].lc,pos);
    }
    else{
        if(!t[id].rc){
            t[id].rc=++cnt;
            t[cnt].l=mid+1; t[cnt].r=t[id].r;
            t[cnt].lc=0; t[cnt].rc=0;
            t[cnt].maxn=-INF;
        }
        Modify(t[id].rc,pos);
    }
    Push_up(id);
}

int Query(int id,int l,int r){
    if(l<=t[id].l && t[id].r<=r) return t[id].maxn;
    int mid=(t[id].l+t[id].r)/2;
    int ret=-1;
    if(t[id].lc && l<=mid) ret=max(ret,Query(t[id].lc,l,r));
    if(t[id].rc && r>=mid+1) ret=max(ret,Query(t[id].rc,l,r));
    return ret;
}

    //m=3
ans=0;
for(int i=n;i>=1;i--){
    Modify(1,g[i]);
    int ret;
    ret=Query(1,0,p-1-f[i]);
    if(ret!=-1) ans=max(ans,f[i]+ret);
    ret=Query(1,p-f[i],p-1);
    if(ret!=-1) ans=max(ans,(f[i]+ret)%p);
}
cout<<ans<<"\n";

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e9;
const int N=1e5+10;

struct Node{
    int l,r;
    int lc,rc;
    int maxn;
}t[40*N];
int cnt=1;

void Push_up(int id){
    t[id].maxn=-INF;
    if(t[id].lc) t[id].maxn=max(t[t[id].lc].maxn,t[id].maxn);
    if(t[id].rc) t[id].maxn=max(t[t[id].rc].maxn,t[id].maxn);
}

void Modify(int id,int pos){
    if(t[id].l==t[id].r){
        t[id].maxn=pos;
        return;
    }
    int mid=(t[id].l+t[id].r)/2;
    if(pos<=mid){
        if(!t[id].lc){
            t[id].lc=++cnt;
            t[cnt].l=t[id].l; t[cnt].r=mid;
            t[cnt].lc=0; t[cnt].rc=0;
            t[cnt].maxn=-INF;
        }
        Modify(t[id].lc,pos);
    }
    else{
        if(!t[id].rc){
            t[id].rc=++cnt;
            t[cnt].l=mid+1; t[cnt].r=t[id].r;
            t[cnt].lc=0; t[cnt].rc=0;
            t[cnt].maxn=-INF;
        }
        Modify(t[id].rc,pos);
    }
    Push_up(id);
}

int Query(int id,int l,int r){
    if(l<=t[id].l && t[id].r<=r) return t[id].maxn;
    int mid=(t[id].l+t[id].r)/2;
    int ret=-1;
    if(t[id].lc && l<=mid) ret=max(ret,Query(t[id].lc,l,r));
    if(t[id].rc && r>=mid+1) ret=max(ret,Query(t[id].rc,l,r));
    return ret;
}

int n,m,p;
int ans,sum;
int in[4][N];
int dp[4][N];
int front[3][N],back[N];
int f[N],g[N];

signed main(){
    // freopen("1.in","r",stdin);
    cin>>n>>m>>p;
    t[1].maxn=-INF; t[1].l=0; t[1].r=p; t[1].lc=0; t[1].rc=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>in[i][j];
            sum+=in[i][j];
        }
    }

    for(int i=1;i<=2;i++){
        for(int j=1;j<=n;j++){
            front[i][j]=front[i][j-1]+in[i][j];
        }
    }

    if(m==1){
        ans=0;
        for(int i=1;i<=n;i++) ans=(ans+in[1][i])%p;
        cout<<ans%p<<"\n";
        return 0;
    }else if(m==2){
        ans=0;
        for(int i=1;i<=n;i++)
            ans=max(ans,(front[1][i]+front[2][n]-front[2][i-1])%p);
        cout<<ans%p<<"\n";
        return 0;
    }else if(sum<p){
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+in[i][j];
            }
        }
        cout<<dp[m][n]<<"\n";
        return 0;
    }

    for(int i=n;i>=1;i--){
        back[i]=back[i+1]+in[3][i];
    }
    for(int i=1;i<=n;i++){
        f[i]=(front[1][i]-front[2][i-1])%p;
        g[i]=(front[2][i]+back[i])%p;
    }

    ans=0;
    for(int i=n;i>=1;i--){
        Modify(1,g[i]);
        int ret;
        ret=Query(1,0,p-1-f[i]);
        if(ret!=-1) ans=max(ans,f[i]+ret);
        ret=Query(1,p-f[i],p-1);
        if(ret!=-1) ans=max(ans,(f[i]+ret)%p);
    }
    cout<<ans<<"\n";
}