牛客练习赛29 B
2024-09-04 17:54:17
炎热的早上，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序列”的长度。
示例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
说明
这回是真良心数据 =
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
#include <set>
#include <queue>
#include <cmath>
#define ll long long
using namespace std;
const int N = 1e5+;
int cnt1[N],cnt2[N];
int a[N][][],b[][];
int l[],r[],u[],d[];
int n;
//0 从左到右，1从右到左 ，2 上 ，3下
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
for(int j=;j<=;j++){
for(int k=;k<=;k++){
scanf("%d",&b[j][k]);
}
}
for(int j=;j<=;j++){
for(int k=;k<=;k++){//5的目的时为了确定这一行是否都是1
if(!b[j][k]){
a[i][j][]=k-;//第i个矩阵第j行从左到右第1个0之前有a[i][j][0]个1
break;
}
}
}
for(int j=;j<=;j++){
for(int k=;k>=;k--){
if(!b[j][k]){
a[i][j][]=-k;
break;
}
}
}
for(int j=;j<=;j++){
for(int k=;k<=;k++){
if(!b[k][j]){
a[i][j][]=k-; break;
}
}
}
for(int j=;j<=;j++){
for(int k=;k>=;k--){
if(!b[k][j]){
a[i][j][]=-k;
break;
}
}
} }
//横着
int ans = ;
for(int i=;i<=n;i++){
for(int j=;j<=;j++){
if(a[i][j][]==){
cnt1[j]++;
}
else{
if(a[i][j][]>l[j]&&a[i][j][]>r[j]){
if(a[i][j][]>a[i][j][]){//1个矩阵只能放在一个位置
l[j]=a[i][j][];
}
else{
r[j]=a[i][j][];
}
}
else{
l[j]=max(l[j],a[i][j][]);
r[j]=max(r[j],a[i][j][]);
}
}
}
}
for(int i=;i<=;i++){
ans=max(ans,cnt1[i]*+l[i]+r[i]);//后缀1序列+全1序列+前缀1序列
}
//竖着
for(int i=;i<=n;i++){
for(int j=;j<=;j++){
if(a[i][j][]==){
cnt2[j]++;
}
else{
if(a[i][j][]>u[j]&&a[i][j][]>d[j]){
if(a[i][j][]>a[i][j][]){
u[j]=a[i][j][];
}
else{
d[j]=a[i][j][];
}
}
else{
u[j]=max(u[j],a[i][j][]);
d[j]=max(d[j],a[i][j][]);
}
}
}
}
for(int i=;i<=;i++){
ans=max(ans,cnt2[i]*+u[i]+d[i]);
}
printf("%d\n",ans);
return ;
}
最新文章
- MySQL主从复制、半同步复制和主主复制
- TOGAF：企业信息化复杂吗？
- JavaScript对象就是一组属性(方法)的集合
- apiCode/1/1.1/1.1.1
- Javascript实现鼠标框选元素后拖拽被框选的元素
- 0环境设置 - AUTOTRACE设置
- actor简介
- Spring Security（07）——缓存UserDetails
- 分页（将数据库中的多条数据一页一页的显示在jsp页面中）
- 反转链表算法Java实现
- python之dict与set实现原理之hash算法
- [原]openstack-kilo--issue(十三)Unauthorized: The request you have made requires authentication. (HTTP 401) (Request
- Java FileReader使用相对路径读取文件
- sort中的比较函数compare
- REST 服务器调试 RESTDebugger.exe 和浏览器测试
- npm私有仓库搭建
- awk例子
- CSS nth-child、first-child、last-child、nth-of-type、first-of-type和last-of-type选择器使用
- 应用层timer_如何序列化timer
- 字符串的partition函数