FNM - 未名空间MITBBS历史存档

b*u2010-04-23 07:04

1 楼

从怀孕到生产，到坐月子，我都是尽量一个人把事情搞定。
怀孕期间，老公从来没和我一起去医院检查，直到最后一天，才见到OB.
生孩子的时候，开了4指，已经疼的快死过去了，周围护士医生都让我赶快给老公电话
让他过来，我才又拖了半小时，然后把老公电话叫来。原因是当时是半夜，我想让老公
多睡会
孩子生完后，老公在家照顾我2个礼拜，之后的月子是我自己做的，没人帮忙。对付一
个新生婴儿有多劳累，多困难，当爹妈的人最清楚。老公晚上也能帮我，但是胸喂宝宝
等等这样的事情只有咱们妇女同志才能担当。平时白天拍嗝，尽量的收拾卫生等等的，
我这月子压根没做。
刚刚出月子2天，老公昨晚和同事出去Party了，弄得我一个人在家给宝宝洗澡，哄睡。
。然后，我自己还不能睡，要等老公回来一起睡，否则我就是心里不踏实。一直到11点
多钟。
今天我和宝宝有两个预约，我怕是赶不上了
昨晚老公回来后，我暴跳如雷，把这些陈年旧帐都翻出来数落他。晚上睡觉的时候梦到
了公公婆婆，梦里的他们一样气得我牙齿咯咯的响。昨晚我抑郁了
有时候，为了让老公好好休息，好好工作，我宁可大包大揽一些，虽然我也是全职工作
。但是，作了很多之后，免不了会抱怨。咳！而我很能干，老公就习以为常了。虽然老
公也尽量的帮我，可是很多时候我还是不平衡。。
刚才老公跟我说，他向单位请了半天假，为了带宝宝去医院的预约。然后又说，你做什
么事情可以和我商量，不要象昨晚那样发那么大脾气
我惭愧了，是呀，很多时候，我的确很泼妇。

y*o2010-04-23 07:04

2 楼

一个N * M 矩阵A，里面的值是1或0，现在求矩阵里面子矩阵(square)最大边长L，满足
1. 0 < L <= min(N, M),
2. 0 <= X <= N - L,
3. 0 <= Y <= M - L,
4. A[X + I][Y + J] = 1 for all 0 <= I < L and 0 <= J < L.
5. 子矩阵能够移动, 从(X, Y)移动到(X + 1, Y)或者(X, Y + 1)
同时满足子矩阵能从左上角(0, 0)走到右下角(N - L, M - L)，
即求能从左上角走到右下角的子矩阵边长最大，使子矩阵任何时刻里面全部是1,有则返
回L，没有返回0
For example, given array A:
1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 1
0 1 1 1
1 0 1 1
the function should return 2.
Given array A:
1 1 0 0
1 0 0 0
0 1 0 1
the function should return 0.
Given array A:
1
the function should return 1.
要求时间O(N * M * log(N + M)), 空间O(N * M)
求大神指点

i*62010-04-23 07:04

3 楼

不建议交易打印胖子；胖子是免费的，收费的是服务:
出售/交换物品的名称:
RA HUGGIES VVQ
物品类别（coupon：mfc等；血糖仪等）:
RA HUGGIES VVQ 2 0ff
物品来源（报纸夹页，厂家邮寄等）:
可接受的价格（必须明码标价，必填）:
2baozi/each
邮寄损失方式哪方承担（若需邮寄，必填）:
付款方式说明:
本贴有效期（必填）:
联系方式（例：站内）:

s*r2010-04-23 07:04

4 楼

so piggy, good to reload?

L*92010-04-23 07:04

5 楼

Abstract：全职老婆出月子(无人帮忙)两天独自带孩子，老公自顾自去party到半夜。
My comments：
1. 假如你非要作践自己宠坏你老公，外人表示彻底无语。
2. 建议转NextGeneration,那里的姐妹会有办法的。

l*82010-04-23 07:04

6 楼

L是边长吧？

【在 y******o 的大作中提到】

