想不通啊 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>pets - 心有所宠

想不通啊

想不通啊# pets - 心有所宠

v*32011-09-18 07:09

1 楼

1. 求A to the power of B，然后modulo C的结果。A, B, C都可能是很大的整数。要
求时间O（logB）
2. merge两个list的时间是两个list里的元素个数之和。给一个array of integers，
每一个integer表示一个list的元素数，求最小的时间把所有的list merge起来。比如
说［300, 100, 200］，可能的merge时间是先merge前两个300＋100, 然后merge （
400＋200）。
第二道应该是一个很经典的题目，由于刚开始找工作，准备不足，水平撮，结果挂在第
二道题上。求拍。。。

I*e2011-09-18 07:09

2 楼

都说狗是从狼训练出来的
GSD, husky看着还有点儿影子， GR， lab也将就吧
这些小狗, 比如pug, 怎么看也无法和狼联系起来啊

t*a2011-09-18 07:09

3 楼

数论太烂。第一题怎么做呢？
第二题感觉是先从小到大排序以后顺着merge过来，这样最大的数字被merge最少，损失
最小。你觉得呢？

b*i2011-09-18 07:09

4 楼

跳坑。

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

: 都说狗是从狼训练出来的
: GSD, husky看着还有点儿影子， GR， lab也将就吧
: 这些小狗, 比如pug, 怎么看也无法和狼联系起来啊

p*g2011-09-18 07:09

5 楼

第二题没看懂意思

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

: 1. 求A to the power of B，然后modulo C的结果。A, B, C都可能是很大的整数。要
: 求时间O（logB）
: 2. merge两个list的时间是两个list里的元素个数之和。给一个array of integers，
: 每一个integer表示一个list的元素数，求最小的时间把所有的list merge起来。比如
: 说［300, 100, 200］，可能的merge时间是先merge前两个300＋100, 然后merge （
: 400＋200）。
: 第二道应该是一个很经典的题目，由于刚开始找工作，准备不足，水平撮，结果挂在第
: 二道题上。求拍。。。

I*e2011-09-18 07:09

6 楼

严肃点儿，打劫呢

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

: 跳坑。

t*22011-09-18 07:09

7 楼

第二题表达有问题，如果按字面，array里的数加起来就是

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

A*a2011-09-18 07:09

8 楼

从狼”训练“出来？

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

: 都说狗是从狼训练出来的
: GSD, husky看着还有点儿影子， GR， lab也将就吧
: 这些小狗, 比如pug, 怎么看也无法和狼联系起来啊

p*92011-09-18 07:09

9 楼

不知道对不对
(1) 设A=kC+x，那么A^B % C = (kC + x)^B % C= x^B % C = (x^(B/2) )^2 % C = (x
^(B /2)%C)^2 = ... O(logn)求得结果
(2) 维护一个堆，每次拿出最小的两个，再把生成的结果放回去，O(nlogn)

B*t2011-09-18 07:09

10 楼

黎叔表示很鄙视啊，打劫这种事太没技术含量了。

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

: 严肃点儿，打劫呢

v*32011-09-18 07:09

11 楼

不好意思，可能表达的不清楚。比如说[100, 200, 400]，merge的时间有三种，先
merge前两个需要（100＋200）＝300,然后merge第三个是（300＋400）＝700，一共需
要300＋700 ＝ 1000.。或者先merge后两个需要（200＋400）＝600,然后merge第一个
是（100＋600）＝700,一共需要600＋700＝1300. 或者是先merge第一个和第三个，过
程类似。求最小可能的时间。

【在 t*******2 的大作中提到】

: 第二题表达有问题，如果按字面，array里的数加起来就是

I*e2011-09-18 07:09

12 楼

不是吗？

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

: 从狼”训练“出来？

g*e2011-09-18 07:09

13 楼

典型DP

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

: 不好意思，可能表达的不清楚。比如说[100, 200, 400]，merge的时间有三种，先
: merge前两个需要（100＋200）＝300,然后merge第三个是（300＋400）＝700，一共需
: 要300＋700 ＝ 1000.。或者先merge后两个需要（200＋400）＝600,然后merge第一个
: 是（100＋600）＝700,一共需要600＋700＝1300. 或者是先merge第一个和第三个，过
: 程类似。求最小可能的时间。

B*t2011-09-18 07:09

14 楼

恩，当年悟空就是拜师学艺以后就能72变了

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

: 从狼”训练“出来？

