头像

Jackle




离线:5小时前


最近来访(244)
用户头像
Fatin
用户头像
test886
用户头像
franksky
用户头像
QS0x01
用户头像
徐晓耕
用户头像
Dgt-pgr
用户头像
no_hard
用户头像
LonelyLove
用户头像
梦忆晴天
用户头像
菜狗是我我是菜狗
用户头像
第二杯半价
用户头像
WA声闹彻明
用户头像
RC_
用户头像
Agito555
用户头像
北边小洛
用户头像
再睡一分钟
用户头像
xjtu_zfw
用户头像
rsy
用户头像
xxgj
用户头像
种花家的市长


Jackle
7小时前

考点:

$偏移量技巧+分析单调性优化复杂度+队列$

思路做法:

首先由题目可以知道我们的操作无非是,每次取最长的蚯蚓,由最长这里我们可以想到用优先队列,对于每秒长度的增加,我们有采用偏移量技巧:

偏移量技巧:$若x_1>x_2,那么由不等式性质,x_1+detal>x_2+detal$

那么这样我们就可以写出一个时间复杂度为$O(mlogm)$的算法,但是$m<=7*10^6$,这样的复杂度显然是过不了的,不过我也把代码贴一下,感兴趣的可以看看:

$O(mlogm)TLE$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
priority_queue<LL,vector<LL>>heap;
int main()
{
    int n,m,q,u,v,t;
    cin>>n>>m>>q>>u>>v>>t;
    double p=1.0*u/v;

    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        heap.push(x);
    }
    int pos=1;
    for(int i=1;i<=m;i++)
    {
        LL x=heap.top();
        heap.pop();
        x+=(i-1LL)*q;
        if(i==pos*t)printf("%lld ",x),pos++;
        LL x1=p*x,x2=x-x1;
        //cout<<x1<<' '<<x2<<endl;
        x1-=1LL*i*q,x2-=1LL*i*q;
        heap.push(x1),heap.push(x2);
    }
    printf("\n");
    pos=1;
    int cnt=0;
    while(heap.size()){
        cnt++;
        LL x=heap.top();
        heap.pop();
        x+=1LL*m*q;
        if(cnt==pos*t)printf("%lld ",x),pos++;
    }

    return 0;
}

此时我们看看能不能优化时间复杂度,我们由刚刚的最长启发,想到用优先队列,但如果我们仔细分析,我们会发现我们的操作天然就具有一定的单调性,而不需要一个优先队列来维护。

下面是单调性的证明:
我们假设我们操作的依次是两个蚯蚓长度分别为$x_1,x_2,由题目可知x_1>=x_2$,即$x_1$先被切,然后我们再设过了$k$秒之后$x_2$被切了,我们设此时$x_1$被切之后的两段为$l_1,r_1$,$x_2$被切之后的两段为$l_2,r_2$
我们有:
$l_1=\left\lfloor px_1 \right\rfloor+qk,r_1=x_1-\left\lfloor px_1 \right\rfloor+qk$
$l_2=\left\lfloor p(x_2+qk) \right\rfloor,r_2=x_2-\left\lfloor p(x_2+qk) \right\rfloor$

证明$l_1>=l_2$:
$l_1=\left\lfloor px_1 \right\rfloor+qk=\left\lfloor px_1+qk \right\rfloor(由于qk是整数)$
又因为:$0<p<1,x_1>=x2,则\left\lfloor px_1+qk \right\rfloor >=\left\lfloor px_1+pqk \right\rfloor=\left\lfloor p(x_1+qk) \right\rfloor >=\left\lfloor p(x_2+qk) \right\rfloor$
故$l_1>=l2$得证

证明$r_1>=r_2$:
$r_1=x_1-\left\lfloor px_1 \right\rfloor+qk=r_1=\left\lfloor x_1-px_1+qk \right\rfloor>=\left\lfloor x_1-px_1+pqk \right\rfloor$
$>=\left\lfloor x_2-px_2-pqk \right\rfloor$
故$r_1>=r2$得证


