题意 对于一个由0,1构成的矩形,求解其中面积最大的全0子矩形,和全0子正方形 思路 法一:枚举上下左右四个边界,利用二维前缀和,如果前缀和为0就成立 复杂度: 法二:枚举左右边界,对边界内的1按y排序,每两个相邻点+边界构成矩形 复杂度:,(m为1的个数,最多到) 法三:悬线法,将矩形中每个1视为黑点0视为无色点,每个点有一条向上的悬线悬线碰到黑点重新开始计算长度,对于每一条悬线,都有可能成为矩形的上下界 求点(i,j)最长悬线度 求点(i,j)向左最长延伸长度 求点(i,j)向左最长延伸长度 求(i,j)所在的悬线向左最长延伸长度 求(i,j)所在的悬线向左最...