SCP-bzoj-1057

项目编号：bzoj-1057

项目等级：Safe

项目描述：

特殊收容措施：

　　首先枚举最左上角的点（记为(1,1)）是黑点还是白点，这样就可以把与(1,1)不在同一对角线系的格点颜色翻转（形式化地，格点(x,y)被翻转颜色当且仅当(x+y) and 1=1），然后问题就等价于求整个棋盘中的颜色与(1,1)相同的最大子矩形/正方形，也即最大全0/1子矩阵。

　　求最大全0/1子矩阵有一个著名的方法叫悬线法：（以下描述中默认为求全1子矩阵）

　　•从上到下枚举每行，设当前行为i，h[j]表示第j列从第i行向上最长连续的全1串长度；l[j]表示选定子矩阵高度为h[j]，最下端行号为i，且(i,j)存在于子矩阵中时其能达到的极左行号；r[j]定义类似于l[j]。

　　•这样最大子矩形即为max{(r[j]-l[j]+1)*h[j]}，子正方形即为max{min(r[j]-l[j]+1,h[j])²}。

　　•h[j]的转移比较显然，每次i下移一行的时候，若第j列元素为1，则h[j]加一，否则h[j]赋为0。

　　•对于l[j]的转移，我们可以通过行内从左向右递推求得。考虑到子矩阵必须连续，则对于cur，不断探测cur的左一位，如果发现h[cur-1]<h[j]则l[j]即cur，否则cur赋为l[cur-1]并继续探索。

　　•r[j]的转移类似l[j]，并且我们可以证明这种递推是均摊O(1)的。

　　这样，我们就能用O(nm)的复杂度解决这个（俩）问题了。

附录：

 1 #include <bits/stdc++.h>

 2 #define range(i,c,o) for(register int i=(c);i<(o);++i)

 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i)

 4 using namespace std;

 5

 6 //#define __debug

 7 #ifdef __debug

 8     #define sub(t) t

 9 #else

10     #define sub(t) __attribute__((optimize("-O2"))) inline t

11 #endif

12

13 // quick_io BEGIN HERE

14 sub(unsigned) getU()

15 {

16     char c; unsigned r=0; while(!isdigit(c=getchar()));

17     for(;isdigit(c);c=getchar()) r=(r<<3)+(r<<1)+c-'0';

18     return r;

19 }

20 // quick_io END HERE

21

22 sub(int) sqr(const int&x) {return x*x;}

23

24 static int n=getU(),m=getU(),squ=0,mat=0;

25 bool a[2005][2005];

26 int h[2005],l[2005],r[2005];

27 sub(void) work(const bool&rev)

28 {

29     memset(h,0,sizeof h);

30     range(i,0,n)

31     {

32         range(j,0,m)

33         {

34             a[i][j]^((i+j)&1)^rev?++h[j]:h[j]=0;

35         }

36         range(j, 0 , m) for(

37             l[j]=j;

38             l[j]    &&h[l[j]-1]>=h[j];

39             l[j]=l[l[j]-1]

40         );

41         dange(j,m-1,-1) for(

42             r[j]=j;

43             r[j]+1<m&&h[r[j]+1]>=h[j];

44             r[j]=r[r[j]+1]

45         );

46         range(j,0,m)

47         {

48             squ=max(squ,sqr(min(r[j]-l[j]+1,h[j])));

49             mat=max(mat,(r[j]-l[j]+1)*h[j]);

50         }

51     }

52 }

53

54 int main()

55 {

56     range(i,0,n) range(j,0,m) a[i][j]=getU();

57     range(i,0,2) work(i);

58     return printf("%d\n%d\n",squ,mat),0;

59 }

巴特西

SCP-bzoj-1057

最新文章

热门文章