: 一个N * M 矩阵A，里面的值是1或0，现在求矩阵里面子矩阵(square)最大边长L，满足
: 1. 0 < L <= min(N, M),
: 2. 0 <= X <= N - L,
: 3. 0 <= Y <= M - L,
: 4. A[X + I][Y + J] = 1 for all 0 <= I < L and 0 <= J < L.
: 5. 子矩阵能够移动, 从(X, Y)移动到(X + 1, Y)或者(X, Y + 1)
: 同时满足子矩阵能从左上角(0, 0)走到右下角(N - L, M - L)，
: 即求能从左上角走到右下角的子矩阵边长最大，使子矩阵任何时刻里面全部是1,有则返
: 回L，没有返回0
: For example, given array A:

l*n2010-04-23 07:04

7 楼

LOAD吧。因为我已经UNLOAD了。被我UNLOAD的一般都会暴涨

x*u2010-04-23 07:04

8 楼

说句可能不当的话
楼主可能有自虐倾向，或者叫“委屈自己以让别人内疚”
生孩子这么大的事儿，非得晚半个小时才叫他来，一辈子少睡这么一两次半个小时不会
死人。
然后你出月子了，你老公出去应酬朋友，他不回来你就不睡。。。太典型了
做你老公压力很大

y*o2010-04-23 07:04

9 楼

是的，我写错了，是边长

【在 l*********8 的大作中提到】

: L是边长吧？

s*r2010-04-23 07:04

10 楼

haha, good credit, just loaded 10K shares again

【在 l********n 的大作中提到】

: LOAD吧。因为我已经UNLOAD了。被我UNLOAD的一般都会暴涨

a*s2010-04-23 07:04

11 楼

有事就说别憋着憋大了一起爆发这才叫恐怖
你老公那样，一半是被你宠坏的嘛，所以自己也有问题，他该做的就告诉他，别你替他
干了，回来再数落他，这是何必呢

y*o2010-04-23 07:04

12 楼

求解

l*n2010-04-23 07:04

13 楼

赚到了的话发包子给我吧，因为我是割得。。。

a*02010-04-23 07:04

14 楼

不明白妹妹为什么这么不把自己当人。你说的事情太极品了。生孩子这样的大事还考虑
老公睡觉的问题。不能理解。

R*i2010-04-23 07:04

15 楼

这个题感觉很有难度。第一步大概是扫描整个M*N的矩阵，把以它为左上角的最大非零
方阵的尺寸存成另外一个矩阵，接下来是找连通，这一步我还没有想明白。

g*l2010-04-23 07:04

16 楼

现在大盘上下拨动的厉害，想LOAD有更好的机会

G*L2010-04-23 07:04

17 楼

家是俩人的，孩子是俩人的，谁大包大拦都不work

【在 b****u 的大作中提到】

: 从怀孕到生产，到坐月子，我都是尽量一个人把事情搞定。
: 怀孕期间，老公从来没和我一起去医院检查，直到最后一天，才见到OB.
: 生孩子的时候，开了4指，已经疼的快死过去了，周围护士医生都让我赶快给老公电话
: 让他过来，我才又拖了半小时，然后把老公电话叫来。原因是当时是半夜，我想让老公
: 多睡会
: 孩子生完后，老公在家照顾我2个礼拜，之后的月子是我自己做的，没人帮忙。对付一
: 个新生婴儿有多劳累，多困难，当爹妈的人最清楚。老公晚上也能帮我，但是胸喂宝宝
: 等等这样的事情只有咱们妇女同志才能担当。平时白天拍嗝，尽量的收拾卫生等等的，
: 我这月子压根没做。
: 刚刚出月子2天，老公昨晚和同事出去Party了，弄得我一个人在家给宝宝洗澡，哄睡。

y*o2010-04-23 07:04

18 楼

是呀，我也卡在找连通这里

【在 R*****i 的大作中提到】

: 这个题感觉很有难度。第一步大概是扫描整个M*N的矩阵，把以它为左上角的最大非零
: 方阵的尺寸存成另外一个矩阵，接下来是找连通，这一步我还没有想明白。

l*n2010-04-23 07:04

19 楼

