美籍华人网店老板携317罐外国奶粉进境被查获 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PennySaver - 省钱一族

美籍华人网店老板携317罐外国奶粉进境被查获 (转载)

美籍华人网店老板携317罐外国奶粉进境被查获 (转载)# PennySaver - 省钱一族

s*e2010-09-15 07:09

1 楼

找出一个矩阵里“平衡数”的总个数.“平衡数”的定义：这个数所在row之上所有row
的数字之和=所在row之下所有row的数字之和, 这个数所在column左边所有col的数字之
和=所在col右边所有col的数字之和
时间 O（mxn）空间O（m+n）
请问怎么做？有个思路是：用四个数组，两个和row有关，一个存之上的row数字和，
一个存之下的row数字和，另两个和col相关，同理。
看不懂，谁给解释一下？谢

M*o2010-09-15 07:09

2 楼

【以下文字转载自 ebiz 讨论区】
发信人: kelvinchufei (Kelvin), 信区: ebiz
标题: 美籍华人网店老板携317罐外国奶粉进境被查获
发信站: BBS 未名空间站 (Wed Sep 15 16:26:03 2010, 美东)
中广网厦门9月15日消息（记者周步恒陈庚通讯员汪山刘频苏菲菲）一个“淘宝网
”网店店主日前从国外携带317罐奶粉从厦门进境时，被厦门海关查获。这是我国从今
年9月1日起实施“个人邮递物品进口税”新政后，厦门关区查获的首起利用旅检渠道走
私网购热销物品进境案。
经调查，该女子是美籍华人，在“淘宝网”上经营网店，主要从事各种品牌的婴幼儿奶
粉及用品的国外代购，在携带涉及美赞臣、雅培、雀巢等多个品牌的 317罐外国产奶粉
乘坐纽约经香港至厦门的航班从厦门高崎国际机场进境被海关查获。该女子因9月1日起
国家实施个人邮递物品进口税新政，进货成本提高，为此企图通过随身携带的方式闯关
进境，违反了个人进出境携带物品不得超过自用、合理数量的相关规定。
据海关介绍，随着网购、邮购、海外代购等新兴交易模式迅速发展，一些人将所经营的
进口

J*32010-09-15 07:09

3 楼

四个数组俩前缀和数组，俩后缀和数组，找出和相等的index?

k*y2010-09-15 07:09

4 楼

得，又该被内部消化了，要不就上缴国库，ft。不过这些貌似不够他们消化的啊。
国库是啥东西啊？谁能点拨一下啊，呵呵

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

: 【以下文字转载自 ebiz 讨论区】
: 发信人: kelvinchufei (Kelvin), 信区: ebiz
: 标题: 美籍华人网店老板携317罐外国奶粉进境被查获
: 发信站: BBS 未名空间站 (Wed Sep 15 16:26:03 2010, 美东)
: 中广网厦门9月15日消息（记者周步恒陈庚通讯员汪山刘频苏菲菲）一个“淘宝网
: ”网店店主日前从国外携带317罐奶粉从厦门进境时，被厦门海关查获。这是我国从今
: 年9月1日起实施“个人邮递物品进口税”新政后，厦门关区查获的首起利用旅检渠道走
: 私网购热销物品进境案。
: 经调查，该女子是美籍华人，在“淘宝网”上经营网店，主要从事各种品牌的婴幼儿奶
: 粉及用品的国外代购，在携带涉及美赞臣、雅培、雀巢等多个品牌的 317罐外国产奶粉

c*p2010-09-15 07:09

5 楼

mark

x*u2010-09-15 07:09

6 楼

wow!
317! how can she fit in all these in her suitcases?

s*e2010-09-15 07:09

7 楼

什么意思？
假设 matrix: A[i,j], 这四个数组分别是什么？

【在 J****3 的大作中提到】

: 四个数组俩前缀和数组，俩后缀和数组，找出和相等的index?

k*y2010-09-15 07:09

8 楼

一个人带那么多,够强的了

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

w*a2010-09-15 07:09

9 楼

