2019牛客多校补题

All-one Matrices （01矩阵）

第八场一道题，求01矩阵中不被其他矩阵完全包含的矩阵个数。

求出一个点的左右边界后，可能的重复情况就只有上下包含关系。

那么逆序枚举每行，记录对于每一对(l,r)(矩阵的左右边界)，下一个矩阵左右边界与其重合时，矩阵底边可能存在的位置。

第二场有个类似的题，求次大矩阵，其实就是求出来不重复的最大矩阵和次大矩阵，

那么可重复的次大矩阵就是次大矩阵或最大矩阵长/宽减一。

#include<cstdio>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
#define INF  0x3f3f3f3f
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
int h[3333][3333];
int vis[3333][3333];
int l[3333],r[3333];
//vis负责记录
//逆序枚举i时
//下次底边在（l,r）范围内的矩形可能出现的范围
//00111
//01111
//01101
//00101
//i=3,j=2时，vis[2][3]=2
//下次矩形底边所在行必须小于2才有可能成为新矩形
int main()
{
    int n,m;s2(n,m);mem(h,0);mem(vis,INF);
    for(int i=1;i<=n;i++)
    {
        char s[3333];scanf("%s",s+1);
        for(int j=1;j<=m;j++)
        {
            if(s[j]=='0') h[i][j]=0;
            else h[i][j]=h[i-1][j]+1;
        }
    }
    int ans=0;
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=m;j++)
        {
            l[j]=j;
            while(l[j]>1&&h[i][l[j]-1]>=h[i][j])
                l[j]=l[l[j]-1];
        }
        for(int j=m;j>=1;j--)
        {
            r[j]=j;
            while(r[j]<m&&h[i][r[j]+1]>=h[i][j])
                r[j]=r[r[j]+1];
        }
        for(int j=1;j<=m;j++)
        {
            int ll=l[j],rr=r[j];
            if(h[i][j]&&i<vis[ll][rr])
            {
                ans++;
                vis[ll][rr]=i-h[i][j]+1;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

CDMA （构造题）

第一次接触构造题呀，，当时比赛的时候一直在找规律但是构造不出。。

如何构造：每一个大矩阵都是由小矩阵

A A

A -A

构造出的。

#include<cstdio>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
int n,a[1111][1111];
int main()
{
    a[1][1]=a[1][2]=a[2][1]=1;a[2][2]=-1;
    s1(n);
    for(int k=4;k<=n;k*=2)
    {
        int kk=k>>1;
        //右上角
        for(int i=1;i<=kk;i++)
            for(int j=kk+1;j<=kk*2;j++)
                a[i][j]=a[i][j-kk];
        //左下角
        for(int i=kk+1;i<=kk*2;i++)
            for(int j=1;j<=kk;j++)
                a[i][j]=a[i-kk][j];
        //右下角
        for(int i=kk+1;i<=kk*2;i++)
            for(int j=kk+1;j<=kk*2;j++)
                a[i][j]=-a[i-kk][j-kk];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ",a[i][j]);
        endll;
    }
    return 0;
}

Move（假二分，枚举暴力）

比赛的时候和队友一起二分双双WA掉了。。。结果这题压根不满足二分性，，，

比如：

15 5

39 39 39 39 39 60 60 60 60 60 100 100 100 100 100

199 为一个合法的答案，但 200 不是，201 也不是。

就直接从下界暴力枚举。

大概学了一下multiset，内部元素自动有序而且可重复，感觉是个很实用的STL了

#include<set>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
int n,k;
int a[1111];
multiset<int>ms;
multiset<int>::iterator it;
int check(int x)//枚举容积
{
    ms.clear();
    for(int i=0;i<n;i++)
        ms.insert(a[i]);
    for(int i=1;i<=k;i++)//枚举每个盒子
    {
        int r=x;
        while(!ms.empty())
        {
            it=ms.upper_bound(r);
            if(it!=ms.begin())
            {
                it--;
                r-=*it;
                ms.erase(it);
            }
            else break;
        }
    }
    if(ms.size()==0) return 1;
    return 0;
}
int main()
{
    int t;s1(t);int tt=1;
    while(t--)
    {
        s2(n,k);
        int sum=0,l=0;
        for(int i=0;i<n;i++)
        {
            s1(a[i]);
            sum+=a[i];l=max(l,a[i]);
        }
        sum/=k;
        l=max(l,sum);
        while(!check(l)) l++;
        printf("Case #%d: %d\n",tt++,l);
    }
    return 0;
}

Upgrading Technology （思维，后缀和优化）

牛客链接：https://ac.nowcoder.com/acm/contest/886/J

第六场J题

题意：你有n个技能每个技能有m级，从j-1 级升级到 j 级需要支付 c元（可能小于零，此时获得收益），当所有技能都升级到 j 级时，获得额外奖励 d 元（可能小于零，此时表示损失）询问最大的利润，利润可以0（即升级0个技能）。

思路：

对每个收益求前缀和，
那么最大收益是在全部技能升到某级别后的收益，和部分（非全部）技能继续升级获得收益，两部分相加得到的

暴力也能过，但是有点险，可以维护一个后缀最大值优化。

还有一点，数据范围在ll的时候INF记得开大点。

#include<cstdio>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
#define INF  1e18
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))

