首页 > 其他分享 >Contest 23-04-18

Contest 23-04-18

时间：2023-04-18 22:58:48浏览次数：39  
标签：max 04 23 int 18 ret maxn ans id

#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";
}

标签：max,04,23,int,18,ret,maxn,ans,id
From： https://www.cnblogs.com/wangyangjena/p/17331541.html

相关文章

  • 4月18日leetcode二叉树几种遍历方式的非递归和递归
    给你二叉树的根节点 root ，返回它节点值的 前序 遍历。 示例1：二叉树的前序中序和后序遍历算法是学习二叉树必不可少的，若是使用c语言遍历前中后序还是比较繁琐的，因为要考虑遍历结果存放的序列大小问题，想要解决这个问题就得想用递归计算二叉树的节点数量，再调用递归子函数完......
  • 23-4-9
    常量2.1字面常量（直接写入的值）const修饰的常变量#define标识符常量枚举常量const修饰的常变量#include<stdio.h>//后面的代码都是在这个头文件下编写的constintnum=4;//const是一种常属性printf("%d\n",num);num=8;printf("%d\n",num);//此时输出的结果为4，不会改变#define......
  • java学习日记20230414-HashSet源码
    HashSetHashSet底层是HashMap添加一个元素时，先得到Hash值，会转化成索引值；找到存储数据表table，看这个索引位置是否存放元素；如果没有直接加入如果有，调用equals比较，如果相同放弃添加，如果不同，则添加到最后在java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)（table表......
  • It's all but a dream（JSOI2023 追忆）
    联赛220，队线265，哈哈。day0下午先去了华山，进行了一个喝茶？？？看着联赛270+的队爷们，感觉人类的悲欢并不相通。晚上试机，由于并不会用Vim，计划sublime写+code::blocks调。先配了code::blocks，然后发现并不能运行？？？查了下发现是xterm没装，尝试自己装一下，然后发现密码并不是123......
  • 2023/3/4[LC:Random_List_Copy]
    2023/3/4[LC:Random_List_Copy]1>心得：写“for"循环之前需要首先思考循环目的和结束条件；例如链表的遍历等；模拟仔细；2>思路首先如果是单纯复制一个普通链表：需要给前一个copy结点留一个pre指针；以便：pre->next=copy;3>解法此题有两个解法问题的关键在于如何解决指向与当前结......
  • 2023.4.18
    今天主要上了python课，我学了python，python好用，最恶心的一点就是代码风格问题，没用太多拘束，看着难受。晚上写了外包，实现了安卓pdf在线预览，通过安卓连接服务器来实现在线预览。 ......
  • 西南民族大学 春季 2023 训练赛 8
    西南民族大学春季2023训练赛8吃火锅思路：每行只算一个（*^*）#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedefpair<string,int>PSI;constintN=2e2+5,INF=0x3f3f3f3f,Mod=1e6;constdoubleeps=1e-8;typedeflonglongll;intall......
  • 4.18学习总结
    用户输入整数n（1<=n<=26）和整数m（m<=n），然后输入n个不同的字母，请编写程序输出在这n个字母中选择m个字母的所有排列序列和组合序列。【源代码程序】import itertools#输入a=input("请输入整数n和整数m的值：")a1=a.split("")for iin a1[::]:    if i=='':    ......
  • 西南民族大学 春季 2023 训练赛 8
    L1-1嫑废话上代码Talkischeap.Showmethecode.L1-2猫是液体a,b,c=map(int,input().split(''))print(a*b*c)L1-3洛希极限#include<bits/stdc++.h>usingnamespacestd;int32_tmain(){doublea,c;intb;cin>>......
  • 2023 4 18
    1#include<iostream>2usingnamespacestd;3intmain(){4intnum=0;5inti,j,k;6for(i=0;i<4;i++){7for(j=0;j<4;j++){8k=8-i-j;9if(k<=6){10num++;11cout<<"time"<<num<......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99