无敌！苹果重获要命专利：颤抖吧Android - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

无敌！苹果重获要命专利：颤抖吧Android

无敌！苹果重获要命专利：颤抖吧Android# PDA - 掌中宝

c*t2013-10-17 07:10

1 楼

说木棍的木头密度不是均匀分布的，密度可以从1-9，比如一个棍子可以表示为1435789
一个人想要拿一根树枝切一对棍子做武器，两个棍子等长，可以分开使，也可以接一起
当一根棍，但是接起来的棍子，要求是平衡的，即重心在中间。
重心的计算是这样的用加权重量除以重量，如果数值在棍子中点(是棍子长度的中心）
比如棍子 3142 （3*1+1*2+4*3+2*4）/(3+1+4+2) =2.5 正好在棍子的中心，所以这个
是个平衡的棍子。
现在给一个长木枝，问能不能切出两个最长的棍子，满足条件。
怎么做？
输入是代表长木枝的string
要求print out 三个整数两个棍子的index i, j，和长度。
比如 cut("3142"), 函数应该print out "0 2 2"

F*82013-10-17 07:10

2 楼

On May 5, 2015, we registered your permanent resident status and mailed you
a Welcome Notice for Receipt Number ********. Please follow the instructions
in the notice. Your new permanent resident card should arrive by July 4,
2015, after this registration or after you complete any ADIT processing
referred to in the welcome notice, whichever is later. If you move, go to
www.uscis.gov/addresschange to give us your new mailing address.
个人隐私,不好意思,隐去了Receipt Number

W*h2013-10-17 07:10

3 楼

RT
$38/张
如需要，请电话联系，760-668-6780

r*e2013-10-17 07:10

4 楼

p*m2013-10-17 07:10

5 楼

2007年苹果带来了首款iPhone，当时谁会料想这款手机竟然改变了手机行业。乔布斯始
终认为手是最好的触控工具，所以iPhone带来全新的触控体验，而这其种就包含了著名
的“multitouch（多点触控）”。
苹果是一家非常注意保护自己利益的公司，他们总是很积极的申请专利，而这样做还能
让他们来制约敌人的发展。其实之前苹果已经拿到了multitouch的专利，不过随后美国
专利商标局取消了这项决议。
如此重要的一个专利，苹果怎能轻易放过，去年12月他们向美国专利商标局递交了一份
多达364页的“乔布斯专利”，经过漫长的复审后，现在美国专利商标局给出了答案是
专利全部有效。
而上述专利就包含了很著名的multitouch，现在多点触控再次归属苹果，目前该功能在
触屏智能手机中随处可见，这将会是苹果向Android阵营发难的重大法宝。
谷歌要颤抖了吗？

p*22013-10-17 07:10

6 楼

3142 （3*1+1*2+4*3+2*4）/(3+1+4+2) =2.5
长度为4？为什么2.5是中心？

v*62013-10-17 07:10

7 楼

cong!

w*k2013-10-17 07:10

8 楼

正规渠道吗？
合法的吗

【在 W********h 的大作中提到】

: RT
: $38/张
: 如需要，请电话联系，760-668-6780

q*l2013-10-17 07:10

9 楼

1688毛片，这得看多久啊

v*g2013-10-17 07:10

10 楼

乖。。继续做梦

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

: 2007年苹果带来了首款iPhone，当时谁会料想这款手机竟然改变了手机行业。乔布斯始
: 终认为手是最好的触控工具，所以iPhone带来全新的触控体验，而这其种就包含了著名
: 的“multitouch（多点触控）”。
: 苹果是一家非常注意保护自己利益的公司，他们总是很积极的申请专利，而这样做还能
: 让他们来制约敌人的发展。其实之前苹果已经拿到了multitouch的专利，不过随后美国
: 专利商标局取消了这项决议。
: 如此重要的一个专利，苹果怎能轻易放过，去年12月他们向美国专利商标局递交了一份
: 多达364页的“乔布斯专利”，经过漫长的复审后，现在美国专利商标局给出了答案是
: 专利全部有效。
: 而上述专利就包含了很著名的multitouch，现在多点触控再次归属苹果，目前该功能在

c*t2013-10-17 07:10

11 楼

题目这么说的，长度5在 3，长度4在2.5，长度3在2，既中心位置。

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

: 3142 （3*1+1*2+4*3+2*4）/(3+1+4+2) =2.5
: 长度为4？为什么2.5是中心？

S*t2013-10-17 07:10

12 楼

阁下演技越来越高了。。。。

you
instructions

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

: On May 5, 2015, we registered your permanent resident status and mailed you
: a Welcome Notice for Receipt Number ********. Please follow the instructions
: in the notice. Your new permanent resident card should arrive by July 4,
: 2015, after this registration or after you complete any ADIT processing
: referred to in the welcome notice, whichever is later. If you move, go to
: www.uscis.gov/addresschange to give us your new mailing address.
: 个人隐私,不好意思,隐去了Receipt Number

W*h2013-10-17 07:10

13 楼

是的。新票：）

H*g2013-10-17 07:10

14 楼

最纯粹的动作这个是什么享受啊

a*y2013-10-17 07:10

15 楼

苹果有格式刷的专利吗

c*p2013-10-17 07:10

16 楼

这题看上去就好麻烦。。
切开的两根棍子可以把其中一根调个个儿再拼一起么?

r*p2013-10-17 07:10

17 楼

应该是通知你被拒了，因为你隐瞒了反革命装逼犯的criminal record！

c*t2013-10-17 07:10

18 楼

厉害，你得到了它

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

: 这题看上去就好麻烦。。
: 切开的两根棍子可以把其中一根调个个儿再拼一起么?

m*e2013-10-17 07:10

19 楼

gxgx!

c*t2013-10-17 07:10

20 楼

我物理很差，大概重心应该是这么算的吧，反正按题目做吧

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

: 题目这么说的，长度5在 3，长度4在2.5，长度3在2，既中心位置。

m*y2013-10-17 07:10

21 楼

用绿卡 tjjtds

you
instructions

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

c*p2013-10-17 07:10

22 楼

我擦，还可以两根长度不一样啊？

c*p2013-10-17 07:10

23 楼

原题说是等长的棍子。。。。。。。。。。。。。。。。

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

: 我擦，还可以两根长度不一样啊？

p*22013-10-17 07:10

24 楼

不行就bruteforce吧。哈哈。

c*t2013-10-17 07:10

25 楼

en 我就是这么做的，杯具了
我把输入和输出要求加上了，是个完整的题了，有兴趣做做吧。

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

: 不行就bruteforce吧。哈哈。

p*22013-10-17 07:10

26 楼

这题密度1－9,如果长度是10自然能找到两个长度为1的棍子。否则的话，长度最多是 9
而已。BF都很快了。

c*t2013-10-17 07:10

27 楼

再仔细想想

9

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

: 这题密度1－9,如果长度是10自然能找到两个长度为1的棍子。否则的话，长度最多是 9
: 而已。BF都很快了。

p*22013-10-17 07:10

28 楼

你这个条件应该加上，不然这题没什么意义。加上之后至少可以用binary search改善
复杂度。

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

: en 我就是这么做的，杯具了
: 我把输入和输出要求加上了，是个完整的题了，有兴趣做做吧。

c*t2013-10-17 07:10

29 楼

如何用binary search?

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

:
: 你这个条件应该加上，不然这题没什么意义。加上之后至少可以用binary search改善
: 复杂度。

c*t2013-10-17 07:10

30 楼

我杯具也不一定是因为用brute force, 有一个简单的test case fail 了，可是其他都
过了，很复杂的都过了。现在还没明白为什么。
最复杂的case,得到解的木棍长度是200多。
我有两个test case可以测试。

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

:
: 你这个条件应该加上，不然这题没什么意义。加上之后至少可以用binary search改善
: 复杂度。

t*a2013-10-17 07:10

31 楼

很有意思的题目啊，能麻烦你把test cases贴出来好吗？最好小的和大的都贴出来，谢
谢！

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

: 我杯具也不一定是因为用brute force, 有一个简单的test case fail 了，可是其他都
: 过了，很复杂的都过了。现在还没明白为什么。
: 最复杂的case,得到解的木棍长度是200多。
: 我有两个test case可以测试。

p*22013-10-17 07:10

32 楼

嗯。贴出来坐坐。

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

: 很有意思的题目啊，能麻烦你把test cases贴出来好吗？最好小的和大的都贴出来，谢
: 谢！

c*t2013-10-17 07:10

33 楼

大的
7512839182731294837512653698759387212532563849823857812519853546649398328875
2561562566521163949159852818593583947382564219379418437589548917235987165478
5647324524354639289887198715265623845821451815818815252738638451823475832516
5316563487283746285745938476523546127534721652812736459874658475366423876152
3874918726587632182763548277685987162837645716526374519628376487268765478263
5987162983654786253476179834691827567647382964865167234698172658761946256162
5162561527384273482748237482734827348274827
小的(我fail了的）
123232111119232333277777999
我原文里面的例子是我自己编的，也算一个test case吧

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

: 很有意思的题目啊，能麻烦你把test cases贴出来好吗？最好小的和大的都贴出来，谢
: 谢！

p*22013-10-17 07:10

34 楼

7512839182731294837512653698759387212532563849823857812519853546649398328875
2561562566521163949159852818593583947382564219379418437589548917235987165478
5647324524354639289887198715265623845821451815818815252738638451823475832516
5316563487283746285745938476523546127534721652812736459874658475366423876152
3874918726587632182763548277685987162837645716526374519628376487268765478263
5987162983654786253476179834691827567647382964865167234698172658761946256162
多谢。一会儿做做。

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

: 大的
: 7512839182731294837512653698759387212532563849823857812519853546649398328875
: 2561562566521163949159852818593583947382564219379418437589548917235987165478
: 5647324524354639289887198715265623845821451815818815252738638451823475832516
: 5316563487283746285745938476523546127534721652812736459874658475366423876152
: 3874918726587632182763548277685987162837645716526374519628376487268765478263
: 5987162983654786253476179834691827567647382964865167234698172658761946256162
: 5162561527384273482748237482734827348274827
: 小的(我fail了的）
: 123232111119232333277777999

p*22013-10-17 07:10

35 楼

7512839182731294837512653698759387212532563849823857812519853546649398328875
2561562566521163949159852818593583947382564219379418437589548917235987165478
5647324524354639289887198715265623845821451815818815252738638451823475832516
5316563487283746285745938476523546127534721652812736459874658475366423876152
3874918726587632182763548277685987162837645716526374519628376487268765478263
5987162983654786253476179834691827567647382964865167234698172658761946256162
有答案吗？

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

c*p2013-10-17 07:10

36 楼

n^2时间n^2空间，，，有更好的办法么。。。。

1435789

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

: 说木棍的木头密度不是均匀分布的，密度可以从1-9，比如一个棍子可以表示为1435789
: 一个人想要拿一根树枝切一对棍子做武器，两个棍子等长，可以分开使，也可以接一起
: 当一根棍，但是接起来的棍子，要求是平衡的，即重心在中间。
: 重心的计算是这样的用加权重量除以重量，如果数值在棍子中点(是棍子长度的中心）
: 比如棍子 3142 （3*1+1*2+4*3+2*4）/(3+1+4+2) =2.5 正好在棍子的中心，所以这个
: 是个平衡的棍子。
: 现在给一个长木枝，问能不能切出两个最长的棍子，满足条件。
: 怎么做？
: 输入是代表长木枝的string
: 要求print out 三个整数两个棍子的index i, j，和长度。

p*22013-10-17 07:10

37 楼

n^2怎么算的？

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

: n^2时间n^2空间，，，有更好的办法么。。。。
:
: 1435789

c*t2013-10-17 07:10

38 楼

brute force是 n^3吧， n^2怎么做？

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

: n^2时间n^2空间，，，有更好的办法么。。。。
:
: 1435789

c*t2013-10-17 07:10

39 楼

有
你做完了我公布，看看对不对。

7512839182731294837512653698759387212532563849823857812519853546649398328875
2561562566521163949159852818593583947382564219379418437589548917235987165478
5647324524354639289887198715265623845821451815818815252738638451823475832516
5316563487283746285745938476523546127534721652812736459874658475366423876152
3874918726587632182763548277685987162837645716526374519628376487268765478263
5987162983654786253476179834691827567647382964865167234698172658761946256162

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

:
: n^2怎么算的？

w*m2013-10-17 07:10

40 楼

两个等长的棍子拼在一起后的长度都是偶数吧
你这个5，3是怎么来的啊？

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

: 题目这么说的，长度5在 3，长度4在2.5，长度3在2，既中心位置。

c*t2013-10-17 07:10

41 楼

你说得对，我只是为了解释一下重心位置。

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

: 两个等长的棍子拼在一起后的长度都是偶数吧
: 你这个5，3是怎么来的啊？

c*p2013-10-17 07:10

42 楼

哦，时间复杂度是n^3。。。。

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

:
: n^2怎么算的？

p*22013-10-17 07:10

43 楼

如果这样bs可以降为n2logm

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

: 哦，时间复杂度是n^3。。。。

c*t2013-10-17 07:10

44 楼

还是没明白怎么binary search

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

: 如果这样bs可以降为n2logm

h*62013-10-17 07:10

45 楼

一共有n^2跟短棍子，计算每根短棍子的重量和重心都是O(1)的。然后比较相同长度的
短棍子，用hashmap或者treemap找出相同的重心，只是浮点数的比较可能不太精确。

c*t2013-10-17 07:10

46 楼

两个重心相同的短棍子接起来，重心就在中点吗？好像不对啊

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

: 一共有n^2跟短棍子，计算每根短棍子的重量和重心都是O(1)的。然后比较相同长度的
: 短棍子，用hashmap或者treemap找出相同的重心，只是浮点数的比较可能不太精确。

t*a2013-10-17 07:10

47 楼

能帮我看看结果对不对好么？不好意思，我还是用clojure写的
(use 'clojure.set)
;; main function: O(n^3) time O(n^2) space

(defn best-cut [branch-string]
(do
(defn parse-branch [branch]
(vec (map #(- (int %) (dec (int \1))) branch)))
(def branch (parse-branch branch-string))
(def sum-stick
(memoize (fn [i k] ; k > 0
(let [j (dec (+ i k))
xj (get branch j)]
(if (== k 1)
xj
(+ xj (sum-stick i (dec k))))))))
(def torque-stick
(memoize (fn [i k]
(if (== k 1)
(let [s (/ (sum-stick i k) 2.0)] [s s])
(let [t- (torque-stick i (dec k))
s- (sum-stick i (dec k))
j (dec (+ i k))
xj (get branch j)
t-l (+ (first t-) s- (/ xj 2))
t-r (+ (second t-) (* xj (- k 0.5)))
]
[t-l t-r]
)))))
(defn is-good-cut? [i j k]
(let [torque-1 (set (torque-stick i k))
torque-2 (set (torque-stick j k))
torque-12 (intersection torque-1 torque-2)]
(if (empty? torque-12)
false
true)))
(def lazy-ijk (let [n (count branch)
ks (range (quot n 2) 0 -1)
iks (mapcat (fn [k] (map #(vector % k) (range (- n k
)))) ks)
ijks (mapcat (fn [[i k]]
(let [js (range (+ i k) (inc (- n k))
)]
(map #(vector i % k (is-good-cut? i
% k)) js))) iks)
]
ijks))
(butlast (first (drop-while #(not (last %)) lazy-ijk)))))
;; test cases
(best-cut "3142") ; (0 2 2)
(best-cut "123232111119232333277777999") ; (7 15 6)
(best-cut "
7512839182731294837512653698759387212532563849823857812519853546649398328875
2561562566521163949159852818593583947382564219379418437589548917235987165478
5647324524354639289887198715265623845821451815818815252738638451823475832516
5316563487283746285745938476523546127534721652812736459874658475366423876152
3874918726587632182763548277685987162837645716526374519628376487268765478263
5987162983654786253476179834691827567647382964865167234698172658761946256162
5162561527384273482748237482734827348274827") ; (10 262 229)

c*t2013-10-17 07:10

48 楼

Orz 佩服，都对了!!
可惜我看不懂，是brute force吗？
为什么我第二个case是 1 12 4呢？

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

: 能帮我看看结果对不对好么？不好意思，我还是用clojure写的
: (use 'clojure.set)
: ;; main function: O(n^3) time O(n^2) space
:
: (defn best-cut [branch-string]
: (do
: (defn parse-branch [branch]
: (vec (map #(- (int %) (dec (int \1))) branch)))
: (def branch (parse-branch branch-string))
: (def sum-stick

t*a2013-10-17 07:10

49 楼

是brute force, 从长到短寻找棍子，用了一点memoize的技巧来减少重复计算。
我不知道怎么做二分查找，有人知道么？

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

: Orz 佩服，都对了!!
: 可惜我看不懂，是brute force吗？
: 为什么我第二个case是 1 12 4呢？

h*62013-10-17 07:10

50 楼

弄错了，应该是算力矩，力矩相等的两根短棍接上之后重心一定在连接点，又根据长度
相等，也就是中心了。任何一段短棍的力矩都是0.5的整数倍，乘以2之后都是整数，因
此也没有浮点数的比较问题了。
一共有n^2根短棍，每根短棍有两个力矩，其和为重量乘以长度，而对于每根短棍的长
度、重量、力矩都可以在O(1)内求出。
比如题目中的例子：3 1 4 2
3 1的力矩为0.5*3 + 1.5*1 = 3
反转力矩为1.5*3 + 0.5*1 = 5
4 2的力矩为0.5*4 + 1.5*2 = 5
因此1 3的力矩和4 2的力矩相等。

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

: 两个重心相同的短棍子接起来，重心就在中点吗？好像不对啊

c*t2013-10-17 07:10

51 楼

我把 test case 2的解里的两个木棍 111192，333277 拿来到我的codes 验证是否
balance, 竟然是false. 难道我的balance验证有问题？可是其他所有case都正确啊。

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

c*t2013-10-17 07:10

52 楼

明白了，这个太难想了啊，考物理啊。
每段短棍的长度、重量、力矩都能在O(1)内求出吗，最长可能的棍子是n/2啊，还有这
样就不用算重量了吧。只用算力矩，平均每根棍子是O(n)
还有不是n^2根，应该是 n*(n+1)/2根吧，不过无所谓了反正是O（n^2), 最后应该是O
(n^3)
brute force 刚才说的O(n^3)忘了验证balance的O(n)了，总共应该是O（n^4)。

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

: 弄错了，应该是算力矩，力矩相等的两根短棍接上之后重心一定在连接点，又根据长度
: 相等，也就是中心了。任何一段短棍的力矩都是0.5的整数倍，乘以2之后都是整数，因
: 此也没有浮点数的比较问题了。
: 一共有n^2根短棍，每根短棍有两个力矩，其和为重量乘以长度，而对于每根短棍的长
: 度、重量、力矩都可以在O(1)内求出。
: 比如题目中的例子：3 1 4 2
: 3 1的力矩为0.5*3 + 1.5*1 = 3
: 反转力矩为1.5*3 + 0.5*1 = 5
: 4 2的力矩为0.5*4 + 1.5*2 = 5
: 因此1 3的力矩和4 2的力矩相等。

p*22013-10-17 07:10

53 楼

大牛终于出现了。你说的的力矩的东西还真不懂。不过怎么计算这块我一直不想brute
force搞。
我当时想的两根棍子会出现八种情况。

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

c*t2013-10-17 07:10

54 楼

请问测平衡 check(棍子1+棍子2) || check(翻转棍子1+棍子2)是不是足够证明它们能
不能平衡？
似乎我就是死在这里了。

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

: 是brute force, 从长到短寻找棍子，用了一点memoize的技巧来减少重复计算。
: 我不知道怎么做二分查找，有人知道么？

c*t2013-10-17 07:10

55 楼

真的哦，还要考虑翻转棍子1+翻转棍子2，和棍子1+翻转棍子2 真奇怪为什么呢？

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

: 请问测平衡 check(棍子1+棍子2) || check(翻转棍子1+棍子2)是不是足够证明它们能
: 不能平衡？
: 似乎我就是死在这里了。

p*22013-10-17 07:10

56 楼

L1 R1 L2 R2
L1 R1 R2 L2
R1 L1 L2 R2
R1 L1 R2 L2
第二根棍子在前边有是4种。
所以八种，我就懒的写了。

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

: 请问测平衡 check(棍子1+棍子2) || check(翻转棍子1+棍子2)是不是足够证明它们能
: 不能平衡？
: 似乎我就是死在这里了。

c*t2013-10-17 07:10

57 楼

第二根在前，与第一根在前无差别，不用算。
倒是我以为 L1 R1 L2 R2 平衡, 一定就 R1 L1 R2 L2也平衡，看来是错的。

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

:
: L1 R1 L2 R2
: L1 R1 R2 L2
: R1 L1 L2 R2
: R1 L1 R2 L2
: 第二根棍子在前边有是4种。
: 所以八种，我就懒的写了。

p*22013-10-17 07:10

58 楼

理论上是这样。不然就不叫平衡了。不过从那个公式怎么推导呢？

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

: 第二根在前，与第一根在前无差别，不用算。
: 倒是我以为 L1 R1 L2 R2 平衡, 一定就 R1 L1 R2 L2也平衡，看来是错的。

h*62013-10-17 07:10

59 楼

用力矩的算法，复杂度O(n^2)
#include
#include
#include
#include
using std::string;
using std::vector;
using stdext::hash_map;
void weightcenter(string str)
{
int n = str.size();
vector w(n);
for(int i = 0; i < n; i++) {
w[i] = str[i] - '0';
}
vector >weight(n, vector(n));
vector >torque(n, vector(n));
int maxlen=-1, maxi=-1, maxj=-1;
for(int len = 1; len <= n/2; len++) {
hash_map M; // map from torque to start index
for(int start = 0; start <= n - len; start++) {
if(start >= len) {
int pusht = torque[len][start-len];
int pushw = weight[len][start-len];
M[pusht] = start - len;
M[2*pushw*len - pusht] = start - len;
}
int curw = weight[len][start] = weight[len-1][start] + w[start+
len-1];
int curt = torque[len][start] = torque[len-1][start] + (2*len-1)
*w[start+len-1];
if(M.find(curt) != M.end()) {
maxlen = len;
maxi = M[curt];
maxj = start;
}
if(M.find(2*curw*len - curt) != M.end()) {
maxlen = len;
maxi = M[2*curw*len - curt];
maxj = start;
}
}
}
printf("%d %d %d\n", maxi, maxj, maxlen);
}

c*t2013-10-17 07:10

60 楼

不知道，俺是数学物理盲

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

:
: 理论上是这样。不然就不叫平衡了。不过从那个公式怎么推导呢？

c*t2013-10-17 07:10

61 楼

赞，学习了

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

: 用力矩的算法，复杂度O(n^2)
: #include
: #include
: #include
: #include
: using std::string;
: using std::vector;
: using stdext::hash_map;
: void weightcenter(string str)
: {

p*22013-10-17 07:10

62 楼

我还是几何盲

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

: 不知道，俺是数学物理盲

p*22013-10-17 07:10

63 楼

han6太帅了

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

: 用力矩的算法，复杂度O(n^2)
: #include
: #include
: #include
: #include
: using std::string;
: using std::vector;
: using stdext::hash_map;
: void weightcenter(string str)
: {

p*22013-10-17 07:10

64 楼

你看懂了？给讲讲

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

: 赞，学习了

t*a2013-10-17 07:10

65 楼

精炼且高效的解法！
合理运用用hashmap把n^3变成了n^2，就好像在数组里寻找重复数字一样的思路！
han6果然厉害，佩服你两年了！

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

: 用力矩的算法，复杂度O(n^2)
: #include
: #include
: #include
: #include
: using std::string;
: using std::vector;
: using stdext::hash_map;
: void weightcenter(string str)
: {

t*a2013-10-17 07:10

66 楼

我的思路是一根棍子会产生两种力矩[t-left, t-right]
那么检测两根棍子是否能平衡，就是看这两根棍子的力矩集合是否存在交集
程序里的is-good-cut?函数就用来评估一个解[i,j,k]是否合法

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

: 请问测平衡 check(棍子1+棍子2) || check(翻转棍子1+棍子2)是不是足够证明它们能
: 不能平衡？
: 似乎我就是死在这里了。

p*22013-10-17 07:10

67 楼

是呀。han6是我的偶像呀。

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

: 精炼且高效的解法！
: 合理运用用hashmap把n^3变成了n^2，就好像在数组里寻找重复数字一样的思路！
: han6果然厉害，佩服你两年了！

h*62013-10-17 07:10

68 楼

我机器里还是用的老系统，只支持C++03。
在C++11里，代码有两点改变:
一个是stdext::hash_map被弃用，改名为std::unordered_map
另一个是嵌套模板的右括号可以连续写，不用空一格。

c*t2013-10-17 07:10

69 楼

我有个建议，能不能从len=n/2开始计算，hit map了就直接返回了，不用遍历。wight
和 torque计算可以用减法算
这样可以加快计算。

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

: 用力矩的算法，复杂度O(n^2)
: #include
: #include
: #include
: #include
: using std::string;
: using std::vector;
: using stdext::hash_map;
: void weightcenter(string str)
: {

c*t2013-10-17 07:10

70 楼

嗯，昨天没真懂
那个 if(start >= len)才开始入map,保证两个棍子没有重合部分还是很tricky的，不
好想。

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

:
: 是呀。han6是我的偶像呀。

c*t2013-10-17 07:10

71 楼

ls的所有人，除了俺自己，都是我偶像
榜样的力量是无穷的。

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

: 我的思路是一根棍子会产生两种力矩[t-left, t-right]
: 那么检测两根棍子是否能平衡，就是看这两根棍子的力矩集合是否存在交集
: 程序里的is-good-cut?函数就用来评估一个解[i,j,k]是否合法