f*72011-09-18 07:09

15 楼

第二题，不就是经典贪心算法嘛，建最小堆，反复取最小两个，相加后push进堆，直到
堆为空。

B*t2011-09-18 07:09

16 楼

认真的说啊，看过一个科教片，说是狗的基因很特别，大小，毛色和种种特性都由某
些个基因控制，这些基因可以在很少的几代内通过杂交改变，狗是同一种类大小可以差
别最大的物种之一了。举个例子是说，俄罗斯机场老被炸，他们就找各种有他们需要的
特性的狗培育出一种特殊的能闻出很多种炸药的成分的狗，当然也是好几十年才培育出
的了。好像很多国家想跟他们买，他们还不卖。

t*22011-09-18 07:09

17 楼

正解

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

: 第二题，不就是经典贪心算法嘛，建最小堆，反复取最小两个，相加后push进堆，直到
: 堆为空。

A*a2011-09-18 07:09

18 楼

pbs的那个纪录片。

【在 B****t 的大作中提到】

: 认真的说啊，看过一个科教片，说是狗的基因很特别，大小，毛色和种种特性都由某
: 些个基因控制，这些基因可以在很少的几代内通过杂交改变，狗是同一种类大小可以差
: 别最大的物种之一了。举个例子是说，俄罗斯机场老被炸，他们就找各种有他们需要的
: 特性的狗培育出一种特殊的能闻出很多种炸药的成分的狗，当然也是好几十年才培育出
: 的了。好像很多国家想跟他们买，他们还不卖。

l*a2011-09-18 07:09

19 楼

是不是不会DP就不能找到拿的出手的工作？

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

: 典型DP

I*e2011-09-18 07:09

20 楼

狗和狼是两个物种？

【在 B****t 的大作中提到】

g*e2011-09-18 07:09

21 楼

让大牛见笑了。能贪心当然比DP好
DP是成为隔壁俱乐部第一类人的充分条件，不是必要条件，哈哈

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

: 是不是不会DP就不能找到拿的出手的工作？

c*t2011-09-18 07:09

22 楼

第一题对，不过最后应该是(x^(B/2) )^2 % C = （(x^(B /2)%C)^2）%C
不过每次循环中间都应该考虑B不是even怎么办，这时候可以x^B % C = (x^(B-1) % C
* (x % C)) % C，然后继续

(x

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

: 不知道对不对
: (1) 设A=kC+x，那么A^B % C = (kC + x)^B % C= x^B % C = (x^(B/2) )^2 % C = (x
: ^(B /2)%C)^2 = ... O(logn)求得结果
: (2) 维护一个堆，每次拿出最小的两个，再把生成的结果放回去，O(nlogn)

c*t2011-09-18 07:09

23 楼

第二题只能merge相邻的吧。

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

: 数论太烂。第一题怎么做呢？
: 第二题感觉是先从小到大排序以后顺着merge过来，这样最大的数字被merge最少，损失
: 最小。你觉得呢？

c*t2011-09-18 07:09

24 楼

不太懂，push进堆后还怎么保证merge的顺序？
比如 5 10 1 3，能说说过程吗？
谢谢

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

: 第二题，不就是经典贪心算法嘛，建最小堆，反复取最小两个，相加后push进堆，直到
: 堆为空。

t*22011-09-18 07:09

25 楼

堆是 1 3 5 10
然后是 4 5 10
然后 9 10
最后19

【在 c********t 的大作中提到】

: 不太懂，push进堆后还怎么保证merge的顺序？
: 比如 5 10 1 3，能说说过程吗？
: 谢谢

c*t2011-09-18 07:09

26 楼

不行啊，1，3，与5不相邻，不能merge。这是我对这题的理解，否则排序，然后从小到
大merge即可。
我觉得还是要DP

【在 t*******2 的大作中提到】

: 堆是 1 3 5 10
: 然后是 4 5 10
: 然后 9 10
: 最后19

g*e2011-09-18 07:09

27 楼

只能merge相邻的是某届NOI决赛题，原题是合并相邻的石头堆。
现在找工作算法题有这么变态么？又不是奥赛金牌。。。

【在 c********t 的大作中提到】

: 不行啊，1，3，与5不相邻，不能merge。这是我对这题的理解，否则排序，然后从小到
: 大merge即可。
: 我觉得还是要DP

f*e2011-09-18 07:09

28 楼

huffman tree，每merge一个，排下序。

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

: 数论太烂。第一题怎么做呢？
: 第二题感觉是先从小到大排序以后顺着merge过来，这样最大的数字被merge最少，损失
: 最小。你觉得呢？

D*d2011-09-18 07:09

29 楼

需要说明的是题目要求结合运算满足结合律（环表），不满足交换律, 不然干脆是两
个 sets,
为什么叫 lists?
所以 Greedy 不能解第二题，见以下反例
按 Greedy 算法
( (2 3) 4 ) ( 6 (5 4) ) ) = 62
但是有一解法（把 2 3 4 移到末位）
（（6 5）（（4 2）（3 4））） = 61
可用二维 DP 解, O(N^2)
对于第一题，可对 B 用二进制表示(所以 log(B) ), 利用
(a mod c)^n mod c = a^n mod c
求解

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