之前看了您的贴，还挺有信心的，但是最近金融震荡太厉害了，忍不住把这只猪给割了

【在 g***l 的大作中提到】

: 现在大盘上下拨动的厉害，想LOAD有更好的机会

z*t2010-04-23 07:04

20 楼

是, you spoiled him

e*l2010-04-23 07:04

21 楼

二维dp, 设dp(i j)为子矩阵0,0到i, j上的解,
它依赖于dp (i-1, j) 和dp (i, j-1)。只需要检查多出来的行或列, 而且可以预先算
好连续1的数目, 这一步应该是常数时间。

h*e2010-04-23 07:04

22 楼

..fnm这种股只能dip的时候买。。而且别一次买齐了。。吃一堑长一智

【在 l********n 的大作中提到】

: 赚到了的话发包子给我吧，因为我是割得。。。

a*32010-04-23 07:04

23 楼

平时把问题好好讲讲，不要憋着一起发泄出来

e*l2010-04-23 07:04

24 楼

假设row (i j)是从点(i j)向左最长的连续1的数目, 可以在o (mn)时间内求出所有的
row (i j). 同样求出col(i j).
则dp (i j) = max ( min (dp (i-1, j), col (i, j)), min (dp (i, j-1), row (i
, j)))

g*l2010-04-23 07:04

25 楼

割了买什么能给你赚钱啊

【在 l********n 的大作中提到】

: 之前看了您的贴，还挺有信心的，但是最近金融震荡太厉害了，忍不住把这只猪给割了

N*72010-04-23 07:04

26 楼

自己都不把自己当人的人，别人是不会把你当人的
连在这里抱怨的资格都显得可笑，我一点也不同情你

c*y2010-04-23 07:04

27 楼

DP好难，我来贴个无脑的，不知道题目理解对了没有。。
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int findMaxAllOneTopLeftSquare(vector>& matrix)
{
int i, j;
int m = matrix.size(); if (!m) return 0;
int n = matrix[0].size(); if (!n) return 0;
int max = min(m, n);

for (i=0; ifor (j=0; j<=i; j++){
if (matrix[i][j] == 0 || matrix[j][i] == 0){
return i;
}
}
}
return i;
}
bool isAbleToMoveToRightDown(vector>& matrix, int& L, int y1,
int x1, int y2, int x2)
{
cout << L << ", (" << y1 << ", " << x1 << "), (" << y2 << ", " << x2 <<
")" << endl;
if (y1 == y2 && x1 == x2) return true;
int i;
bool bRight = true, bDown = true;
// check right
if (x1 < x2){
for (i=0; iif (matrix[y1+i][x1+L] == 0){
bRight = false;
break;
}
}
}
else{
bRight = false;
}
// check down
if (y1 < y2){
for (i=0; iif (matrix[y1+L][x1+i] == 0){
bDown = false;
break;
}
}
}
else{
bDown = false;
}

return bRight && isAbleToMoveToRightDown(matrix, L, y1, x1+1, y2, x2
) || bDown && isAbleToMoveToRightDown(matrix, L, y1+1, x1, y2, x2);

}
int main (int argc, char** argv) {

vector> matrix;
matrix.push_back({1, 1, 1, 0});
matrix.push_back({1, 1, 1, 0});
matrix.push_back({1, 1, 1, 0});
matrix.push_back({1, 1, 1, 0});
matrix.push_back({0, 0, 1, 1});
matrix.push_back({1, 0, 1, 1});

int L = findMaxAllOneTopLeftSquare(matrix);
int i;
int m = matrix.size(); if (!m) return 0;
int n = matrix[0].size(); if (!n) return 0;
cout << "m = " << m << endl;
cout << "n = " << n << endl;
cout << "L = " << L << endl;

for (i=L; i>=1; i--){
cout << "i = " << i << endl;
if (isAbleToMoveToRightDown(matrix, i, 0, 0, m-i, n-i)){
break;
}
}
cout << "Min L for square is " << i << endl;

return 0;
}

l*n2010-04-23 07:04

28 楼

因为本钱小啊。
现在金融板块什么火就DT什么
现在不是小银行嘛