所以我们可以发现早切出来的蚯蚓到后面它切出来的段也一定比晚切的蚯蚓段来的长
故我们可以开3个队列来维护,分别维护原序列,以及切出来的左段,和切出来的右段,由刚刚的分析,先切的一定比后切的大,即再同一个队列里面,靠前的一定更大,即我们发现最大值就是队头,所以每次我们取最长,只需要比较三个队列的队头即可,取最大就行

代码:

时间复杂度:$O(nlogn+m)$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=7e6+10;
int q1[N],q2[N],q3[N],hh1,hh2,hh3,tt1,tt2,tt3;

int get()
{
    int ans=-1e9;
    if(hh1<=tt1)ans=max(ans,q1[hh1]);
    if(hh2<=tt2)ans=max(ans,q2[hh2]);
    if(hh3<=tt3)ans=max(ans,q3[hh3]);

    if(hh1<=tt1&&ans==q1[hh1])hh1++;
    else if(hh2<=tt2&&ans==q2[hh2])hh2++;
    else hh3++;

    return ans;

}


int main()
{
    int n,m,q,u,v,t;
    cin>>n>>m>>q>>u>>v>>t;
    tt1=tt2=tt3=-1;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        q1[++tt1]=x; //加入原队列
    }
    sort(q1,q1+n,greater<int>());

    int detal=0; //偏移量
    for(int i=1;i<=m;i++) //模拟过程
    {
        int x=get();
        x+=detal;
        if(i%t==0)printf("%d ",x);
        detal+=q; //偏移量增加
        //切
        int left=1LL*x*u/v,right=x-left;
        //这里要减去是因为在前i秒这两段都还没开始增加
        //我们要维护是一个全局的偏移,即我们要保证他们的实际长度都等于x+detal
        //故我们需要看成他们都在增加,相当于在还没生成时看成这两段都增加了detal
        //故我们可以看成left是由(left-detal)+detal而来,right同理
        left-=detal,right-=detal; 
        q2[++tt2]=left,q3[++tt3]=right;
    }
    printf("\n");

    for(int i=1;i<=n+m;i++)
    {
        int x=get();
        if(i%t==0)printf("%d ",x+detal);
    }

    return 0;
}




Jackle
1天前

考点:

$队列套队列$

思路做法:

我们发现这个不是普通的队列维护问题,因为题目中加入了一个条件,同一个小组内的人会插队,即告诉我们同一个小组内的人会站一起,此时我们发现同一个小组的人可以用一个队列维护,同时我们还要维护不同小组之间的关系,即又需要一个队列,即我们需要队列套队列,第一层队列维护的是小组的编号在队的位置,第二层队列是分别维护每一个小组内人员的位置,故我们只要定义queue<int>Q,q[N],$Q维护的是不同小组之间的排队情况(存的是小组编号),q[i]维护的是编号为i对应的小组人员排队情况$

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int id[N];
queue<int>Q,q[1010];
int main()
{
    int t,T=0;
    auto Clear=[&](int n){
      while(Q.size())Q.pop(); 
      for(int i=1;i<=n;i++)
          while(q[i].size())q[i].pop();
    };
    while(cin>>t,t)
    {
        Clear(t); //清空原先的队列
        T++;
        printf("Scenario #%d\n",T);
        for(int i=1;i<=t;i++)
        {
            int n;
            scanf("%d",&n);
            for(int j=1;j<=n;j++)
            {
                int x;
                scanf("%d",&x);
                id[x]=i;
            }
        }
        char op[20];
        while(scanf("%s",op),*op!='S')
        {
            if(*op=='E')
            {
                int x;
                scanf("%d",&x);
                if(q[id[x]].size()){
                    //有同一组的人了就直接放进去
                    q[id[x]].push(x);
                }else{
                    //说明是新的小组进来
                    q[id[x]].push(x);
                    Q.push(id[x]);
                }
            }
            else
            {
                //出队
                int num=Q.front();
                printf("%d\n",q[num].front());
                q[num].pop();
                if(q[num].size()==0){
                    //删除这个小组
                    Q.pop();
                }
            }
        }
        puts("");
    }

    return 0;
}



Jackle
1天前