: 第二题，不就是经典贪心算法嘛，建最小堆，反复取最小两个，相加后push进堆，直到
: 堆为空。

f*e2011-09-18 07:09

30 楼

(4,4)

【在 D**********d 的大作中提到】

: 需要说明的是题目要求结合运算满足结合律（环表），不满足交换律, 不然干脆是两
: 个 sets,
: 为什么叫 lists?
: 所以 Greedy 不能解第二题，见以下反例
: 按 Greedy 算法
: ( (2 3) 4 ) ( 6 (5 4) ) ) = 62
: 但是有一解法（把 2 3 4 移到末位）
: （（6 5）（（4 2）（3 4））） = 61
: 可用二维 DP 解, O(N^2)
: 对于第一题，可对 B 用二进制表示(所以 log(B) ), 利用

g*y2011-09-18 07:09

31 楼

greedy：
2 3 4 6 5 4 0
5 4 4 5 6 5
5 5 6 8 13
10 6 8 23
14 10 37
24 61

【在 D**********d 的大作中提到】

D*d2011-09-18 07:09

32 楼

(4,4) 不能结合，因为不相邻（即使是环型）
如果不满足环形相邻结合，我的反例可以是
6 5 4 2 3 4
结论一样

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

: greedy：
: 2 3 4 6 5 4 0
: 5 4 4 5 6 5
: 5 5 6 8 13
: 10 6 8 23
: 14 10 37
: 24 61

c*t2011-09-18 07:09

33 楼

好吧，那feiw217 的解正确
如果只能相邻的，可以用linked list 每次都找相邻和的最小值，删除他们，插入他
们的和。直到最后剩一个。O(N^2)

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

: 只能merge相邻的是某届NOI决赛题，原题是合并相邻的石头堆。
: 现在找工作算法题有这么变态么？又不是奥赛金牌。。。

g*y2011-09-18 07:09

34 楼

题目有说不相邻不能merge吗？如果有这个条件的话，那就是典型的DP，和matrix
multiplication一样的。

【在 D**********d 的大作中提到】

: (4,4) 不能结合，因为不相邻（即使是环型）
: 如果不满足环形相邻结合，我的反例可以是
: 6 5 4 2 3 4
: 结论一样

f*72011-09-18 07:09

35 楼

亲，第一题有log时间算power的，leetcode有原题。
话说怎么mod才能log时间呢？

c*t2011-09-18 07:09

36 楼

如果有这个条件，求动态方程，我想不出来

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

: 题目有说不相邻不能merge吗？如果有这个条件的话，那就是典型的DP，和matrix
: multiplication一样的。

f*72011-09-18 07:09

37 楼

lz的意思是，算出最优merge时间。
那就是，可以rearrange merge的顺序，不一定merge相邻的
所以原则就是，总是merge最短的两个。
lz也说，经典题嘛。那就套huffman编码的算法了。

c*t2011-09-18 07:09

38 楼

Min heap 不是挺好吗？O(nlogn)
Haffman tree 怎么做

★ 发自iPhone App: ChineseWeb 7.5

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

: lz的意思是，算出最优merge时间。
: 那就是，可以rearrange merge的顺序，不一定merge相邻的
: 所以原则就是，总是merge最短的两个。
: lz也说，经典题嘛。那就套huffman编码的算法了。

c*p2011-09-18 07:09

39 楼

a^b mod c = (a mod c) ^b mod c

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

: 数论太烂。第一题怎么做呢？
: 第二题感觉是先从小到大排序以后顺着merge过来，这样最大的数字被merge最少，损失
: 最小。你觉得呢？

