欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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构成的第二大的矩形。(前缀和思 ......

2019牛客暑期多校训练营(第二场)H Second Large Rectangle

示例一:

输入  :

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 }