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的倍数，则
|