f*72011-09-18 07:09

40 楼

对啊，就是用min-heap
huffman tree，是给定各个字符编码长度，构建编码树，算法和这个一模一样，贪心！

【在 c********t 的大作中提到】

: Min heap 不是挺好吗？O(nlogn)
: Haffman tree 怎么做
:
: ★ 发自iPhone App: ChineseWeb 7.5

g*y2011-09-18 07:09

41 楼

如果有这个条件，那就可以参考matrix multiplication的解法。
c[i，j]: denotes the optimal cost of merging array i to array j
then the subproblem structure can be:
c[i,j] = min(c[i,k] + c[k+1,j] + cost of merging array[i:k] and array[k + 1,
j]) for k = i to j - 1
time complexity: O(n^3)
def merge_array(arrays):
assert arrays
n = len(arrays)
if n == 1:
return 0
c = [[sys.maxsize for j in range(n)] for i in range(n)]
for i in range(n):
c[i][i] = 0
for i in range(1, n):
c[i-1][i] = arrays[i - 1] + arrays[i]
for l in range(2, n + 1):
for i in range(n - l + 1):
j = i + l - 1
cost = sum(arrays[i:j + 1])
for k in range(i, j):
total_cost = cost + c[i][k] + c[k+1][j]
c[i][j] = min(total_cost, c[i][j])
return c[0][n-1]

【在 c********t 的大作中提到】

: 如果有这个条件，求动态方程，我想不出来

c*t2011-09-18 07:09

42 楼

学习中.
问一下我这样不用DP解行不?
用linked list 每次都找 "两数相邻和" 的最小值，删除他们，在同位置插入他
们的和。直到最后剩一个。O(N^2)

1,

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

: 如果有这个条件，那就可以参考matrix multiplication的解法。
: c[i，j]: denotes the optimal cost of merging array i to array j
: then the subproblem structure can be:
: c[i,j] = min(c[i,k] + c[k+1,j] + cost of merging array[i:k] and array[k + 1,
: j]) for k = i to j - 1
: time complexity: O(n^3)
: def merge_array(arrays):
: assert arrays
: n = len(arrays)
: if n == 1:

g*y2011-09-18 07:09

43 楼

好像不行。一个counterexample是4,2,3,4. 最优解应该是26.按照你的解法是27?

【在 c********t 的大作中提到】

: 学习中.
: 问一下我这样不用DP解行不?
: 用linked list 每次都找 "两数相邻和" 的最小值，删除他们，在同位置插入他
: 们的和。直到最后剩一个。O(N^2)
:
: 1,

c*t2011-09-18 07:09

44 楼

赞，明白了。谢谢！
你的codes
for l in range(2, n + 1):
for i in range(n - l + 1):
j = i + l - 1
改成
for (int i = n-3; i >=0; i--) {
for (int j = i + 2; j < n; j++) {
我感觉更容易理解一些，就是从c[n-3,n-1]算到c[0,n-1]

1,

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

g*y2011-09-18 07:09

45 楼

我的code里面length l = j - i + 1. 这个解法的关键是先得到length短的optimal
solution，然后以此为基础，得到length长的optimal solution。你这样改掉以后好像
不行了吧？

【在 c********t 的大作中提到】

: 赞，明白了。谢谢！
: 你的codes
: for l in range(2, n + 1):
: for i in range(n - l + 1):
: j = i + l - 1
: 改成
: for (int i = n-3; i >=0; i--) {
: for (int j = i + 2; j < n; j++) {
: 我感觉更容易理解一些，就是从c[n-3,n-1]算到c[0,n-1]
:

c*t2011-09-18 07:09

46 楼

我的也是从短往长算啊，不过是从后头开始，一直到i=0,可以的
原来l是length, 那为什么 l range 是2 到 n+1, 而不是到 n呢？

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

: 我的code里面length l = j - i + 1. 这个解法的关键是先得到length短的optimal
: solution，然后以此为基础，得到length长的optimal solution。你这样改掉以后好像
: 不行了吧？

g*y2011-09-18 07:09

47 楼

python里range（2，n+1)表示2 to n.

【在 c********t 的大作中提到】

: 我的也是从短往长算啊，不过是从后头开始，一直到i=0,可以的
: 原来l是length, 那为什么 l range 是2 到 n+1, 而不是到 n呢？

c*t2011-09-18 07:09

48 楼

明白了，多谢

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

: python里range（2，n+1)表示2 to n.