【在 g***l 的大作中提到】

: 割了买什么能给你赚钱啊

N*72010-04-23 07:04

29 楼

再说得不好听点：你老公又找了位妈

l*62010-04-23 07:04

30 楼

build a matrix of N by M, each cell contain a number as the bigest square
with all 1 end at this cell using DP
Mat[i][j] = 0 if src[i][j] == 0
max(Mat[i][j - 1] , Mat[i - 1][j] , Mat[i - 1][j - 1]) + 1
otherwise
start from right bottom cell, do binary search from 1 to Mat[M - 1][N - 1]
each itaration, with value i, using bfs/dfs to check if there is a path from
Mat[M - 1][N - 1] to Mat[i - 1][i - 1], a path is connected if Mat[x][y] >=
i;
Space : M * N
time: binary iteration log(M + N)
each iteration, bfs/dfs worst time M*N total M*N*log(M + N)

y*e2010-04-23 07:04

31 楼

女人要多撒娇才行
你太强悍了
总有一天你老公会无聊地去保护更加需要保护的MM的
到时候你就欲哭无泪了

【在 b****u 的大作中提到】

: 从怀孕到生产，到坐月子，我都是尽量一个人把事情搞定。
: 怀孕期间，老公从来没和我一起去医院检查，直到最后一天，才见到OB.
: 生孩子的时候，开了4指，已经疼的快死过去了，周围护士医生都让我赶快给老公电话
: 让他过来，我才又拖了半小时，然后把老公电话叫来。原因是当时是半夜，我想让老公
: 多睡会
: 孩子生完后，老公在家照顾我2个礼拜，之后的月子是我自己做的，没人帮忙。对付一
: 个新生婴儿有多劳累，多困难，当爹妈的人最清楚。老公晚上也能帮我，但是胸喂宝宝
: 等等这样的事情只有咱们妇女同志才能担当。平时白天拍嗝，尽量的收拾卫生等等的，
: 我这月子压根没做。
: 刚刚出月子2天，老公昨晚和同事出去Party了，弄得我一个人在家给宝宝洗澡，哄睡。

h*e2010-04-23 07:04

32 楼

以size 搜索通路bfs 每次移动增加　2* size ，O(M*N) 然后　二分size O(log min(m
, n))

b*y2010-04-23 07:04

33 楼

是你的问题
生孩子为啥不叫醒他一起来医院，兴许你老公还抱怨错过了和你一起担当的时刻呢。
月子累可以适当请个保姆，你不讲出来，男人心粗不一定能体会到。

f*e2010-04-23 07:04

34 楼

题目都看晕了，这个是面试题吗？

【在 y******o 的大作中提到】

: 一个N * M 矩阵A，里面的值是1或0，现在求矩阵里面子矩阵(square)最大边长L，满足
: 1. 0 < L <= min(N, M),
: 2. 0 <= X <= N - L,
: 3. 0 <= Y <= M - L,
: 4. A[X + I][Y + J] = 1 for all 0 <= I < L and 0 <= J < L.
: 5. 子矩阵能够移动, 从(X, Y)移动到(X + 1, Y)或者(X, Y + 1)
: 同时满足子矩阵能从左上角(0, 0)走到右下角(N - L, M - L)，
: 即求能从左上角走到右下角的子矩阵边长最大，使子矩阵任何时刻里面全部是1,有则返
: 回L，没有返回0
: For example, given array A:

w*s2010-04-23 07:04

35 楼

我生孩子的时候也最后才叫老公的。因为不知道要持续多久，想他多睡会儿可以打持久
战。

y*o2010-04-23 07:04

36 楼

from
>=
start from right bottom cell, do binary search from 1 to Mat[M - 1][N - 1]
没明白，能具体解释一下吗

【在 l******6 的大作中提到】

