链接:https://www.nowcoder.com/acm/contest/211/B
来源:牛客网

题目描述

炎热的早上,gal男神们被迫再操场上列队,gal男神们本来想排列成x∗x的正方形,可是因为操场太小了(也可能是gal男神太大了),校长安排gal男神们站成多个4∗4的正方形(gal男神们可以正好分成n个正方形)但是有些gal男神对于这种站法颇有微词,所以他们把衣服脱下来拿在手上摇晃示威,站在一条直线上的gal男神可以“交头接耳”,交头接耳会使他们联合起来闹事,人数越多,威胁程度就越大。你作为也反对这种站队方式的体育老师,为了助纣为虐,应该以一种“合理”的方式来排布n个gal男神方阵,使得最大的威胁程度最大。输出这个威胁程度。 以下为化简版题干: 现在有n个由0和1组成的4∗4矩阵,你可以任意排列这些矩阵(注意:你不能旋转或者翻转它们),但是每两个矩阵应该恰好对应。即第一列对第一列(或是第一行对第一行)比如说:

聪明的你一定可以找到一种排列方法使“连续1的序列最长”。我们定义“连续的1序列”为这个序列仅含1且这个序列不拐弯,它可以是横着或者竖着的。请输出最长的“连续的1序列”长度

输入描述:

第一行一个n。
接下来 4*n行,每行4个数。(仅含0,1)。代表n个0/1矩阵。

输出描述:

一个数字表示最长的“连续的1序列”的长度。

示例1

输入

1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出

4

说明

良心样例1

示例2

输入

1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

输出

0

说明

良心样例2

示例3

输入

3
1 0 1 0 
0 0 1 0 
1 0 1 0 
0 1 0 1 

1 0 1 0 
0 1 1 1 
1 0 1 1 
1 1 1 0 

1 0 1 1 
0 1 0 0 
0 1 0 0 
0 0 0 1 

输出

7

说明

这回是真良心数据

备注:

对于前30%,保证n<=1e3.(  然而并没卵用  )
对于前100%的数据,保证n<=1e5.
乱搞是没有活路的,出题人在验题时已经卡掉9种奇奇怪怪的dp和贪心了。
包括但不限于区间dp,O(n)的错误dp,模拟退火算法,爬山算法,遗传算法等.
而且出题人特别卡掉了快读。
ps:10%的数据保证随机。

题目是个贪心……令人绝望的贪心,比赛的时候想的有一些多,其实矩阵就是要么竖着放,要么横着放,然后计算左右/上下边连续最多的1在加上一列/行全是1的,然后不断更新答案就行。题目数据有一些水

1
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

很多代码没有考虑这种情况……其实就是在多加一个判断就好了。

#include<bits/stdc++.h>
#define MAX 200010
using namespace std;
int N[MAX][4][4];
int n,x;
void Read(){
    for(int i=0;i<n;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                cin>>N[i][j][k];
}
int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    Read();
    int ans=0;
    for(int i=0;i<4;i++){
        int t=0,mx_l=0,mx_r=0,mx=0;
        for(int j=0;j<n;j++){
            int l=0,r=0,tl=0;
            for(int k=0;k<4;k++){
                if(N[j][i][k]==0) break;
                l++;
            }
            for(int k=3;k>=0;k--){
                if(N[j][i][k]==0) break;
                r++;
            }
            if(N[j][i][0]==0&&N[j][i][3]==0){
                if(N[j][i][1]==1&&N[j][i][2]==1)
                    tl=2;
                else if(N[j][i][1]==1||N[j][i][2]==1)
                    tl=1;
                else
                    tl=0;
            }
            if(l==4) t++;
            if(l<4){
                mx=max(max(tl,mx),max(mx_r+l,mx_l+r));
                mx_l=max(mx_l,l);
                mx_r=max(mx_r,r);
            }
        }
        ans=max(ans,mx+t*4);
    }

    for(int i=0;i<4;i++){
        int t=0,mx_l=0,mx_r=0,mx=0;
        for(int j=0;j<n;j++){
            int l=0,r=0,tl=0;
            for(int k=0;k<4;k++){
                if(N[j][k][i]==0) break;
                l++;
            }
            for(int k=3;k>=0;k--){
                if(N[j][k][i]==0) break;
                r++;
            }
            if(N[j][0][i]==0&&N[j][3][i]==0){
                if(N[j][1][i]==1&&N[j][2][i]==1)
                    tl=2;
                else if(N[j][1][i]==1||N[j][2][i]==1)
                    tl=1;
                else
                    tl=0;
            }
            if(l==4) t++;
            if(l<4){
                mx=max(max(tl,mx),max(mx_r+l,mx_l+r));
                mx_l=max(mx_l,l);
                mx_r=max(mx_r,r);
            }
        }
        ans=max(ans,mx+t*4);
    }
    cout<<ans<<endl;
    system("pause");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注