int n,m;//种类数和等级数
ll s[1111];//全部技能升到j等级的净收益
ll d[1111];//全部技能升到j等级的总收益
ll c[1111][1111];//i技能升到j等级获得的收益
ll x[1111][1111];//i技能升级到j等级及以后能获得的最大收益
int main()
{
    int t;s1(t);int tt=1;
    while(t--)
    {
        s2(n,m);
        mem(c,0);mem(s,0);mem(d,0);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ll z;scanf("%lld",&z);
                c[i][j]=c[i][j-1]-z;
                x[i][j]=c[i][j];
            }
            for(int j=m-1;j>=0;j--)//记得0的情况，因为枚举等级基础时可能为0
                x[i][j]=max(c[i][j],x[i][j+1]);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%lld",&d[i]);
            d[i]+=d[i-1];s[i]=d[i];
            for(int j=1;j<=n;j++)
                s[i]+=c[j][i];
        }
        ll ans=0;
        for(int k=0;k<=m;k++)//枚举以加到哪一等级为基础
        {
            ll minsh=INF,tmp=0,cnt=0;
            for(int i=1;i<=n;i++)
            {
                ll maxsh=x[i][k]-c[i][k];
                if(maxsh>0)
                {
                    cnt++;
                    minsh=min(minsh,maxsh);
                    tmp+=maxsh;
                }
            }
            if(cnt==n) tmp-=minsh;
            ans=max(ans,tmp+s[k]);
        }
        printf("Case #%d: %lld\n",tt++,ans);
    }
    return 0;
}

Subsequence（单调队列，思维）

VJ链接：https://vjudge.net/problem/HDU-3530

补题补到第三场有个题，是这题的二维版本，就先拿这个题练一下。

题意：求数列中满足最大值减去最小值的范围在m，k之间的最长子串

思路:利用两个单调队列，一个维护当前最大值，一个维护当前最小值。

如更新到某值时候，最大值减去最小值大于k，说明该值更新了最大值或者最小值，

为了让该值结尾的字串依然满足题意，需要更新另外一个最值队列，

用last记录最后满足题意的左端点位置。

然后判断此序列是否满足最值之差大于等于m。

因为如果最大值减去最小值仍然小于m，此区间不可能存在字串满足题意。

如m=2,k=2,a[]=234356。

#include<cstdio>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,m,k;
int a[MAXN];
//单调队列
int mx[MAXN];//单调递减
int mi[MAXN];//单调递增
int main()
{
    while(~s3(n,m,k))
    {
        int l1=0,l2=0,r1=0,r2=0,last=1,ans=0;
        for(int i=1;i<=n;i++)
        {
            s1(a[i]);
            while(r1>l1&&a[mx[r1-1]]<a[i]) r1--;
            while(r2>l2&&a[mi[r2-1]]>a[i]) r2--;
            mx[r1++]=i;mi[r2++]=i;
            while(r1>l1&&r2>l2&&a[mx[l1]]-a[mi[l2]]>k)
            {
                if(mx[l1]<mi[l2])
                    last=mx[l1++]+1;
                else
                    last=mi[l2++]+1;
            }
            if(r1>l1&&r2>l2&&a[mx[l1]]-a[mi[l2]]>=m)
                ans=max(ans,i-last+1);
        }
        printf("%d\n",ans);
    }
    return 0;
}

Planting Trees （单调队列）

链接：https://ac.nowcoder.com/acm/contest/883/F?&headNav=acm

题意：求矩阵中满足元素之差小于等于m的最大矩阵。

思路：没思路。。一开始想拿求01矩阵的思路写，但是发现很难维护，因为需要维护当前串的最大元素，最小元素。

进一步想到使用单调队列（我还以为单调队列就只能拿来滑窗玩呢ε=ε=ε=┏(゜ロ゜;)┛）

题目描述中提到了n^3，并且保证不会超时，应该想到设计一个O（n^3）的算法。

那么枚举矩阵的上边界，下边界，右边界，利用这些求出满足要求的最小左边界。

为了将二维矩阵压缩成一维，枚举上边界下边界时顺序枚举，并且只在枚举上边界时初始化最值数组。

这样数组中存的即为上界下界该列中的最值。