: build a matrix of N by M, each cell contain a number as the bigest square
: with all 1 end at this cell using DP
: Mat[i][j] = 0 if src[i][j] == 0
: max(Mat[i][j - 1] , Mat[i - 1][j] , Mat[i - 1][j - 1]) + 1
: otherwise
: start from right bottom cell, do binary search from 1 to Mat[M - 1][N - 1]
: each itaration, with value i, using bfs/dfs to check if there is a path from
: Mat[M - 1][N - 1] to Mat[i - 1][i - 1], a path is connected if Mat[x][y] >=
: i;
: Space : M * N

F*P2010-04-23 07:04

37 楼

非常有道理

【在 x*****u 的大作中提到】

: 说句可能不当的话
: 楼主可能有自虐倾向，或者叫“委屈自己以让别人内疚”
: 生孩子这么大的事儿，非得晚半个小时才叫他来，一辈子少睡这么一两次半个小时不会
: 死人。
: 然后你出月子了，你老公出去应酬朋友，他不回来你就不睡。。。太典型了
: 做你老公压力很大

l*62010-04-23 07:04

38 楼

The final answer, must be a value between 0 and Mat[M - 1][N - 1]
let low = 1 high = Mat[M - 1][N - 1]
using binary search to find that value . If a value i is working , there
must be a path between Mat[i - 1][i - 1] and Mat[M - 1][N - 1] with all the
cell value greater or equal to i
If such path exists, search between i + 1 and high for next i
otherwise search between low and i - 1 for next i;
for a i to determine whether the path exists , using bfs/dfs

【在 y******o 的大作中提到】

:
: from
: >=
: start from right bottom cell, do binary search from 1 to Mat[M - 1][N - 1]
: 没明白，能具体解释一下吗

m*d2010-04-23 07:04

39 楼

多让老公干活，保持良好心情

【在 b****u 的大作中提到】

: 从怀孕到生产，到坐月子，我都是尽量一个人把事情搞定。
: 怀孕期间，老公从来没和我一起去医院检查，直到最后一天，才见到OB.
: 生孩子的时候，开了4指，已经疼的快死过去了，周围护士医生都让我赶快给老公电话
: 让他过来，我才又拖了半小时，然后把老公电话叫来。原因是当时是半夜，我想让老公
: 多睡会
: 孩子生完后，老公在家照顾我2个礼拜，之后的月子是我自己做的，没人帮忙。对付一
: 个新生婴儿有多劳累，多困难，当爹妈的人最清楚。老公晚上也能帮我，但是胸喂宝宝
: 等等这样的事情只有咱们妇女同志才能担当。平时白天拍嗝，尽量的收拾卫生等等的，
: 我这月子压根没做。
: 刚刚出月子2天，老公昨晚和同事出去Party了，弄得我一个人在家给宝宝洗澡，哄睡。

e*l2010-04-23 07:04

40 楼

1, 1, 1
0, 0, 1
0, 0, 1
Mat[M-1][N-1]是0，Mat[M][N]是1.
the

g*02010-04-23 07:04

41 楼

你自己愿意的，抱怨什么啊？

l*62010-04-23 07:04

42 楼

I think index is usually 0 based

【在 e***l 的大作中提到】

: 1, 1, 1
: 0, 0, 1
: 0, 0, 1
: Mat[M-1][N-1]是0，Mat[M][N]是1.
: the

h*12010-04-23 07:04

43 楼

你劳工没提出来陪你吗？

e*l2010-04-23 07:04

44 楼

我是说你的dp不对。递推只和上面和左边的位置有关, 跟斜上方的无关

【在 l******6 的大作中提到】

:
: I think index is usually 0 based

h*t2010-04-23 07:04

45 楼

跟自己LG客气啥呀...
我LG工作很忙,但是每次检查他都去.
要生的时候他24小时待命.
生宝宝,宝妈已经很辛苦了,宝爸付出点不是太正常不过了吗.
辛苦点也幸福不是么.

b*d2010-04-23 07:04

46 楼

这叫自作孽不可活。你要自虐没办法啊！

a*a2010-04-23 07:04

47 楼

大男人，有力气，你干嘛这么宠他，自己自虐阿。

j*a2010-04-23 07:04

48 楼

你做到了100，就不要不好意思要求对方做到100
这个没啥的
没见很多人，自己做50，却很好意思开口要对方做100的么