考点:

$双栈模拟+维护前缀最大值$

思路做法:

我们发现光标的移动可以看成入栈和出栈,我们可以定义2个栈为分别为$sl,sr$,$sl$表示光标前面的数,$sr$表示光标后面的数,$tl,tr$为两个栈的栈顶,由于我们还要维护前缀的最大值,故我们在定义$f[i]=max(s_1,s_2,..,s_i)$,然后我们在用变量$s$实时维护$sl$中所有数的和,即光标前面所有数的和。

现在我们来看这5个操作:
(1)I X:相当于往$sl$入栈,即$sl[++tl]=x$,然后更新一下栈中的所有数的$s+=x$,同时更新一下我们的$f[tl]=max(f[tl-1],s)$

(2)D:相当于把$sl$出栈,如果$tl>0$,则出栈,同时更新s,即$s-=sl[tl–]$

(3)L:相当于把$sl$出栈,此时不是删除,故我们要把这个数入栈到$sr$,同时更新s,$s-=sl[tl],sr[++tr]=sl[tl–]$

(4)R:相当于把$sr$出栈,如果$tr>0$,则出栈,然后入到左边的栈$sl$,同时更新s和f[tl],即
$s+=sr[tr],sl[++tl]=sr[tr–],f[tl]=max(f[tl-1],s)$

(5)Q k:直接输出$f[k]$即可

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int sl[N],sr[N],tl,tr; //双栈维护
int f[N]; //表示在光标前面,前i个前缀和的最大值,即f[i]=max(s[1],s[2],...,s[i])
int main()
{
    int q;
    cin>>q;
    int s=0;
    f[0]=-1e9;
    while(q--)
    {
        char op[10];
        int x;
        scanf("%s",op);
        if(*op=='I'){
            scanf("%d",&x),sl[++tl]=x;
            s+=x;
            f[tl]=max(f[tl-1],s);
        }
        if(*op=='D'){
            if(tl){
                s-=sl[tl--];
            }
        }
        if(*op=='L'){
            if(tl){
                s-=sl[tl];
                sr[++tr]=sl[tl--];
            }
        }
        if(*op=='R'){
            if(tr){
                s+=sr[tr];
                sl[++tl]=sr[tr--];
                f[tl]=max(f[tl-1],s);
            }
        }
        if(*op=='Q'){
            scanf("%d",&x);
            printf("%d\n",f[x]);
        }
    }

    return 0;
}



Jackle
1天前

考点:

单调栈

思路做法:

我们可以枚举以其中一个矩形为高,看它往两边可以伸展到哪里,即我们发现如果左边的矩形的高$>=$它,都可以延申过去,知道遇到第一个比他小的元素,右边也是同理,如图所示:

123123.png

我们发现$h[l]$和$h[r]$分别是从左往右第一个比它小的,和从右往左第一个比他小的,故在$[l+1,r-1]$之间的矩形高度都可以截出和我们枚举的矩形高度一样,即构成了一个对齐的矩形

故对于求从一个方向开始数每个元素第一个比他小的元素,我们可以采用单调栈算法

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int h[N],L[N],R[N],stk[N],top;
int main()
{
    //单调栈
    int n;
    while(cin>>n,n)
    {
        //求每个矩形从左边开始数第一个比他小的,和右边开始数第一比他小的
        for(int i=1;i<=n;i++)scanf("%d",&h[i]);
        h[0]=h[n+1]=0; //为了让每个矩形都有比他小的,便于处理边界
        top=0;
        for(int i=0;i<=n+1;i++)
        {
            while(top&&h[stk[top]]>=h[i])top--;
            L[i]=stk[top]; //存一下下标
            stk[++top]=i;
        }
        top=0;
        for(int i=n+1;i>=0;i--)
        {
            while(top&&h[stk[top]]>=h[i])top--;
            R[i]=stk[top]; //存一下下标
            stk[++top]=i;
        }
        //枚举以每一个矩形为高,看看能扩展到哪
        LL ans=0;
        for(int i=1;i<=n;i++)
        {
            int l=L[i]+1,r=R[i]-1; //[r,l]范围内的矩形的高都可以到h[i]
            ans=max(ans,(r-l+1LL)*h[i]);
        }
        printf("%lld\n",ans);
    }


    return 0;
}