设置两个数组，分别代表某一行及以上所有数字之和，某一列及以左边所有数字之和。
然后可以o(1)求出某一行上面的和是否等于下面的和。列也是同理。
然后一次MxN扫描可以找出这个平衡数。
需要注意的溢出情况。
这是电面题么？

b*92010-09-15 07:09

10 楼

5000rmb以内
按coupon前还是coupon后算?

q*o2010-09-15 07:09

11 楼

mark

s*r2010-09-15 07:09

12 楼

牛的
那些飞国际航班的机组人员是不是可以放心带啊
安检都放水吧

t*r2010-09-15 07:09

13 楼

mark

row
★ 发自iPhone App: ChineseWeb 7.8

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

: 找出一个矩阵里“平衡数”的总个数.“平衡数”的定义：这个数所在row之上所有row
: 的数字之和=所在row之下所有row的数字之和, 这个数所在column左边所有col的数字之
: 和=所在col右边所有col的数字之和
: 时间 O（mxn）空间O（m+n）
: 请问怎么做？有个思路是：用四个数组，两个和row有关，一个存之上的row数字和，
: 一个存之下的row数字和，另两个和col相关，同理。
: 看不懂，谁给解释一下？谢

j*a2010-09-15 07:09

14 楼

估计是按国内市场价来算的，5000的话可能20灌不到吧！

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

: 5000rmb以内
: 按coupon前还是coupon后算?

s*e2010-09-15 07:09

15 楼

懂了。题意理解错了。我还以为平衡数是指这个数上面
这个数所在row之上所有在这一列的row。。。
在准备店面。

【在 w****a 的大作中提到】

: 设置两个数组，分别代表某一行及以上所有数字之和，某一列及以左边所有数字之和。
: 然后可以o(1)求出某一行上面的和是否等于下面的和。列也是同理。
: 然后一次MxN扫描可以找出这个平衡数。
: 需要注意的溢出情况。
: 这是电面题么？

t*s2010-09-15 07:09

16 楼

LOL. zan pennysaver's mindset

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

: 5000rmb以内
: 按coupon前还是coupon后算?

A*l2010-09-15 07:09

17 楼

假设n * m 矩阵，子矩阵(n - 2) * m 全是0，比如
0 0 ... 0
0 0 ... 0
........
0 0 ... 0
1 1 ... 1
2 2 ... 2
如果先扫描行，那么在第一行，所有的0都是candidate，然后需要扫描所有的列。这
样在第一行需要O(n * m)的操作。
如果只设置两个数组的话，在扫描第二行的时候，还是需要O(n * m)的操作, 因为之前
的列和没有存下来。
最后的复杂度是O(n ^ 2 *m) ?
是否需要把第一次行扫描的时候，把列号存下来（Mapnumber>>），然后按照列号计算列和，避免重复计算?

【在 w****a 的大作中提到】

G*82010-09-15 07:09

18 楼

这也太猖狂了，不是找抓吗？有这么笨的人，摇头。

s*e2010-09-15 07:09

19 楼

不懂你的意思。应该是：
UP = (0,0,0,0,0,4) (竖着看)
Down = (12,12,12,12,8,0) (竖着看)
Left = (0,3,6,9)
Right = (9,6,3,0)
A[i,j]:
if Up[0]+...Up[i-1] == Down[i+1]+...Down[n-1]
&& Left[0]+..Left[j-1] == Left[j+1]...Left[m-1]
then A[i,j] is balance number

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

: 假设n * m 矩阵，子矩阵(n - 2) * m 全是0，比如
: 0 0 ... 0
: 0 0 ... 0
: ........
: 0 0 ... 0
: 1 1 ... 1
: 2 2 ... 2
: 如果先扫描行，那么在第一行，所有的0都是candidate，然后需要扫描所有的列。这
: 样在第一行需要O(n * m)的操作。
: 如果只设置两个数组的话，在扫描第二行的时候，还是需要O(n * m)的操作, 因为之前

f*w2010-09-15 07:09

20 楼

好笨啊，既然到了香港，先通关啊

A*l2010-09-15 07:09

21 楼