#include<bits/stdc++.h>
#define INF  0x3f3f3f3f
using namespace std;
//单调队列
//枚举上下边界和右边界
//二维压缩成一维
int n,m,a[505][505];
int mx[505],mn[505];
int q1[505],q2[505];
int l1,l2,r1,r2;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d",&a[i][j]);
        int ans=0;
        for(int l=1; l<=n; l++)
        {
            //初始化最大最小值
            for(int p=0;p<=n+1;p++)
                mx[p]=0,mn[p]=INF;
            for(int r=l; r<=n; r++)
            {
                l1=l2=r1=r2=0;
                for(int k=1,p=0; k<=n; k++) //枚举右边界
                {
                    //更新最大最小值
                    mx[k]=max(mx[k],a[r][k]);
                    mn[k]=min(mn[k],a[r][k]);
                    while(l1<r1&&mx[q1[r1-1]]<mx[k]) r1--;
                    while(l2<r2&&mn[q2[r2-1]]>mn[k]) r2--;
                    q1[r1++]=k,q2[r2++]=k;
                    while(l1<r1&&l2<r2&&mx[q1[l1]]-mn[q2[l2]]>m)//更新最小左边界
                    {
                        if(q1[l1]<q2[l2])
                            p=q1[l1++];
                        else
                            p=q2[l2++];
                    }
                    ans=max(ans,(r-l+1)*(k-p));
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

sequence （单调栈，线段树，前缀和）

牛客链接：https://ac.nowcoder.com/acm/contest/884/C?&headNav=acm

题意：

给你2个长度为n的区间 a区间和b区间

区间的值为b区间之和乘以a区间的最小值，要你求出值最大的区间

思路：么得思路，只能想到求出a数组每个数字最远贡献，想怎么求有贡献的这段区间里 b数组的最大和绞尽脑汁，，，

一直在想怎么让求出的最值区间还能包括ai，忘了分成两段求前缀和。。。

因为舍友借走了电脑这个题断断续续写了三天，也是今年牛客多校补题的最后一道题了。

一个教训就是线段树的端点要记得啊，左开右闭写顺了，，右区间忘记y>=mid+1，(′д｀ )…彡…彡

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=3e6+10;
#define pi  acos(-1.0)
#define INF  0x3f3f3f3f3f3f3f3f
#define mod   1000000009
#define lson rt<<1,l,mid
#define endll printf("\n")
#define pii pair<int, int>
#define rson rt*2+1,mid+1,r
#define s1(a) scanf("%d",&a)
int n;
ll a[MAXN],b[MAXN];
int l[MAXN],r[MAXN];//a数组中某点向左向右最远贡献
struct IN
{
    ll mi,ma;
}m[MAXN<<2];
//枚举每个点，利用a数组找到该数字影响范围(l,r)
//对前缀和利用线段树维护最大值与最小值
//当a[i]>0时对左小区间求最小值，右小区间求前缀和最大值，相减即为最大值
ll tmpmi,tmpmx;
void build(int rt,int l,int r)
{
    if(l==r)
    {
        m[rt].mi=m[rt].ma=b[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);build(rson);
    m[rt].mi=min(m[rt<<1].mi,m[rt*2+1].mi);
    m[rt].ma=max(m[rt<<1].ma,m[rt*2+1].ma);
}
void init()
{
    for(int i=1;i<=n;i++)
    {
        l[i]=i;
        while(l[i]>1&&a[l[i]-1]>=a[i])
            l[i]=l[l[i]-1];
    }
    for(int i=n;i>=1;i--)
    {
        r[i]=i;
        while(r[i]<n&&a[r[i]+1]>=a[i])
            r[i]=r[r[i]+1];
    }
    build(1,1,n);
}
ll askmi(int x,int y,int rt,int l,int r)
{
    if(l>=x&&r<=y) return m[rt].mi;
    int mid=(l+r)>>1;
    ll ans=INF;
    if(x<=mid) ans=min(ans,askmi(x,y,lson));
    if(y>mid) ans=min(ans,askmi(x,y,rson));//又是血的教训。。错误示范：y>=mid，摔
    return ans;
}
ll askmx(int x,int y,int rt,int l,int r)
{
    if(l>=x&&r<=y) return m[rt].ma;
    int mid=(l+r)>>1;
    ll ans=-INF;
    if(x<=mid) ans=max(ans,askmx(x,y,lson));
    if(y>mid) ans=max(ans,askmx(x,y,rson));//
    return ans;
}
int main()
{
    s1(n);b[0]=0;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]),b[i]+=b[i-1];
    if(n==1)//特判加速
    {
        printf("%lld\n",a[1]*b[1]);
        return 0;
    }
    init();
    ll ans=-INF;
    for(int i=1;i<=n;i++)
    {
        int ll=l[i],rr=r[i];
        if(a[i]==0) ans=ans>0?ans:0;//特判加速
        else if(a[i]>0)
        {
            tmpmi=askmi(max(ll-1,1),max(i-1,1),1,1,n);
            tmpmx=askmx(i,rr,1,1,n);
            ans=max(ans,a[i]*(tmpmx-tmpmi));
        }
        else
        {
            tmpmx=askmx(max(ll-1,1),max(i-1,1),1,1,n);
            tmpmi=askmi(i,rr,1,1,n);
            ans=max(ans,a[i]*(tmpmi-tmpmx));
        }
    }
    printf("%lld\n",ans);
}

2019牛客多校补题

All-one Matrices （01矩阵）

CDMA （构造题）

Move（假二分，枚举暴力）

Upgrading Technology （思维，后缀和优化）

Subsequence（单调队列，思维）

Planting Trees （单调队列）

sequence （单调栈，线段树，前缀和）