Jackle
1天前

考点:

$字符串哈希+二分最大回文半径$

思路做法:

做法是利用字符串哈希,枚举每一个回文串的中心,然后求最大的回文半径

为了统一字数回文串和偶数回文串,我们可以把串直接都统一变成奇数串:
abba 可以写成#a#b#b#a# ,abc可以写成#a#b#c#
我们发现我们加上'#'并不会影响是否是回文串
而且我们可以统一把长度为$n$的字符串变成长度为$2*n+1$的字符串,即统一了都是奇数串,这样方便我们枚举回文中心

二分的正确性证明:
我们假设枚举到$i$是字符串的回文中心,我们想要找到以这个位置为中心的最大回文半径是多少,即最大回文串
我们考虑这个回文半径是否具有二分性质,我们假设最大回文半径是$mid$,那么意味着在字符串中$s[i-mid,i+mid]$是一个回文串,那么对于$<=mid$的半径,我们设为$t<=mid$,那么$s[i-t,i+t]$是否是回文串呢,那么是肯定的,因为区间$[i-mid,i+mid]是包含[i-t,i+t]$,由回文串的对称性可知,$s[i-t,i+t]$也一定是回文串,那么我们就证明了对于$<=mid$的数同样满足条件,而对于$>mid$,我们可以利用反证法,如果$>mid$的成立,那么$mid$就不是我们的最大回文半径。
至此我们证明了答案具有二分性,$对于<=mid$的满足条件,$>mid$的不满足条件,所以我们可以使用二分求最大回文半径


那么分析完之后代码就比较好写了:
只要给字符串建立正反哈希,然后枚举回文中心,求最大回文半径,然后取所有回文中心半径最大的,即可以求出最大回文子串的长度

代码:

时间复杂度:$O(NlogN)$

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
typedef unsigned long long ULL;
ULL P=131,h1[N],h2[N],p[N];
char s[N],t[N];
int main()
{
    int T=0;
    while(scanf("%s",s+1),strcmp(s+1,"END"))
    {
        int n=strlen(s+1);
        int m=0;
        t[++m]='#';
        for(int i=1;i<=n;i++)t[++m]=s[i],t[++m]='#'; //把字符串变成奇数串
        //t[++m]='\0';
        p[0]=1;
        //puts(t);
        for(int i=1,j=m;i<=m;i++,j--){
            p[i]=p[i-1]*P;
            //处理正反哈希
            h1[i]=h1[i-1]*P+t[i];
            h2[j]=h2[j+1]*P+t[j];
        }
        auto get=[&](int l,int r,int type){
            if(type==1)return h1[r]-h1[l-1]*p[r-l+1];
            return h2[l]-h2[r+1]*p[r-l+1];
        };
        int ans=1;
        for(int i=1;i<=2*n+1;i++)
        {
            int l=0,r=min(i-1,2*n+1-i); //注意边界
            //mid<=i-1
            //mid<=2*n+1-i
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(get(i-mid,i-1,1)==get(i+1,mid+i,2))l=mid;
                else r=mid-1;
            }
            ans=max(ans,l); //由于我们添加了'#'故我们的回文串的长度就是l
        }
        T++;
        printf("Case %d: %d\n",T,ans);
    }

    return 0;
}



Jackle
2天前

考点:

$(异或前缀树+01Trie)$
$通过异或前缀树,转化成最大异或对问题$

思路做法:

我们可以人为定义一个根,我们定义$0$号点是根节点,定义$d[x]$表示节点u到根节点的路径中所有边权的异或和,由于根节点到自己没有边,所以$d[0]=0$

首先我们由异或的运算性质:
若$s[r]=x_1\oplus x_2 \oplus ......\oplus x_r$,$s[l-1]=x_1\oplus x_2 \oplus ......\oplus x_{l-1}$
则有$x_l\oplus x_{l+1} \oplus ......\oplus x_r=s[r]\oplus s[l-1]$
这就是异或前缀和,这是由于异或和加法类似都具有交换律,结合律,分配律