题目理解错了。我原以为是这个平衡数的定义：所在列上部分的列和等于下部分的列
和，所在行左部分的列和等于有部分的列和。
懂你的意思了，是所有上部分的行和and下部分的行和，以及所有左部分的列和and有部
分的列和

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

: 不懂你的意思。应该是：
: UP = (0,0,0,0,0,4) (竖着看)
: Down = (12,12,12,12,8,0) (竖着看)
: Left = (0,3,6,9)
: Right = (9,6,3,0)
: A[i,j]:
: if Up[0]+...Up[i-1] == Down[i+1]+...Down[n-1]
: && Left[0]+..Left[j-1] == Left[j+1]...Left[m-1]
: then A[i,j] is balance number

M*o2010-09-15 07:09

22 楼

啥意思？

【在 f*******w 的大作中提到】

: 好笨啊，既然到了香港，先通关啊

l*32010-09-15 07:09

23 楼

row
扫描，得到每行每列的和，并计算全部行列和,say, S. O(mn)time, O(m+n)space。
扫描行，每扫一行，累计在它上面的行的总和，在它下面的行的总和＝S-上面行总和-
本行和。扫描列同理。O(m+n)time, O(m+n) space
输出所有的平衡数： brute force, O(mn) time.

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

f*w2010-09-15 07:09

24 楼

从陆路到深圳再飞吗，那就查的没那么严了呀，直接飞飞机，找查嘛

M*s2010-09-15 07:09

25 楼

注意
1.Up[0]+...Up[i-1] == Down[i+1]+...Down[n-1]只与i相关
2.Left[0]+..Left[j-1] == Left[j+1]...Left[m-1]只与j相关
故1式成立时，称i行为平衡行
当2式成立时，称j行为平衡列
行列的关系彼此独立，故平衡数总个数=平衡行数*平衡列数
剩下就是一些实作细节问题
其实只要记住每行每列和，在迴圈中就可判断是否为平衡行列了
下面是O(m+n) space, O(m*n) time的实作
其实还满简单的，只是稍长了些
int balancingCells(vector >& matrix) {
if (matrix.empty()) return 0;
int nRow = matrix.size(), nCol = matrix[0].size();
vector rowSum(nRow, 0), colSum(nCol, 0);
int total = 0;
for (int r=0; rfor (int c=0; cint value = matrix[r][c];
rowSum[r] += value; //每列和
colSum[c] += value; //每行和
total += value; //所有数总和
}
}
//计算平衡列数
int up=0, down=total, balancingRow=0;
for (int r=0; rdown -= rowSum[r]; //down为r列以下所有数总和
if (up==down) ++balancingRow;
up += rowSum[r]; //up为r列以上所有数总和
}
//计算平衡行数
int left=0, right=total, balancingCol=0;
for (int c=0; cright -= colSum[c];
if (left==right) ++balancingCol;
left += colSum[c];
}
return balancingRow * balancingCol;
}
延伸讨论一下
这题可以在O(1) space, O(n*m) time完成
但需要scan整个matrix 3次(2 row scan, 1 column scan)
可能会有很大的L1/L2 cache miss时间开销(尤其是column scan)
通常还是以空间换取时间为佳
以下为O(1) space, O(n*m) time的实作
int balancingCellsConstantSpace(vector >& matrix) {
if (matrix.empty()) return 0;
int nRow = matrix.size(), nCol = matrix[0].size();
int total = 0;
// row scan, 计算整个matrix总和
for (int r=0; rfor (int c=0; cint value = matrix[r][c];
total += value;
}
}
// row scan, 计算平衡列数
int up=0, down=total, balancingRow=0;
for (int r=0; rint rowSum = 0;
for (int c=0; cdown -= rowSum;
if (up==down) ++balancingRow;
up += rowSum;
}
// column scan, 计算平衡行数
int left=0, right=total, balancingCol=0;
for (int c=0; cint colSum = 0;
for (int r=0; rright -= colSum;
if (left==right) ++balancingCol;
left += colSum;
}
return balancingRow * balancingCol;
}

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