2019牛客暑期多校训练营(第二场)H Second Large Rectangle
程序员文章站
2022-05-29 10:12:18
示例一: 输入 : 1 2 01 输出: 0 示例二: 输入 : 1 3 101 输出: 1 示例三(自己自测找错误用的): 输入 : 6 6100111111011111111111111111111101111 输出: 16 题意:在由1和0构成的矩形中找到由仅由1构成的第二大的矩形。(前缀和思 ......
示例一:
输入 :
1 2
01
输出:
0
示例二:
输入 :
1 3
101
输出:
1
示例三(自己自测找错误用的):
输入 :
6 6
100111
111011
111111
111111
111111
101111
输出:
16
题意:在由1和0构成的矩形中找到由仅由1构成的第二大的矩形。(前缀和思维)
解题思路:(1)这是比赛后看别人代码的解法,比赛中自己也有这思路,但没考虑周到。运用前缀和思想算出每个位置前面到这个位置一共有多少个连续的1,然后从左上角开始往下算,每次记录当前位置的长度和位置(位置后面用来计算矩形的高度),每次算出当前最大矩形的大小和次大矩形的大小,更新答案。
(2)dfs,感觉自己剪枝做得不够好所以一直超时,还没想出如何不超时的剪枝方法,先留着,复杂度为o(n³),通过率为95%。
不说了,贴代码:
(1)ac代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e3+20; 4 int a[maxn][maxn],max_1=0,max_2=0;///a数组记录每个位置的前缀和,max_1和max_2为最大和次大 5 char ss[maxn][maxn]; 6 struct node 7 { 8 int num,ins; 9 }pp[maxn];///记录当前位置的长度和位置 10 void update(int summ)///更新最大值和次大值 11 { 12 if(summ>max_1){ 13 swap(max_1,max_2);swap(summ,max_1); 14 } 15 else if(summ>max_2)swap(summ,max_2); 16 } 17 int main() 18 { 19 int n,m; 20 scanf("%d%d",&n,&m); 21 for(int i=1; i<=n; i++) 22 scanf("%s",ss[i]); 23 for(int i=1;i<=n;i++){ 24 for(int j=0;j<m;j++){ 25 if(ss[i][j]=='0')a[i][j+1]==0; 26 else if(ss[i][j]=='1')a[i][j+1]=a[i][j]+1; 27 } 28 } 29 for(int j=1; j<=m; j++) 30 { 31 int r=0; 32 for(int i=1; i<=n; i++) 33 { 34 int book=i; 35 while(r&&pp[r].num>a[i][j]){ 36 update((i-pp[r].ins)*pp[r].num); 37 update((i-pp[r].ins-1)*pp[r].num); 38 book=min(book,pp[r].ins); 39 r--; 40 } 41 pp[++r]={a[i][j],book}; 42 } 43 while(r){ 44 update(((n+1)-pp[r].ins)*pp[r].num); 45 update(((n+1)-pp[r].ins-1)*pp[r].num); 46 r--; 47 } 48 } 49 printf("%d\n",max_2); 50 return 0; 51 }
(2)有剪枝通过的大佬教我一下
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e3+20; 4 int a[maxn][maxn],max_1=0,max_2=0,t;///a数组记录每个位置的前缀和,max_1和max_2为最大和次大 5 int jlen=0,ilen=0,rec;///用于记录最小长度,最高高度和当前面积 6 char ss[maxn][maxn]; 7 void dfs(int x,int y) 8 { 9 if(a[x][y]) 10 { 11 if(a[x][y]>=jlen) 12 { 13 ilen++; 14 rec=ilen*jlen; 15 if(rec>max_1){ 16 swap(max_1,max_2);swap(rec,max_1);} 17 else if(rec>max_2) 18 swap(rec,max_2); 19 dfs(x-1,y); 20 } 21 else if(a[x][y]<jlen) 22 { 23 ilen++,jlen=a[x][y]; 24 rec=ilen*jlen; 25 if(rec>max_1) 26 t=max_1,max_1=rec,max_2=t; 27 else if(rec>max_2) 28 max_2=rec; 29 dfs(x-1,y); 30 } 31 } 32 return; 33 } 34 int main() 35 { 36 int n,m,x,book=0; 37 scanf("%d%d",&n,&m); 38 for(int i=1; i<=n; i++){ 39 scanf("%s",ss[i]); 40 for(int j=0; j<m; j++) 41 { 42 if(j==0&&ss[i][0]=='1') 43 a[i][1]=1,book++; 44 else if(ss[i][j]=='0') 45 a[i][j+1]=0; 46 else if(ss[i][j]=='1') 47 a[i][j+1]=a[i][j]+1,book++; 48 } 49 } 50 for(int i=1; i<=n; i++) 51 { 52 for(int j=1; j<=m; j++) 53 { 54 if(a[i][j]) 55 { 56 ilen=1,jlen=a[i][j]; 57 rec=ilen*jlen; 58 if(rec>max_1) 59 t=max_1,max_1=rec,max_2=t; 60 else if(rec>max_2) 61 max_2=rec; 62 dfs(i-1,j); 63 } 64 } 65 } 66 printf("%d\n",max_2); 67 return 0; 68 }
上一篇: 论分治与归并思想
下一篇: npm package.json文件解读
推荐阅读
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
2020牛客暑期多校训练营(第二场)——H
-
2019牛客暑期多校训练营(第二场) - B - Eddy Walker 2 - BM算法
-
2019牛客暑期多校训练营(第二场)F,H,A,D,B
-
题解 | Polygons-2019牛客暑期多校训练营第二场G题
-
题解 | Go on Strike!-2019牛客暑期多校训练营第二场C题
-
题解 | Kth minimum Clique-2019牛客暑期多校训练营第二场D题
-
2019牛客暑期多校训练营(第二场)A
-
题解 | Subarray-2019牛客暑期多校训练营第二场J题