故如果我们已经知道了所有节点到根路径上的边权异或和,那么我们可以树上任意2点的路径异或和我们都可以表示出来:
即$若给定两点u,v,路径u-v上所有边权异或和为:d[u]\oplus d[v]$
故问题就变成了我们在树上任意选2个点要求$d[u]\oplus d[v]最大$
这不就转化成我们之前做过的一道经典题目: 最大异或对

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
int tr[32*N][2],cnt;
int d[N]; //到根的异或和
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        d[j]=d[u]^w[i];
        dfs(j,u);
    }
}

void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--){
        int t=x>>i&1;
        if(!tr[p][t])tr[p][t]=++cnt;
        p=tr[p][t];
    }
}


int query(int x)
{
    int res=0,p=0;
    for(int i=30;i>=0;i--){
        int t=x>>i&1;
        if(tr[p][!t]){
            p=tr[p][!t];
            res=res*2+!t;
        }else{
            p=tr[p][t];
            res=res*2+t;
        }
    }
    return res;
}



int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    dfs(0,-1);
    //问题变成在n个点选2个使得dx^dy最大
    int ans=0;
    for(int i=0;i<n;i++){
        insert(d[i]);
        ans=max(ans,d[i]^query(d[i]));
    }
    cout<<ans<<endl;
    return 0;
}



Jackle
2天前

考点:

$01Trie树+贪心$

思路做法:

我们考虑一个贪心,就是尽可能让异或起来的高位是1,我们可以建立一个$01trie树$来维护,每个节点最多只有2个儿子($0,1)$,我们只要每次先$insert(x)$,然后从高位到低位遍历x的二进制,即$query(x)$,就可以找到在x前面已经被插入的和$x$异或最大的数是多少。

由于我们要异或和尽可能大,那我们就需要高位尽可能是1,所以我们在遍历字典树的时候,即如果x的第i位是1,那么我们选的数的第i位就尽可能是0,反之如果是0,我们选的数的第i位就尽可能是1,如果不满足在走相同的。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int tr[32*N][2],idx;

void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--){ //从高位到低位
        int t=x>>i&1;
        if(!tr[p][t])tr[p][t]=++idx;
        p=tr[p][t];
    }
}


int query(int x)
{
    int p=0;
    int res=0;
    for(int i=30;i>=0;i--){ //从高位到低位 (贪心尽可能让高位异或起来是1)
        int t=x>>i&1;
        if(t){
            //如果是1,我们要往0走,否则就只能走1
            if(tr[p][0])p=tr[p][0];
            else p=tr[p][1],res|=1<<i;
        }else{
            if(tr[p][1])p=tr[p][1],res|=1<<i;
            else p=tr[p][0];
        }
    }
    return res;

}


int main()
{
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        insert(x);
        ans=max(ans,x^query(x));
    }

    cout<<ans<<endl;


    return 0;
}



Jackle
2天前

考点:

$Trie(字典树)$

思路做法:

我们只要在$insert$的时候在每一个串的结尾字母打上标记,表示有这个单词。
然后我们$query$的时候,我们是按前缀遍历的,所以我们每遍历到一个存在的节点,我们都可以让$res+=cnt[p]$,加上$p$这个节点结尾的单词数量,这$cnt[p]$个单词都是S的前缀,当$p$不存在的时候及时返回$res$,中断前缀遍历

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int tr[N][26],cnt[N*26],idx;
char s[N];
void insert(char *s)
{
    int p=0;
    for(int i=0;s[i];i++){
        int t=s[i]-'a';
        if(!tr[p][t])tr[p][t]=++idx;
        p=tr[p][t];
    }
    cnt[p]++; //打标记
}

int query(char *s)
{
    int p=0;
    int res=0;
    for(int i=0;s[i];i++){
        int t=s[i]-'a';
        p=tr[p][t];
        if(!p)return res;
        res+=cnt[p];
    }
    return res;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        insert(s);
    }
    while(m--){
        scanf("%s",s);
        printf("%d\n",query(s));
    }

    return 0;
}



