H******7 发帖数: 1728 | 1 废话不多说,细节没意义。直接说题目:
1. 找出一串整数最长的连续递增或者递减序列 我找到了2n的解法,有更好的么?
2. 色子题目,2人玩,A先抛。B后。 A得到6胜利,B得到1胜利。问A赢的概率。B赢的
概率
3. C++里什么是lower_bound;
sort_heap的复杂度 为什么。
4.模板编程,利用transform.
5.OO design. 设计一个冷饮冰激凌店. |
g*********s 发帖数: 1782 | 2 赞。
n就可以吧?如果递减不成立就去更新递增,反之亦然。
相等?应该和先后抛无关吧。就像经典抽签问题,谁先抽都一样。
O(NlgN). what do you mean by "why" here?
what is this?
【在 H******7 的大作中提到】 : 废话不多说,细节没意义。直接说题目: : 1. 找出一串整数最长的连续递增或者递减序列 我找到了2n的解法,有更好的么? : 2. 色子题目,2人玩,A先抛。B后。 A得到6胜利,B得到1胜利。问A赢的概率。B赢的 : 概率 : 3. C++里什么是lower_bound; : sort_heap的复杂度 为什么。 : 4.模板编程,利用transform. : 5.OO design. 设计一个冷饮冰激凌店.
|
x*******i 发帖数: 777 | |
r******r 发帖数: 700 | 4 冷饮店,包括哪些类和操作?
如果对工作流程不熟悉,就只能边问,边讨论了?
【在 H******7 的大作中提到】 : 废话不多说,细节没意义。直接说题目: : 1. 找出一串整数最长的连续递增或者递减序列 我找到了2n的解法,有更好的么? : 2. 色子题目,2人玩,A先抛。B后。 A得到6胜利,B得到1胜利。问A赢的概率。B赢的 : 概率 : 3. C++里什么是lower_bound; : sort_heap的复杂度 为什么。 : 4.模板编程,利用transform. : 5.OO design. 设计一个冷饮冰激凌店.
|
g*****i 发帖数: 2162 | 5 第一题如果要求的序列是连续的,类似substring,扫一遍就可以了吧,o(n) time o(1) space
【在 H******7 的大作中提到】 : 废话不多说,细节没意义。直接说题目: : 1. 找出一串整数最长的连续递增或者递减序列 我找到了2n的解法,有更好的么? : 2. 色子题目,2人玩,A先抛。B后。 A得到6胜利,B得到1胜利。问A赢的概率。B赢的 : 概率 : 3. C++里什么是lower_bound; : sort_heap的复杂度 为什么。 : 4.模板编程,利用transform. : 5.OO design. 设计一个冷饮冰激凌店.
|
O******n 发帖数: 1505 | 6 同意
怀疑是不连续的还有点做头
space
【在 g*****i 的大作中提到】 : 第一题如果要求的序列是连续的,类似substring,扫一遍就可以了吧,o(n) time o(1) space
|
H******7 发帖数: 1728 | 7 是 第一题是简单。
我也想出o(n)的了 当时时间短 没想好就说了。 |
h*********3 发帖数: 111 | 8 6/11 For a to win, 5/11 for b to win
【在 g*********s 的大作中提到】 : 赞。 : : n就可以吧?如果递减不成立就去更新递增,反之亦然。 : 相等?应该和先后抛无关吧。就像经典抽签问题,谁先抽都一样。 : O(NlgN). what do you mean by "why" here? : what is this?
|
g*****i 发帖数: 2162 | 9 恩,不连续的一般是O(nlogn),不知道算法的话用dp是o(n^2)
【在 O******n 的大作中提到】 : 同意 : 怀疑是不连续的还有点做头 : : space
|
g*********s 发帖数: 1782 | 10 why? 6/(6+5) vs 5/(6+5)
consider another case of coin throwing. A wins if head up, B wins if tail
up. then a has 2/3 to win while B only has 1/3?
【在 h*********3 的大作中提到】 : 6/11 For a to win, 5/11 for b to win
|
|
|
g*****i 发帖数: 2162 | 11 能解释下吗?对这概率题没啥思路.
【在 h*********3 的大作中提到】 : 6/11 For a to win, 5/11 for b to win
|
g*********s 发帖数: 1782 | 12 that algorithm is not easy at at all.
i'd say it's harder than that historgram dp one.
【在 g*****i 的大作中提到】 : 恩,不连续的一般是O(nlogn),不知道算法的话用dp是o(n^2)
|
d*******l 发帖数: 338 | 13 第二题是什么意思?如果A没抛到6,B也没抛到1呢? |
O******n 发帖数: 1505 | 14 继续啊
我也不知道为什么是6/11和5/11
【在 d*******l 的大作中提到】 : 第二题是什么意思?如果A没抛到6,B也没抛到1呢?
|
g*********s 发帖数: 1782 | 15 let 1/6 = p, 5/6 = q.
a to win: p + q^2*p + q^4*p + ... = =p/(1-q^2) = (1/6)/(11/36) = 6/11.
【在 O******n 的大作中提到】 : 继续啊 : 我也不知道为什么是6/11和5/11
|
O******n 发帖数: 1505 | 16 公式对了但是结果就是6/11。。。
【在 g*********s 的大作中提到】 : let 1/6 = p, 5/6 = q. : a to win: p + q^2*p + q^4*p + ... = =p/(1-q^2) = (1/6)/(11/36) = 6/11.
|
g*********s 发帖数: 1782 | 17 miscalculation. 1-25/36, i got 9/36, not 11/36.
old leh, sigh.
【在 O******n 的大作中提到】 : 公式对了但是结果就是6/11。。。
|
g*****i 发帖数: 2162 | 18 那个算法很好记,程序很短.
【在 g*********s 的大作中提到】 : that algorithm is not easy at at all. : i'd say it's harder than that historgram dp one.
|
d*******l 发帖数: 338 | 19 看了回复终于明白题意了,大概意思就是A掷到6就赢,B掷到1就赢,A先B后,两人轮流
,不死不休。。。其实可以抽象为两个人每轮都有1/6概率获胜,问先掷和后掷赢得概
率分别是多少。
其实还是比较简单的,设A赢得概率P(A)
P(A) = 1/6(第一轮掷到6)+ 5/6 * (1 - P(A))
P(A) = 6/11
【在 O******n 的大作中提到】 : 继续啊 : 我也不知道为什么是6/11和5/11
|
g*****i 发帖数: 2162 | 20 原来我题目理解错了,我以为总共比了7次,是比大小,a赢了6次,b赢了1次,所以我对问题
的含义很迷惑.
【在 d*******l 的大作中提到】 : 看了回复终于明白题意了,大概意思就是A掷到6就赢,B掷到1就赢,A先B后,两人轮流 : ,不死不休。。。其实可以抽象为两个人每轮都有1/6概率获胜,问先掷和后掷赢得概 : 率分别是多少。 : 其实还是比较简单的,设A赢得概率P(A) : P(A) = 1/6(第一轮掷到6)+ 5/6 * (1 - P(A)) : P(A) = 6/11
|
|
|
d*******l 发帖数: 338 | 21 嗯,题目描述有点简略
【在 g*****i 的大作中提到】 : 原来我题目理解错了,我以为总共比了7次,是比大小,a赢了6次,b赢了1次,所以我对问题 : 的含义很迷惑.
|
g*********s 发帖数: 1782 | 22 好记与否不在长短吧。
【在 g*****i 的大作中提到】 : 那个算法很好记,程序很短.
|
m****t 发帖数: 555 | 23 第一题不简单,在简单扫描的基础上可以改进加快速度。
比如说,在位置i到i+L-1已找到长度为L的连续递增序列,下一步则直接比较位置i+L和
i+2L的值。如果后者小于前者,则直接跳到位置i+2L+1来搜索。这样可以省掉不必要的
扫描。时间<n. |
g*********s 发帖数: 1782 | 24 i don't see speedup by your approach.
【在 m****t 的大作中提到】 : 第一题不简单,在简单扫描的基础上可以改进加快速度。 : 比如说,在位置i到i+L-1已找到长度为L的连续递增序列,下一步则直接比较位置i+L和 : i+2L的值。如果后者小于前者,则直接跳到位置i+2L+1来搜索。这样可以省掉不必要的 : 扫描。时间<n.
|
m****t 发帖数: 555 | 25
上面想的有点不对。应该是这样的。
在位置 i 到 i+L-1 已找到长度为 L 的连续递增序列,下一步则直接跳到位置 i+2L来反向搜索最长连续递减序列,找到后再从位置 i+2L 继续正向搜索连续递增序列。这样可以省掉不必要的扫描。时间<n.,
【在 g*********s 的大作中提到】 : i don't see speedup by your approach.
|
g*****i 发帖数: 2162 | 26 恩,确实可以跳过一些点,code写起来要麻烦点
来反向搜索最长连续递减序列,找到后再从位置 i+2L 继续正向搜索连续递增序列。这
样可以省掉不必要的扫描。时间<n.,
【在 m****t 的大作中提到】 : : 上面想的有点不对。应该是这样的。 : 在位置 i 到 i+L-1 已找到长度为 L 的连续递增序列,下一步则直接跳到位置 i+2L来反向搜索最长连续递减序列,找到后再从位置 i+2L 继续正向搜索连续递增序列。这样可以省掉不必要的扫描。时间<n.,
|