2019牛客暑期多校训练营（第二场）

传送门

F.Partition priblem(DFS)

•题意

　　有 2n 个人，任意两个人之间都存在竞争值；

　　定义 v[ i ][ j ] 表示 i 与 j 的竞争值为 v[ i ][ j ]；

　　将这 2n 个人划分成两组，每组有 n 人，组内的成员之间不存在竞争；

       竞争值为(i,j不同组)

求竞争值最大是多少

•思路

先用sum记录总的竞争值

再分别把k先后放入A,B两个组

同组之间 减去竞争值

直到2n个都分配完毕

至于为什么是用总的做减法呢？

是因为这样比较容易剪枝：

当未分配的竞争值(也就是需要继续做减法的竞争值)<前面情况已得到的最大竞争值ans，这种情况可以不再讨论

•代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=50;
int t[maxn][maxn];
int a[maxn],b[maxn];
ll sum,ans;
int n;
void dfs(int curA,int curB,ll unt)//A B队员和未安排的关系
{
    if(unt<ans) return ;
    if(curA>n||curB>n) return ;//每对4队人数限制为n
    int k=curA+curB+1;//下一个该安排的人的序号
    if(k>2*n)
    {
        ans=max(ans,unt);
        return ;
    }
    ll untA=unt,untB=unt;

    //归为A组
    a[curA]=k;
    for(int i=0;i<curA;i++)
        untA-=t[a[i]][k];
    dfs(curA+1,curB,untA);

    //k号归为B组
    b[curB]=k;
    for(int i=0;i<curB;i++)
        untB-=t[b[i]][k];
    dfs(curA,curB+1,untB);
}


int main()
{
    cin>>n;
    for(int i=1;i<=2*n;i++)
    {
        for(int j=1;j<=2*n;j++)
        {
            cin>>t[i][j];
            if(j<i)
                sum+=t[i][j];
        }
    }
    dfs(0,0,sum);
    cout<<ans<<endl;
}

H.Second Large Rectangle(单调栈或悬线法)

•题意

给一个由01组成的NxM矩阵

求全由1组成的第二大矩阵面积

•思路1(单调栈)

先预处理一下矩形的高，再利用单调栈求最大面积，根据最大面积求大面积

设h[i][j]为第i行第j列的高(列连续的1)

因为在利用单调栈求最大面积时，

是通过每一行求最大面积

所以可以优化二维h[i][j]变一维h[j]

在更新矩形时，要注意矩形去重和大矩形内部的最大矩形

•代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
stack<int> sta;
char a[maxn][maxn];
int h[maxn];//每一行每一列的高度
int l[maxn],r[maxn];
int n,m;
struct node
{
    int x1,y1;
    int x2,y2;
    int val;
};
struct node fir={0,0,0,0,0};
struct node sec={0,0,0,0,0};

void Broad()
{
    while(!sta.empty())
        sta.pop();

    for(int i=1;i<=m;++i)
    {
        while(!sta.empty()&&h[sta.top()]>=h[i])
            sta.pop();

        l[i]=sta.empty()?1:sta.top()+1;
        sta.push(i);
    }

    while(!sta.empty())
        sta.pop();

    for(int i=m;i>=1;--i)
    {
        while(!sta.empty()&&h[sta.top()]>=h[i])
            sta.pop();

        r[i]=sta.empty()?m:sta.top()-1;
        sta.push(i);
    }
}

void update(node &n,int x1,int y1,int x2,int y2)
{
    n.x1=x1;
    n.x2=x2;
    n.y1=y1;
    n.y2=y2;
    n.val=(x2-x1+1)*(y2-y1+1);
}