Jackle
3天前

考点:

$二维前缀和$
$枚举边界+dp(最大连续字段和)$

思路做法:

这题有两种做法:时间复杂度各不相同

(1)二维前缀和:
显然一个朴素的想法就是我们之间枚举矩阵的左上角和右下角,然后用二维前缀和快速计算出矩阵的和
我们可以预处理出二维前缀和复杂度是$O(n^2)$,然后枚举左上角和右下角时间复杂度是$O(n^4)$

二维前缀和:已知矩形左上角$(x_1,y_1$,右下角$(x_2,y_2)$,可以用$O(1)$的时间复杂度计算出矩阵的和
原理:我们定义$s[i][j]表示以(i,j)为右下角,(1,1)为左上角的矩形的和$
<1>.我们来看看$s[i][j]如何计算:$
1111.png
由图我们可以知道$s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]$
<2>.我们来看看$给定(x_1,y_1)和(x_2,y_2)如何求得以这两点确定的矩阵和$:
222.png
由图我们可以看到:$sum=s[x_2][y_2]-s[x_2][y_1-1]-s[x_1-1][y_2]+s[x_1-1][y_1-1]$


代码:

时间复杂度:$O(n^4)$

#include<bits/stdc++.h>
using namespace std;
int s[110][110];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>s[i][j];
        }
    }

    //处理二维前缀和
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
        }
    }
    //枚举左下角和右下角
    int ans=-1e9;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int k=i;k<=n;k++){
                    for(int z=j;z<=n;z++){
                        int x1=i,y1=j,x2=k,y2=z;
                        ans=max(ans,s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
                    }
                }
            }
        }
    cout<<ans<<endl;

    return 0;
}

(2)枚举边界+最大连续字段和
上面我们的枚举方式是枚举左下角和右下角,这里我们换一种枚举烦方式,我们枚举矩阵的上下边界,如何在看看左右边界怎么取,其实我们枚举上下边界之后,我们的问题就转化成一维的了(降维打击),如图:
22222.png

我们可以把在$(i,j)$范围内的每一列看成一个整体即图中的:$k_1,k_2,....,k_n$
如何我们的问题就转化了,我们把从$上下边界在(i,j)的1-n的每一列看成一个数组$,如何我们的问题就变成了求数组的最大连续字段和,这是我们熟悉的问题:

最大连续字段和:
我们定义:$dp[i]表示以i结尾往前连续的最大的和是多少$
我们可以知道状态转移方程为:$dp[i]=max(dp[i-1]+a[i],a[i])$

所以我们就可以只用$O(n^3)$复杂度搞定这题啦
我们只需要维护一下每一列的前缀和,如何枚举上下边界,每次做一次dp即可

代码:

时间复杂度:$O(n^3)$

#include<bits/stdc++.h>
using namespace std;
int s[110][110];
int dp[110];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>s[i][j];
            s[i][j]+=s[i-1][j];
        }
    }



    //枚举上下边界
    int ans=-1e9;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int k=1;k<=n;k++){
                //dp求最大连续字段和
                dp[k]=max(dp[k-1]+s[j][k]-s[i-1][k],s[j][k]-s[i-1][k]);
                ans=max(ans,dp[k]);
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}



Jackle
3天前

考点:

$贪心(中位数)$

思路做法:

首先我们知道对于一个士兵$(x_i,y_i)$它在x轴方向上和y轴方向上是两个独立的部分,即士兵向上向下移动和向左向右移动是互不影响的,所有我们可以分成两个部分来看,要整体最小,由于两部分是独立的,我们只需要这两个部分都取最小即可

我们可以假设所有士兵都会移动到$y=a$这条线上,且每个士兵分别分布在这条线的$b,b+1,.....,b+n-1$位置上,我们设:
$ansy=|y_1-a|+|y_2-a|+....+|y_n-a|$
$ansx=|x_1-b|+|(x_2-1)-b|+....+|(x_n-n+1)-b|$
由题目可知我们的$ans=(ansy+ansx)_{min}$,由于两部分是独立的所以等价于两部分别取最小值
现在我们分别来讨论如何求$ansy和ansx的最小值$


