a*******y 发帖数: 1040 | 1 Imagine there is a square matrix with n x n cells. Each cell is either
filled with a black pixel or a white pixel. Design an algorithm to find the
maximum subsquare such that all four borders are filled with black pixels; |
l*********8 发帖数: 4642 | |
Z*****Z 发帖数: 723 | 3 有比O(N3)更好的解么?
【在 l*********8 的大作中提到】 : 经典DP问题吧
|
s*******s 发帖数: 46 | 4 想到了一个O(n^2)的DP算法,把一个矩形分成两部分,分开DP |
Z*****Z 发帖数: 723 | |
g**e 发帖数: 6127 | 6 悲剧,题目都看错了 lol
【在 Z*****Z 的大作中提到】 : 确认一下,这题是空心儿的?
|
Z*****Z 发帖数: 723 | 7 lol
【在 g**e 的大作中提到】 : 悲剧,题目都看错了 lol
|
w****x 发帖数: 2483 | 8
the
A[i,j] = 0 || 1 + max{A[i-1, j], A[i, j-1], A[i-1, j-1]}
【在 a*******y 的大作中提到】 : Imagine there is a square matrix with n x n cells. Each cell is either : filled with a black pixel or a white pixel. Design an algorithm to find the : maximum subsquare such that all four borders are filled with black pixels;
|
Z*****Z 发帖数: 723 | 9 这题是空心儿的
【在 w****x 的大作中提到】 : : the : A[i,j] = 0 || 1 + max{A[i-1, j], A[i, j-1], A[i-1, j-1]}
|
g**e 发帖数: 6127 | 10 只想出了O(n^3)的
【在 Z*****Z 的大作中提到】 : lol
|
|
|
t**********h 发帖数: 2273 | 11 经典dp,two爷给出过简洁解法,我没记错的话 |
a*******y 发帖数: 1040 | |
s********0 发帖数: 34 | 13 O(n^3) 这样可行不~
预处理: O(N^2)
x[i][j]: (i,j) 在ith row左边的连续black
y[i][j]: (i,j) 在jth col上边的连续black
for i:
for j:
for (int d = min(x[i][j], y[i][j]); d >= 1; d--)
if (x[i][j-d+1] >= d && y[i-d+1][j] >= d) {
ans = max(ans, d);
break;
}
return ans; |
Z*****Z 发帖数: 723 | 14 cool
【在 s********0 的大作中提到】 : O(n^3) 这样可行不~ : 预处理: O(N^2) : x[i][j]: (i,j) 在ith row左边的连续black : y[i][j]: (i,j) 在jth col上边的连续black : for i: : for j: : for (int d = min(x[i][j], y[i][j]); d >= 1; d--) : if (x[i][j-d+1] >= d && y[i-d+1][j] >= d) { : ans = max(ans, d); : break;
|
w****x 发帖数: 2483 | 15
这题记的是麦考索芙特的题,拿个二维矩阵作DP, 就是在知道定点和长度的情况下,O(1)
判断是不是4边都是black.
顺便再膜拜一下two爷
【在 t**********h 的大作中提到】 : 经典dp,two爷给出过简洁解法,我没记错的话
|
t**********h 发帖数: 2273 | 16 哥,好久没去你博客看,你都快做满800道了啊,牛逼
1)
【在 w****x 的大作中提到】 : : 这题记的是麦考索芙特的题,拿个二维矩阵作DP, 就是在知道定点和长度的情况下,O(1) : 判断是不是4边都是black. : 顺便再膜拜一下two爷
|
l*********8 发帖数: 4642 | 17 赞!
【在 t**********h 的大作中提到】 : 哥,好久没去你博客看,你都快做满800道了啊,牛逼 : : 1)
|
Z*****Z 发帖数: 723 | 18 还有一个小优化
for (int d = min(x[i][j], y[i][j]); d >= ans; d--)
还可以考虑,优化之后的worst case在什么时候达到?
【在 s********0 的大作中提到】 : O(n^3) 这样可行不~ : 预处理: O(N^2) : x[i][j]: (i,j) 在ith row左边的连续black : y[i][j]: (i,j) 在jth col上边的连续black : for i: : for j: : for (int d = min(x[i][j], y[i][j]); d >= 1; d--) : if (x[i][j-d+1] >= d && y[i-d+1][j] >= d) { : ans = max(ans, d); : break;
|
p********s 发帖数: 37 | 19 yy个未完成的思路
对于每个点首先算出上下左右各能走多远,记为l[x][y], r[x][y],t[x][y],b[x][y]
然后记每个点(x,y)的l和t的最小值为lt[x][y],r和b的最小值为rb[x][y],这样我们有
所有正方形可能的左上边框和右下边框
然后按对角线dp,就是看俩边框能不能套起来(当然能套起来一定就是个正方形)。因
此可以进一步转化为给定俩有序区间集合,可各从中选一个区间,使得这俩区间的交最
大。。
最后一步明天店面完再yy吧,说不定能比n^3好 |
Z*****Z 发帖数: 723 | 20 貌似还是N3的。如果像你说的记 左上 和 右下,worst case的输入矩阵是,一个方阵,
左上角全是1,右下角全是0.
【在 p********s 的大作中提到】 : yy个未完成的思路 : 对于每个点首先算出上下左右各能走多远,记为l[x][y], r[x][y],t[x][y],b[x][y] : 然后记每个点(x,y)的l和t的最小值为lt[x][y],r和b的最小值为rb[x][y],这样我们有 : 所有正方形可能的左上边框和右下边框 : 然后按对角线dp,就是看俩边框能不能套起来(当然能套起来一定就是个正方形)。因 : 此可以进一步转化为给定俩有序区间集合,可各从中选一个区间,使得这俩区间的交最 : 大。。 : 最后一步明天店面完再yy吧,说不定能比n^3好
|
|
|
p********s 发帖数: 37 | 21 可能没大理解"左上角全是1,右下角全是0",这个好像是best case
阵,
【在 Z*****Z 的大作中提到】 : 貌似还是N3的。如果像你说的记 左上 和 右下,worst case的输入矩阵是,一个方阵, : 左上角全是1,右下角全是0.
|
Z*****Z 发帖数: 723 | 22 也可能我没理解对你的算法。等你有空了具体说说。
【在 p********s 的大作中提到】 : 可能没大理解"左上角全是1,右下角全是0",这个好像是best case : : 阵,
|
p********s 发帖数: 37 | 23 还是没考虑成熟,哎面完了人就懒下来了,bz大牛将就看下
如前所述如果把正方形预处理成左上和右下两部分,并根据对角线dp,那么对于每条对
角线(左上-右下方向)问题可以转化为一维情况。即
如果可能的左上角(x0,y0)可以往右往下延伸到(x0+a,y0)和(x0,y0+a),且如果
可能的右下角(x0+i,y0+i)可以往左往下延伸到(x0+i-b,y0+i)和(x0+i,y0+i-b)
则构成正方形,否则不行。一维表示就是
用集合{(ai,bi)}表示所有(<=n)条起点为ai,终点为bi的直线,对应于上面的左上角(
ai是y0的值,bi是y0+a)
用{cj,dj}表示所有条起点为cj,终点为dj的直线,对应上面的右下角(dj是y0+i,cj是
y0+i-b)
要求的是:对于每个(ai,bi)有集合{(cj',dj')}满足cj'<=ai,bi>=dj'(才能构成正
方形),求集合中最大的dj'-ai(对于每个ai相当于求最大的dj')
-----问题描述后开始糊涂的分割线------
一开始显然{ai,bi}是按ai自然排好序的,a[i+1]=a[i]+1
而{cj,dj}是按dj排序,d[j+1]=d[j]+1
那么关键在于for(i=y0,i
并从中求出小于bi的最大的dj。
首先满足cj<=ai的条件很容易递推,只要o(n)的重新对{(cj,dj)}按cj进行桶排序,就
可以知道啥时候一个(cj,dj)开始能够覆盖ai,啥时候不再能够覆盖,那每次从i移动到
i+1只要移进移出相应的(cj,dj)就行了。
而维护条件bi>=dj相应麻烦很多,因为bi和bi+1之间没有任何关系。但是如果现在维护
的集合是按照di排序的(di天然有序)那么我们只要做一个范围查询即在[0,bi]区间
中求最大的di,就可以了。
那么算法描述如下
for i <- y0 to yn
把所有dj=b[i-1]的(cj,dj)请出去集合
把所有cj=b[i]的请进来集合
(因为cj<=dj所以每个(cj,dj)只能被请进请出一次,均摊O(1))
查询集合中小于bi的最大的dj
比较记录这个dj和目前遇到的最大的(dj-ai)d
最后就剩下一个问题:这个集合要满足请进/请出/范围查询的效率尽量高,那么树状数
组应
该就是个最合适的选择了,三种操作都是logn。这样总复杂度为n^2logn。。。。。。
我天真幼小地心灵一开始以为这是个+/- 1 rmq问题,后来发现数组值是动态的。。 |
p*****2 发帖数: 21240 | 24
你可是太牛了。别的不说了。膜拜一下。
【在 p********s 的大作中提到】 : 还是没考虑成熟,哎面完了人就懒下来了,bz大牛将就看下 : 如前所述如果把正方形预处理成左上和右下两部分,并根据对角线dp,那么对于每条对 : 角线(左上-右下方向)问题可以转化为一维情况。即 : 如果可能的左上角(x0,y0)可以往右往下延伸到(x0+a,y0)和(x0,y0+a),且如果 : 可能的右下角(x0+i,y0+i)可以往左往下延伸到(x0+i-b,y0+i)和(x0+i,y0+i-b) : 则构成正方形,否则不行。一维表示就是 : 用集合{(ai,bi)}表示所有(<=n)条起点为ai,终点为bi的直线,对应于上面的左上角( : ai是y0的值,bi是y0+a) : 用{cj,dj}表示所有条起点为cj,终点为dj的直线,对应上面的右下角(dj是y0+i,cj是 : y0+i-b)
|
p********s 发帖数: 37 | 25 惶恐无地啊。化笨力气想的,也没coding出来过,而且没经ZhangBZ大牛同意的算法都
是错算法。。
【在 p*****2 的大作中提到】 : : 你可是太牛了。别的不说了。膜拜一下。
|
m*****k 发帖数: 731 | 26 should be
, otherwise 0;
1, otherwise 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int d = Math.min(x[i][j], y[i][j]); d >= 1; d--){
int upperLeft_i = i-d+1;
int upperLeft_j = j-d+1;
if (x[upperLeft_i][j] >= d && y[i][upperLeft_j] >= d) { |
Z*****Z 发帖数: 723 | 27 “那么算法描述如下
(1)for i <- y0 to yn
(2)把所有dj=b[i-1]的(cj,dj)请出去集合
(3)把所有cj=b[i]的请进来集合
(因为cj<=dj所以每个(cj,dj)只能被请进请出一次,均摊O(1))
查询集合中小于bi的最大的dj
比较记录这个dj和目前遇到的最大的(dj-ai)d”
对于每个(ai,bi)有集合{(cj',dj')|cj'<=ai,bi>=dj'}
对于这个集合如何update还没看明白。
假设对于i-1,已经有了这样的集合。那么对于i,集合中需要请出去的是bi
点。为什么那些点都包含在(2)中了呢?(我同意你提到的“bi和bi+1之间没有任何
关系”)
我对(3)也有类似的问题,并且更严重,因为(2)中去掉多了点不要紧,(3)中可
以再请回来,但是我现在看不出这样的逻辑来。。。 |
p********s 发帖数: 37 | 28 靠俺又typo了=v=罪过罪过。。
应该是
(2)把所有dj=a[i-1]的(cj,dj)请出去集合
(3)把所有cj=a[i]的请进来集合
意思是(cj,dj)起码必须覆盖a[i],所以(2)是把刚刚已经移动到(ai,bi)左边的(dj=a[i-
1])清除掉,(3)是把能覆盖当前ai的加进来(ci==ai)。
因为ai和dj的有序,所以请进请出的递推关系能够保证(嗯如之前打错的bi的话就没法
保证这个性质了)
总的来说我们一共需要维护两条性质
第一是cj<=ai<=dj,这个是由刚才的递推操作保证的
第二是ai<=dj<=bi,这个是由树状数组的范围查询保证的:
我们知道递推维护的集合已经满足ai<=dj了,所以每个i递推出集合后,只需要查询目
前集合中小于等于bi的最大的dj就行了。。 |
Z*****Z 发帖数: 723 | 29 举个例子,如果:
a[i-1] = 5
b[i-1] = 10
c = 4, d = 9
这是满足你说的两个条件吧?(cj<=ai<=dj和ai<=dj<=bi)
如果
a[i] = 6
b[i] = 7
这个c,d会在(2)里被干掉么?
i-
【在 p********s 的大作中提到】 : 靠俺又typo了=v=罪过罪过。。 : 应该是 : (2)把所有dj=a[i-1]的(cj,dj)请出去集合 : (3)把所有cj=a[i]的请进来集合 : 意思是(cj,dj)起码必须覆盖a[i],所以(2)是把刚刚已经移动到(ai,bi)左边的(dj=a[i- : 1])清除掉,(3)是把能覆盖当前ai的加进来(ci==ai)。 : 因为ai和dj的有序,所以请进请出的递推关系能够保证(嗯如之前打错的bi的话就没法 : 保证这个性质了) : 总的来说我们一共需要维护两条性质 : 第一是cj<=ai<=dj,这个是由刚才的递推操作保证的
|
p********s 发帖数: 37 | 30 会留在集合里吧
但是在查询的时候这个cj,dj不满足dj<=bi,也就是(4,9)虽然在集合里,但是和(6,7)
无法组成一个正方形 |
|
|
Z*****Z 发帖数: 723 | 31 有意思。
你那个集合是怎么实现的?好像要存储二位数据:支持插入;删除;查询在某一个维度
上,为给定值的所有的点;查询某一个维度上,某个范围内所有的点-然后在结果里找
另外一个维度的最大值?
【在 p********s 的大作中提到】 : 会留在集合里吧 : 但是在查询的时候这个cj,dj不满足dj<=bi,也就是(4,9)虽然在集合里,但是和(6,7) : 无法组成一个正方形
|
p********s 发帖数: 37 | 32 插入删除都只要用修改表示就可以了,再就一个范围查询,具体如下
不大明白“某个维度”是指啥,如果问题转化为一维了,只要对于每条对角线建立一个
这样的数据结构就行了。
树状数组http://baike.baidu.com/view/1420784.htm
好像又叫胜者树,其实就是外排序k路归并里用的那个数据结构,很好实现
val[0][]表示原始数据,存着第0..n-1个元素
val[i+1][j]表示val[i][j*2]和val[i][j*2+1]中胜出者(这里比如是更大的那个)的
index
所以最高层val[logn][0]就是0..n-1里面的最终胜出者
设m为小于等于k的最大的2的倍数,则
查询:0..k-1中最大的数就是递归查询(0..m-1)和(m..k)中最大的数,O(logn)
修改:修改val[0][k]的值,并沿着一路修改其祖先的值,O(logn)
初始化:逐层建树,O(n)
这题里对于一条对角线,val[0][]的index就表示dj,值的话如果(cj,dj)进入集合里就
修改为dj,不在就修改为-1。这样如果查询0..bi中的最大的那个元素,就可以获得目
前集合内最大的dj了。。吧。。
【在 Z*****Z 的大作中提到】 : 有意思。 : 你那个集合是怎么实现的?好像要存储二位数据:支持插入;删除;查询在某一个维度 : 上,为给定值的所有的点;查询某一个维度上,某个范围内所有的点-然后在结果里找 : 另外一个维度的最大值?
|
Z*****Z 发帖数: 723 | 33 原来是BIT,我开始想成kdtree了,以为c和d都要存在树里。现在看你意思好像存d就行
了,c可以算出来。
嗯,我没其他问题了,只有一个子:强!
【在 p********s 的大作中提到】 : 插入删除都只要用修改表示就可以了,再就一个范围查询,具体如下 : 不大明白“某个维度”是指啥,如果问题转化为一维了,只要对于每条对角线建立一个 : 这样的数据结构就行了。 : 树状数组http://baike.baidu.com/view/1420784.htm : 好像又叫胜者树,其实就是外排序k路归并里用的那个数据结构,很好实现 : val[0][]表示原始数据,存着第0..n-1个元素 : val[i+1][j]表示val[i][j*2]和val[i][j*2+1]中胜出者(这里比如是更大的那个)的 : index : 所以最高层val[logn][0]就是0..n-1里面的最终胜出者 : 设m为小于等于k的最大的2的倍数,则
|