J*b2010-04-23 07:04

49 楼

觉得你老公挺懂事。他知道你需要，就请半天假。

【在 b****u 的大作中提到】

: 从怀孕到生产，到坐月子，我都是尽量一个人把事情搞定。
: 怀孕期间，老公从来没和我一起去医院检查，直到最后一天，才见到OB.
: 生孩子的时候，开了4指，已经疼的快死过去了，周围护士医生都让我赶快给老公电话
: 让他过来，我才又拖了半小时，然后把老公电话叫来。原因是当时是半夜，我想让老公
: 多睡会
: 孩子生完后，老公在家照顾我2个礼拜，之后的月子是我自己做的，没人帮忙。对付一
: 个新生婴儿有多劳累，多困难，当爹妈的人最清楚。老公晚上也能帮我，但是胸喂宝宝
: 等等这样的事情只有咱们妇女同志才能担当。平时白天拍嗝，尽量的收拾卫生等等的，
: 我这月子压根没做。
: 刚刚出月子2天，老公昨晚和同事出去Party了，弄得我一个人在家给宝宝洗澡，哄睡。

w*o2010-04-23 07:04

50 楼

r u freaking kidding me? 你老公那是纯属被你宠的吧？女人就应该显示你软弱的一
面的，你自己啥都干了，男人更觉得你要我干嘛？

H*H2010-04-23 07:04

51 楼

我倒不是特别同情你老公，反正看他的处理方式还算可以。我挺同情你的孩子。因为有
一个喜欢用内疚感操纵他人的妈妈，他会过得非常不快乐，还以为是自己的错

t*g2010-04-23 07:04

52 楼

你老公不错了，能帮忙，发现问题了，立刻有改观。
你有话要直说，不要太要强。

【在 b****u 的大作中提到】

: 从怀孕到生产，到坐月子，我都是尽量一个人把事情搞定。
: 怀孕期间，老公从来没和我一起去医院检查，直到最后一天，才见到OB.
: 生孩子的时候，开了4指，已经疼的快死过去了，周围护士医生都让我赶快给老公电话
: 让他过来，我才又拖了半小时，然后把老公电话叫来。原因是当时是半夜，我想让老公
: 多睡会
: 孩子生完后，老公在家照顾我2个礼拜，之后的月子是我自己做的，没人帮忙。对付一
: 个新生婴儿有多劳累，多困难，当爹妈的人最清楚。老公晚上也能帮我，但是胸喂宝宝
: 等等这样的事情只有咱们妇女同志才能担当。平时白天拍嗝，尽量的收拾卫生等等的，
: 我这月子压根没做。
: 刚刚出月子2天，老公昨晚和同事出去Party了，弄得我一个人在家给宝宝洗澡，哄睡。

L*i2010-04-23 07:04

53 楼

活的任性一点你自在你身边的人也自在……

p*52010-04-23 07:04

54 楼

他对孩子和你照顾越多，他越珍惜这个家。
告诉他你很累，告诉他你很弱，要他帮助。
（如果你说的这些算泼妇，我比你更泼。）

h*12010-04-23 07:04

55 楼

非常同意，guilty cards play多了都sick...

【在 H*H 的大作中提到】

: 我倒不是特别同情你老公，反正看他的处理方式还算可以。我挺同情你的孩子。因为有
: 一个喜欢用内疚感操纵他人的妈妈，他会过得非常不快乐，还以为是自己的错

k*x2010-04-23 07:04

56 楼

同意。男人需适当地给点被依赖的感觉，
他们觉得特别自豪，做事儿就热情高涨。

【在 y********e 的大作中提到】

: 女人要多撒娇才行
: 你太强悍了
: 总有一天你老公会无聊地去保护更加需要保护的MM的
: 到时候你就欲哭无泪了

N*72010-04-23 07:04

57 楼

挺好的老公呀，是你自己做得不好。不是什么事都你做了就是最好的solution，要不就
不是一个家了。

w*y2010-04-23 07:04

58 楼

恩，跟我妈很像，所以我现在什么都不敢让她帮我做，免得到时候对不起她～