首先这里介绍一下如何求解:$|t_1-k|+|t_2-k|+....+|t_n-k|的最小值$
我们可以把问题抽象成,在一条直线上有$n$个点,它们的位置分别为$t_1,t_2,…,t_n$,你需要在这条直线上选择一个点,它的位置是$k$,要求这个点到$n$个点的距离之和最小

我们先来讨论一个简单的问题:若直线上只有两个点$a,b$,且$a<b$,求$|a-k|+|b-k|$最小值:
我们可以画一个图:
sssss.png
我们发现k的位置有3种可能,$(1)k < a,(2)a <=k <= b,(3)k > b$,由图可以知道我们的k取到a和b之间的时候,$|a-k|+|b-k|=|a-b|这是最小值,其余情况都会比这个值要大$,故我们得到了
$|a-k|+|b-k|>=|a-b|,当且仅当(a<=k<=b)的时候等号成立$
现在我们在来看$|t_1-k|+|t_2-k|+....+|t_n-k|的最小值$,我们可以把$(t_1,t_n),(t_2,t_{n-1})…$这样来分组,这样问题就变成了
若n是偶数
$(|t1-k|+|t_n-k|)+(|t_2-k|+|t_{n-1}-k|)+.....+(|t_{n/2}-k|+|t_{n/2+1}-k|)$
若n是奇数
$(|t1-k|+|t_n-k|)+(|t_2-k|+|t_{n-1}-k|)+.....+|t_{n/2+1}-k|$
我们这样分组之后,我们已经知道了$|a-k|+|b-k|>=|a-b|$那么推广之后,我们要上面的不等式都取到最小值,那么我们这个$k$要位于$t_1,t_2....,t_n的中位数上$,这样我分的每一组$(|t_1-k|+|t_n-k|).....$都可以取到最小值,所以由不等式的可加性,总的不等式也可以取到最小值


(1)由上面的分析,我们可以马上知道$ansy的最小值如何求解:$
我们把所以士兵的$y$坐标从小到大排序,取它们的中位数,即$y[(n+1)/2]$,所有士兵的y坐标都要移动到这

(2)下面我们来分析较$ansx的最小值$,我们假定b已知,对于位置$b,b+1,…,b+n-1$我们每个位置应该放哪个士兵呢?,我们可以贪心的想,肯定是就近原则,即x小的匹配小的位置,大的匹配大的位置。故我们得到了第一步,我们先按每个士兵的$x$值从小到到大排,然后让它们分别对应这n个位置
然后当我们知道了$x_1,x_2…x_n分别是谁的时候$,我们问题就变成了:
$ansx=|x_1-b|+|(x_2-1)-b|+....+|(x_n-n+1)-b|$的最小值,我们可以把$(x_i-(i-1))看成一个整体$把每一个$x[i]$重新变成$x[i]=x[i]-(i-1)$,然后我们问题就变成$ansx=|X_1-b|+|X_2-b|+.....+|X_n-b|$,又变成了我们一般的情况,所以我们在按新的X[i]的权值从小到大排,取中位数$X[(n+1)/2]$然后就可以计算出最小值了

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e4+10;
int x[N],y[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y[i]);
    }
    sort(x+1,x+1+n); //这一步排序是贪心的把每一个x分配到b,b+1,....,b+n-1的位置上(就近原则)
    for(int i=1;i<=n;i++){
        x[i]-=i-1;
    }
    sort(x+1,x+1+n); //这一步排序是求解新的|x1-b|+|x2-b|+...+|xn-k|的最小值
    int mx=x[(n+1)/2];
    LL res=0;
    for(int i=1;i<=n;i++){
        res+=abs(x[i]-mx);
    }

    sort(y+1,y+1+n); //求解|y1-a|+|y2-a|+....+|yn-a|的最小值
    int my=y[(n+1)/2];
    for(int i=1;i<=n;i++){
        res+=abs(y[i]-my);
    }

    cout<<res<<endl;

    return 0;
}