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.，
|