void Slove()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='1') h[j]++;
            else h[j]=0;
        }
        Broad();
        for(int j=1;j<=m;j++)
        {
            //当前面积
            int curS=h[j]*(r[j]-l[j]+1);
            //当前坐标 (x1,y1)左上 (x2,y2)右下
            int x1=i-h[j]+1;
            int y1=l[j];
            int x2=i;
            int y2=r[j];

            if(curS>=fir.val)//当前面积>=最大面积时
            {
                if(!(x1==fir.x1&&x2==fir.x2&&y1==fir.y1&&y2==fir.y2))//不是同一个矩形时
                {
                    fir.val=curS;//更新最大矩形和第二大矩形
                    update(sec,fir.x1,fir.y1,fir.x2,fir.y2);
                    update(fir,x1,y1,x2,y2);
                }
            }
            else if(curS>sec.val)//当前面积>第二大矩形时 更新
                update(sec,x1,y1,x2,y2);

            int curxsub=(x2-x1)*(y2-y1+1);//(宽-1)*长
            int curysub=(y2-y1)*(x2-x1+1);//(长-1)*宽
            
            if(curxsub>sec.val)//当前矩形长-1的矩形面积>第二大矩形时 更新
                update(sec,x1+1,y1,x2,y2);

            if(curysub>sec.val)//当前矩形宽-1的矩形面积>第二大矩形时 更新
                update(sec,x1,y1+1,x2,y2);
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];

    Slove();
    cout<<sec.val<<endl;
}

•思路2(悬线法)

悬线法裸题，(悬线法)

利用悬线法处理出left[i][j],right[i][j]和up[i][j]

更新矩阵与方法1相同

坑点：

在初始化时，只把为1的left[i][j],right[i][j],up[i][j]赋值，

为0的不用赋值，如果赋值的话，也变成可以有面积的了

(在这找了一个多小时bug，哭唧唧

•代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
char a[maxn][maxn];
int l[maxn][maxn],r[maxn][maxn],up[maxn][maxn];
int n,m;
struct node
{
    int x1,y1;
    int x2,y2;
    int val;
};
struct node fir={0,0,0,0,0};
struct node sec={0,0,0,0,0};
void update(node &n,int x1,int y1,int x2,int y2)
{
    n.x1=x1;
    n.x2=x2;
    n.y1=y1;
    n.y2=y2;
    n.val=(x2-x1+1)*(y2-y1+1);
}

void Slove()
{
     for(int i=1;i<=n;i++)
        for(int j=2;j<=m;j++)//左边界 从左往右推
            if(a[i][j]=='1'&&a[i][j-1]=='1')
                l[i][j]=l[i][j-1];

    for(int i=1;i<=n;i++)
        for(int j=m-1;j>=1;j--)//右边界 从右往左推
            if(a[i][j]=='1'&&a[i][j+1]=='1')
                r[i][j]=r[i][j+1];

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i>1&&a[i][j]=='1'&&a[i-1][j]=='1')
            {
                up[i][j]=up[i-1][j]+1;
                l[i][j]=max(l[i][j],l[i-1][j]);
                r[i][j]=min(r[i][j],r[i-1][j]);
            }
            //下面跟方法一相同
            int curS=(r[i][j]-l[i][j]+1)*up[i][j];
            int x1=i-up[i][j]+1;
            int y1=l[i][j];
            int x2=i;
            int y2=r[i][j];
            if(curS>=fir.val)//当前面积>=最大面积时
            {
                if(!(x1==fir.x1&&x2==fir.x2&&y1==fir.y1&&y2==fir.y2))//不是同一个矩形时
                {
                    fir.val=curS;//更新最大矩形和第二大矩形
                    update(sec,fir.x1,fir.y1,fir.x2,fir.y2);
                    update(fir,x1,y1,x2,y2);
                }
            }
            else if(curS>sec.val)//当前面积>第二大矩形时 更新
                update(sec,x1,y1,x2,y2);
;

            int curxsub=(x2-x1)*(y2-y1+1);//(宽-1)*长
            int curysub=(y2-y1)*(x2-x1+1);//(长-1)*宽

            if(curxsub>sec.val)//当前矩形长-1的矩形面积>第二大矩形时 更新
                update(sec,x1+1,y1,x2,y2);

            if(curysub>sec.val)//当前矩形宽-1的矩形面积>第二大矩形时 更新
                update(sec,x1,y1+1,x2,y2);

        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='1')//只把为1的初始化!!!
            {
                l[i][j]=j;
                r[i][j]=j;
                up[i][j]=1;
            }
        }
    }
    Slove();
    cout<<sec.val<<endl;
}