hci想过没有为什么你没有机会面试Harvard毕业的孩子？# Programming - 葵花宝典
A*E
1 楼
距离最后一个candidate结束已经2周了
今年第一个on site就这么没戏勒
求bless
今年第一个on site就这么没戏勒
求bless
m*f
2 楼
You are given N blocks of height 1…N. In how many ways can you arrange
these blocks in a row such that when viewed from left you see only L blocks
(rest are hidden by taller blocks) and when seen from right you see only R
blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
these blocks in a row such that when viewed from left you see only L blocks
(rest are hidden by taller blocks) and when seen from right you see only R
blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
d*y
3 楼
今天在cvs 感觉不好，相机很烂，也没有打灯照，相片还没拿到手，特向各位前辈请教
。
。
f*2
4 楼
其实你说的abc最强根本道理在这个问题。
social network那个电影里有答案
social network那个电影里有答案
n*l
5 楼
Bless. 但是就算不是第一人选,也有可能是第二人选啊,还可能有机会的.
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
m*f
6 楼
验证下我的想法。如下：
左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
定x= L-1, y >= R-1,
假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
y = n-x-1
f(a,b) 可以用DP求出...
觉得有点繁琐, 有人有别的想法么
左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
定x
假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
y = n-x-1
f(a,b) 可以用DP求出...
觉得有点繁琐, 有人有别的想法么
n*s
7 楼
costco. DIY is the best if you want to go through lots of details.
m*r
8 楼
人家在西岸；哈佛在东岸。
哈佛也就那么回事其实； 要是你到波士顿上班，周围同事哈佛一堆一堆的。
哈佛也就那么回事其实； 要是你到波士顿上班，周围同事哈佛一堆一堆的。
x*s
9 楼
bless
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
u*p
10 楼
honestly, i am not familiar with DP, to me, it might be easier if we
approach it by
1) finding the largest two values in the array of N, denoted as N_maxA and N
_maxB and (N_maxA>N_maxB).
2) place N_maxA and N_maxB at the R^th and (L-1)^th position. Note that you
can place it in the opposite way, by placing N_maxB and N_maxA at the L^th
and (R-1)^th position
3) assuming we go with the first arrangement, then we will have a sequence (
in increasing order) placed at the left of the N_maxA, and a s
approach it by
1) finding the largest two values in the array of N, denoted as N_maxA and N
_maxB and (N_maxA>N_maxB).
2) place N_maxA and N_maxB at the R^th and (L-1)^th position. Note that you
can place it in the opposite way, by placing N_maxB and N_maxA at the L^th
and (R-1)^th position
3) assuming we go with the first arrangement, then we will have a sequence (
in increasing order) placed at the left of the N_maxA, and a s
B*i
11 楼
本来我也打算在costco, cvs 照的，连买菜带照相一次就齐了，不想到costco 一看，
还不少人在排队都是一水的小印，那个大妈就拿着个大概二百不到的小dc挨个拍，想想
还是算了，回家用咱那单反diy 吧，送到cvs 两元8张，搞定。麻烦的是家里某人太挑
剔，要海选出一张满意的，也折腾了半天。
还不少人在排队都是一水的小印，那个大妈就拿着个大概二百不到的小dc挨个拍，想想
还是算了，回家用咱那单反diy 吧，送到cvs 两元8张，搞定。麻烦的是家里某人太挑
剔，要海选出一张满意的，也折腾了半天。
h*i
12 楼
因为Harvard不在系统里面？在系统里面的好学校的学生我大都面过，Yale, Princeton
，Columbia, etc.
Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
【在 f******2 的大作中提到】
: 其实你说的abc最强根本道理在这个问题。
: social network那个电影里有答案
，Columbia, etc.
Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
【在 f******2 的大作中提到】
: 其实你说的abc最强根本道理在这个问题。
: social network那个电影里有答案
a*a
13 楼
bless
s*t
14 楼
Longest Increasing Subsequence
blocks
}
【在 m*****f 的大作中提到】
: You are given N blocks of height 1…N. In how many ways can you arrange
: these blocks in a row such that when viewed from left you see only L blocks
: (rest are hidden by taller blocks) and when seen from right you see only R
: blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
: while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
blocks
}
【在 m*****f 的大作中提到】
: You are given N blocks of height 1…N. In how many ways can you arrange
: these blocks in a row such that when viewed from left you see only L blocks
: (rest are hidden by taller blocks) and when seen from right you see only R
: blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
: while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
c*i
15 楼
costco, cvs 照方便
diy 选照片麻烦 便宜
diy 选照片麻烦 便宜
f*2
16 楼
记得有个场景，当时zackerburg和那兄弟俩进了校长办公室，校长的大意就是说，你们
不是想如何take a job，我们培养你们如何make jobs。
当时我就恍然大悟，哇，这可能就是我这么多年没有遇到过havard的人的原因。
时间太长，具体情节记不清了。
: 因为Harvard不在系统里面？在系统里面的好学校的学生我大都面过，Yale,
Princeton
: ，Columbia, etc.
: Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
【在 h*i 的大作中提到】
: 因为Harvard不在系统里面？在系统里面的好学校的学生我大都面过，Yale, Princeton
: ，Columbia, etc.
: Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
不是想如何take a job，我们培养你们如何make jobs。
当时我就恍然大悟，哇，这可能就是我这么多年没有遇到过havard的人的原因。
时间太长，具体情节记不清了。
: 因为Harvard不在系统里面？在系统里面的好学校的学生我大都面过，Yale,
Princeton
: ，Columbia, etc.
: Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
【在 h*i 的大作中提到】
: 因为Harvard不在系统里面？在系统里面的好学校的学生我大都面过，Yale, Princeton
: ，Columbia, etc.
: Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
c*b
17 楼
别泄气. 还有很多.
m*f
18 楼
sigh..不是让你求LIS...回帖不看帖吗
【在 s***t 的大作中提到】
: Longest Increasing Subsequence
:
: blocks
: }
【在 s***t 的大作中提到】
: Longest Increasing Subsequence
:
: blocks
: }
H*S
19 楼
任何一个标明是照passport photo的连锁店都可以，walgreens, CVS, costco, kinko'
s，无所谓的。
s，无所谓的。
h*i
20 楼
怎么可能没遇到过Harvard的人？我接触的圈子里，Harvard毕业的多了。读博的时候最
赏识我的一个老师就是Havard本科Stanford博士。工作的时候同事里面Harvard毕业的
随便就能想出几个人来。Harvard真不是什么特别的，不必神话了。
点？
【在 f******2 的大作中提到】
: 记得有个场景，当时zackerburg和那兄弟俩进了校长办公室，校长的大意就是说，你们
: 不是想如何take a job，我们培养你们如何make jobs。
: 当时我就恍然大悟，哇，这可能就是我这么多年没有遇到过havard的人的原因。
: 时间太长，具体情节记不清了。
:
:
: 因为Harvard不在系统里面？在系统里面的好学校的学生我大都面过，Yale,
: Princeton
:
: ，Columbia, etc.
:
: Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
:
赏识我的一个老师就是Havard本科Stanford博士。工作的时候同事里面Harvard毕业的
随便就能想出几个人来。Harvard真不是什么特别的，不必神话了。
点？
【在 f******2 的大作中提到】
: 记得有个场景，当时zackerburg和那兄弟俩进了校长办公室，校长的大意就是说，你们
: 不是想如何take a job，我们培养你们如何make jobs。
: 当时我就恍然大悟，哇，这可能就是我这么多年没有遇到过havard的人的原因。
: 时间太长，具体情节记不清了。
:
:
: 因为Harvard不在系统里面？在系统里面的好学校的学生我大都面过，Yale,
: Princeton
:
: ，Columbia, etc.
:
: Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
:
s*g
21 楼
Bless
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
m*f
22 楼
step 5 不对, 你确定了最高的两个, 并不能保证剩下的L-1/R-1个slot, 就是说MaxA左
边或者MaxB右边, 怎么放都一定100%排成L长或者R长的LIS. 矮的放在高的后面就看不
见了
N
you
(
【在 u******p 的大作中提到】
: honestly, i am not familiar with DP, to me, it might be easier if we
: approach it by
: 1) finding the largest two values in the array of N, denoted as N_maxA and N
: _maxB and (N_maxA>N_maxB).
: 2) place N_maxA and N_maxB at the R^th and (L-1)^th position. Note that you
: can place it in the opposite way, by placing N_maxB and N_maxA at the L^th
: and (R-1)^th position
: 3) assuming we go with the first arrangement, then we will have a sequence (
: in increasing order) placed at the left of the N_maxA, and a s
边或者MaxB右边, 怎么放都一定100%排成L长或者R长的LIS. 矮的放在高的后面就看不
见了
N
you
(
【在 u******p 的大作中提到】
: honestly, i am not familiar with DP, to me, it might be easier if we
: approach it by
: 1) finding the largest two values in the array of N, denoted as N_maxA and N
: _maxB and (N_maxA>N_maxB).
: 2) place N_maxA and N_maxB at the R^th and (L-1)^th position. Note that you
: can place it in the opposite way, by placing N_maxB and N_maxA at the L^th
: and (R-1)^th position
: 3) assuming we go with the first arrangement, then we will have a sequence (
: in increasing order) placed at the left of the N_maxA, and a s
s*b
23 楼
自己照吧，去costco什么的排队都老半天。而且5块钱才2张。
h*i
24 楼
差不多每个精英点的学校都这么说吧? “我们是培养领袖的”。说辞而已。
点？
【在 f******2 的大作中提到】
: 记得有个场景，当时zackerburg和那兄弟俩进了校长办公室，校长的大意就是说，你们
: 不是想如何take a job，我们培养你们如何make jobs。
: 当时我就恍然大悟，哇，这可能就是我这么多年没有遇到过havard的人的原因。
: 时间太长，具体情节记不清了。
:
:
: 因为Harvard不在系统里面？在系统里面的好学校的学生我大都面过，Yale,
: Princeton
:
: ，Columbia, etc.
:
: Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
:
点？
【在 f******2 的大作中提到】
: 记得有个场景，当时zackerburg和那兄弟俩进了校长办公室，校长的大意就是说，你们
: 不是想如何take a job，我们培养你们如何make jobs。
: 当时我就恍然大悟，哇，这可能就是我这么多年没有遇到过havard的人的原因。
: 时间太长，具体情节记不清了。
:
:
: 因为Harvard不在系统里面？在系统里面的好学校的学生我大都面过，Yale,
: Princeton
:
: ，Columbia, etc.
:
: Harvard计算机可能也不太强吧，比Stanford, MIT, Berkeley啥的是不是要差点？
:
o*u
25 楼
不用着急，我当年是等了半年才等到offer的。
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
k*e
26 楼
是对的
我最爱的题目类型
希望被问到
L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x= L-1, y >= R-1,
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
我最爱的题目类型
希望被问到
L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
e*o
27 楼
我在一个医学院 同事老板基本上除了我全是名校
国内的时候还觉得名校如何 美国遍地名校
【在 h*i 的大作中提到】
: 怎么可能没遇到过Harvard的人？我接触的圈子里，Harvard毕业的多了。读博的时候最
: 赏识我的一个老师就是Havard本科Stanford博士。工作的时候同事里面Harvard毕业的
: 随便就能想出几个人来。Harvard真不是什么特别的，不必神话了。
:
: 点？
国内的时候还觉得名校如何 美国遍地名校
【在 h*i 的大作中提到】
: 怎么可能没遇到过Harvard的人？我接触的圈子里，Harvard毕业的多了。读博的时候最
: 赏识我的一个老师就是Havard本科Stanford博士。工作的时候同事里面Harvard毕业的
: 随便就能想出几个人来。Harvard真不是什么特别的，不必神话了。
:
: 点？
x*s
28 楼
什么原因如此拖拉？
【在 o****u 的大作中提到】
: 不用着急，我当年是等了半年才等到offer的。
【在 o****u 的大作中提到】
: 不用着急，我当年是等了半年才等到offer的。
g*y
29 楼
我觉得你做的不错呢
L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x= L-1, y >= R-1,
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
x*u
30 楼
美国的名校出名不是因为难考，而是因为原则上不招外国人
算美国本土的录取率这几个学校不如印度理工牛呢
【在 e*******o 的大作中提到】
: 我在一个医学院 同事老板基本上除了我全是名校
: 国内的时候还觉得名校如何 美国遍地名校
算美国本土的录取率这几个学校不如印度理工牛呢
【在 e*******o 的大作中提到】
: 我在一个医学院 同事老板基本上除了我全是名校
: 国内的时候还觉得名校如何 美国遍地名校
l*y
31 楼
blessing!!
m*f
32 楼
就怕有什么trick没想到阿, 战战兢兢的
【在 g*******y 的大作中提到】
: 我觉得你做的不错呢
:
: L,
【在 g*******y 的大作中提到】
: 我觉得你做的不错呢
:
: L,
T*x
33 楼
也不招外国人的儿子。
【在 x****u 的大作中提到】
: 美国的名校出名不是因为难考，而是因为原则上不招外国人
: 算美国本土的录取率这几个学校不如印度理工牛呢
【在 x****u 的大作中提到】
: 美国的名校出名不是因为难考，而是因为原则上不招外国人
: 算美国本土的录取率这几个学校不如印度理工牛呢
g*a
34 楼
bless
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
【在 A**E 的大作中提到】
: 距离最后一个candidate结束已经2周了
: 今年第一个on site就这么没戏勒
: 求bless
g*y
35 楼
trick估计就是在算f(a,b)那里，有好的方法，也有差一点的方法。
【在 m*****f 的大作中提到】
: 就怕有什么trick没想到阿, 战战兢兢的
【在 m*****f 的大作中提到】
: 就怕有什么trick没想到阿, 战战兢兢的
W*o
36 楼
美国的名校不像国内的名校大而全，美国这里所谓的名校分几种，比如像哈佛，布朗这
样老牌的；大多数美国名校只是几个学科比较牛（或只是理科或只是工科牛），像后起
之秀斯坦福这样的土豪，也并不是每个学科都牛。
国内的名校资源更集中，美国的名校资源相对平均一点。
话说回来，hci的样本分布有问题，导致他的结论有问题。就好比 在mall里看见的人绝
大多数是女人，从而推论世界上的女人占大多数，这种结论就有点可笑了。
我在一个医学院 同事老板基本上除了我全是名校
【在 e*******o 的大作中提到】
: 我在一个医学院 同事老板基本上除了我全是名校
: 国内的时候还觉得名校如何 美国遍地名校
样老牌的；大多数美国名校只是几个学科比较牛（或只是理科或只是工科牛），像后起
之秀斯坦福这样的土豪，也并不是每个学科都牛。
国内的名校资源更集中，美国的名校资源相对平均一点。
话说回来，hci的样本分布有问题，导致他的结论有问题。就好比 在mall里看见的人绝
大多数是女人，从而推论世界上的女人占大多数，这种结论就有点可笑了。
我在一个医学院 同事老板基本上除了我全是名校
【在 e*******o 的大作中提到】
: 我在一个医学院 同事老板基本上除了我全是名校
: 国内的时候还觉得名校如何 美国遍地名校
o*u
37 楼
Second on the list。First on the list拖半年把学校拒了。害得我悲催了半年 ：（
【在 x***s 的大作中提到】
: 什么原因如此拖拉？
【在 x***s 的大作中提到】
: 什么原因如此拖拉？
c*y
38 楼
f(a,b)的递推式似乎不好搞啊, any clue here?
【在 g*******y 的大作中提到】
: trick估计就是在算f(a,b)那里，有好的方法，也有差一点的方法。
【在 g*******y 的大作中提到】
: trick估计就是在算f(a,b)那里，有好的方法，也有差一点的方法。
m*r
39 楼
你还不如说我在厕所里碰到的全是男的，所以世界上全是男人。
名校的作用就是个名牌衣服 能boost你的career,机会比别人多一点而已 controlling
other factors
什么make/take job更扯。 请问这位校长自己make了几个job? 他培养的学生能makejob
的人多，还是takejob的人多? 他自己就是个takejob的人，还说什么makejob
名校的作用就是个名牌衣服 能boost你的career,机会比别人多一点而已 controlling
other factors
什么make/take job更扯。 请问这位校长自己make了几个job? 他培养的学生能makejob
的人多，还是takejob的人多? 他自己就是个takejob的人，还说什么makejob
x*s
40 楼
你最后去的是这个学校吗？
【在 o****u 的大作中提到】
: Second on the list。First on the list拖半年把学校拒了。害得我悲催了半年 ：（
【在 o****u 的大作中提到】
: Second on the list。First on the list拖半年把学校拒了。害得我悲催了半年 ：（
b*j
41 楼
错的吧？
4 1 2 3应该算是f(4, 3)中的一种吧，但是只能看到4
L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x= L-1, y >= R-1,
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
4 1 2 3应该算是f(4, 3)中的一种吧，但是只能看到4
L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
e*o
42 楼
美国大学二战后，不少确实做出了不少成就，名校也名副其实。
国内大学因为国家落后，名校太少。
【在 W***o 的大作中提到】
: 美国的名校不像国内的名校大而全，美国这里所谓的名校分几种，比如像哈佛，布朗这
: 样老牌的；大多数美国名校只是几个学科比较牛（或只是理科或只是工科牛），像后起
: 之秀斯坦福这样的土豪，也并不是每个学科都牛。
: 国内的名校资源更集中，美国的名校资源相对平均一点。
: 话说回来，hci的样本分布有问题，导致他的结论有问题。就好比 在mall里看见的人绝
: 大多数是女人，从而推论世界上的女人占大多数，这种结论就有点可笑了。
:
: 我在一个医学院 同事老板基本上除了我全是名校
国内大学因为国家落后，名校太少。
【在 W***o 的大作中提到】
: 美国的名校不像国内的名校大而全，美国这里所谓的名校分几种，比如像哈佛，布朗这
: 样老牌的；大多数美国名校只是几个学科比较牛（或只是理科或只是工科牛），像后起
: 之秀斯坦福这样的土豪，也并不是每个学科都牛。
: 国内的名校资源更集中，美国的名校资源相对平均一点。
: 话说回来，hci的样本分布有问题，导致他的结论有问题。就好比 在mall里看见的人绝
: 大多数是女人，从而推论世界上的女人占大多数，这种结论就有点可笑了。
:
: 我在一个医学院 同事老板基本上除了我全是名校
g*y
43 楼
我觉得他(她)的思路应该是对的，不过表述可能有些问题:
f(a,b)应该是：a个数，固定从一个方向看过去(比如左边)，能看到b个数，有多少种情
况的结果。
【在 b****j 的大作中提到】
: 错的吧？
: 4 1 2 3应该算是f(4, 3)中的一种吧，但是只能看到4
:
: L,
f(a,b)应该是：a个数，固定从一个方向看过去(比如左边)，能看到b个数，有多少种情
况的结果。
【在 b****j 的大作中提到】
: 错的吧？
: 4 1 2 3应该算是f(4, 3)中的一种吧，但是只能看到4
:
: L,
e*o
44 楼
hci 说的是他面试的人，并无啥问题。
至于在更大的层面能否hold住，我肯定不赞同。
【在 f******2 的大作中提到】
: 其实你说的abc最强根本道理在这个问题。
: social network那个电影里有答案
至于在更大的层面能否hold住，我肯定不赞同。
【在 f******2 的大作中提到】
: 其实你说的abc最强根本道理在这个问题。
: social network那个电影里有答案
m*f
45 楼
假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
这表述有问题? 我又没说什么左阿右阿的, 数列中最长递增子序列阿, 不从左边开始从
哪儿开始阿...
【在 g*******y 的大作中提到】
: 我觉得他(她)的思路应该是对的，不过表述可能有些问题:
: f(a,b)应该是：a个数，固定从一个方向看过去(比如左边)，能看到b个数，有多少种情
: 况的结果。
这表述有问题? 我又没说什么左阿右阿的, 数列中最长递增子序列阿, 不从左边开始从
哪儿开始阿...
【在 g*******y 的大作中提到】
: 我觉得他(她)的思路应该是对的，不过表述可能有些问题:
: f(a,b)应该是：a个数，固定从一个方向看过去(比如左边)，能看到b个数，有多少种情
: 况的结果。
c*y
46 楼
赫赫，现在的问题是这个f(a,b)怎么求得到，似乎不太easy
就问这个f(a,b)的问题估计也很难
【在 m*****f 的大作中提到】
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
: 这表述有问题? 我又没说什么左阿右阿的, 数列中最长递增子序列阿, 不从左边开始从
: 哪儿开始阿...
就问这个f(a,b)的问题估计也很难
【在 m*****f 的大作中提到】
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
: 这表述有问题? 我又没说什么左阿右阿的, 数列中最长递增子序列阿, 不从左边开始从
: 哪儿开始阿...
m*f
47 楼
假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
设最大的那个数最终位置为x, 显然b<=x<=a, 得
f(a,b) = f(a-1, b-1) (x=a的情况) + f(a-2, b-1)*(a-1) (x=a-1的情况, a位置可放
任一数) + f(a-3, b-1)*(a-1)*(a-2) (x=a-2, a, a-1位置可放任意数) ....
until...f(b-1, b-1) * (a-1) * (a-2) ...(a-b)
声明一个axb的数组, 显然
f(*,1) = 1
f(a, b) = 1 if a = b
f(a, b) = 0 if a < b
然后填满这个数组, 我刚才懒得写完, 现在就写完罢
当然, 求更好的方法...
【在 c***y 的大作中提到】
: 赫赫，现在的问题是这个f(a,b)怎么求得到，似乎不太easy
: 就问这个f(a,b)的问题估计也很难
设最大的那个数最终位置为x, 显然b<=x<=a, 得
f(a,b) = f(a-1, b-1) (x=a的情况) + f(a-2, b-1)*(a-1) (x=a-1的情况, a位置可放
任一数) + f(a-3, b-1)*(a-1)*(a-2) (x=a-2, a, a-1位置可放任意数) ....
until...f(b-1, b-1) * (a-1) * (a-2) ...(a-b)
声明一个axb的数组, 显然
f(*,1) = 1
f(a, b) = 1 if a = b
f(a, b) = 0 if a < b
然后填满这个数组, 我刚才懒得写完, 现在就写完罢
当然, 求更好的方法...
【在 c***y 的大作中提到】
: 赫赫，现在的问题是这个f(a,b)怎么求得到，似乎不太easy
: 就问这个f(a,b)的问题估计也很难
x*y
48 楼
How about
f(a,b)=sum_{k=b-1}^{a-1} f(k,b-1)×P(a-1,a-1-k)
with the initial condition f(a,1)=(a-1)! with a>0
【在 c***y 的大作中提到】
: 赫赫，现在的问题是这个f(a,b)怎么求得到，似乎不太easy
: 就问这个f(a,b)的问题估计也很难
f(a,b)=sum_{k=b-1}^{a-1} f(k,b-1)×P(a-1,a-1-k)
with the initial condition f(a,1)=(a-1)! with a>0
【在 c***y 的大作中提到】
: 赫赫，现在的问题是这个f(a,b)怎么求得到，似乎不太easy
: 就问这个f(a,b)的问题估计也很难
b*j
49 楼
不知道有没有解析的公式，写了个递推的：
#include
int N,L,R;
long long num[128][128];
int main() {
int i,j,k;
scanf("%d%d%d", &N, &L, &R);
num[1][1] = 1;
for (i=2;i<=N;++i)
for (j=i;j>=1;--j)
for (k=i-j+1;k>=1;--k)
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
printf("%lld\n", num[L][R]);
return 0;
}
blocks
}
【在 m*****f 的大作中提到】
: You are given N blocks of height 1…N. In how many ways can you arrange
: these blocks in a row such that when viewed from left you see only L blocks
: (rest are hidden by taller blocks) and when seen from right you see only R
: blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
: while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
#include
int N,L,R;
long long num[128][128];
int main() {
int i,j,k;
scanf("%d%d%d", &N, &L, &R);
num[1][1] = 1;
for (i=2;i<=N;++i)
for (j=i;j>=1;--j)
for (k=i-j+1;k>=1;--k)
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
printf("%lld\n", num[L][R]);
return 0;
}
blocks
}
【在 m*****f 的大作中提到】
: You are given N blocks of height 1…N. In how many ways can you arrange
: these blocks in a row such that when viewed from left you see only L blocks
: (rest are hidden by taller blocks) and when seen from right you see only R
: blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
: while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
g*y
50 楼
nice!
But I think you can further improve, if you combine your idea with mudhoof's
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
But I think you can further improve, if you combine your idea with mudhoof's
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
k*e
51 楼
why dont you just say the answer?
just not that to get f(n, l, r)
define a_ln means given n numbers that look from left we can see just l of
them
b_rn means given n numbers that look from right and we can see just r
then a_ln=b_ln
to get a_ln, decompose on the smallest element
a_ln=a_l-1 n-1 + (n-1)a_l n-1
for n numbers with L R as given, the total time would be max(L, R)n to get a
_ij
then f(n,L,R) can be represented as a_ln, b_rn as have done by some ppl
before
thus the total time is just max(
【在 g*******y 的大作中提到】
: nice!
: But I think you can further improve, if you combine your idea with mudhoof's
just not that to get f(n, l, r)
define a_ln means given n numbers that look from left we can see just l of
them
b_rn means given n numbers that look from right and we can see just r
then a_ln=b_ln
to get a_ln, decompose on the smallest element
a_ln=a_l-1 n-1 + (n-1)a_l n-1
for n numbers with L R as given, the total time would be max(L, R)n to get a
_ij
then f(n,L,R) can be represented as a_ln, b_rn as have done by some ppl
before
thus the total time is just max(
【在 g*******y 的大作中提到】
: nice!
: But I think you can further improve, if you combine your idea with mudhoof's
b*j
52 楼
I think his idea is wrong.
's
【在 g*******y 的大作中提到】
: nice!
: But I think you can further improve, if you combine your idea with mudhoof's
's
【在 g*******y 的大作中提到】
: nice!
: But I think you can further improve, if you combine your idea with mudhoof's
g*y
53 楼
那我来转述一遍:
n个blocks，最高那个假设在位置k上，
可能的情况数有:
C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)
f(i,j)代表：i个不同的blocks(block的具体长度不重要，重要的只是大小顺序)，从左
往右看，能看到j个，有多少种情况
用你的思路来算f(i,j),就只需要两重循环，降低了一个维度的时间复杂度
【在 b****j 的大作中提到】
: I think his idea is wrong.
:
: 's
n个blocks，最高那个假设在位置k上，
可能的情况数有:
C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)
f(i,j)代表：i个不同的blocks(block的具体长度不重要，重要的只是大小顺序)，从左
往右看，能看到j个，有多少种情况
用你的思路来算f(i,j),就只需要两重循环，降低了一个维度的时间复杂度
【在 b****j 的大作中提到】
: I think his idea is wrong.
:
: 's
m*f
54 楼
...if you say someone is wrong, at least also explain why...
【在 b****j 的大作中提到】
: I think his idea is wrong.
:
: 's
【在 b****j 的大作中提到】
: I think his idea is wrong.
:
: 's
b*j
55 楼
算f(i,j)是两重循环，那么算最终答案是几重循环？
【在 g*******y 的大作中提到】
: 那我来转述一遍:
: n个blocks，最高那个假设在位置k上，
: 可能的情况数有:
: C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)
: f(i,j)代表：i个不同的blocks(block的具体长度不重要，重要的只是大小顺序)，从左
: 往右看，能看到j个，有多少种情况
: 用你的思路来算f(i,j),就只需要两重循环，降低了一个维度的时间复杂度
【在 g*******y 的大作中提到】
: 那我来转述一遍:
: n个blocks，最高那个假设在位置k上，
: 可能的情况数有:
: C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)
: f(i,j)代表：i个不同的blocks(block的具体长度不重要，重要的只是大小顺序)，从左
: 往右看，能看到j个，有多少种情况
: 用你的思路来算f(i,j),就只需要两重循环，降低了一个维度的时间复杂度
b*j
56 楼
I explained before:
in your notation, f(a, b) means the number of permutations of a numbers with
the longest increasing subsequence length being b.
4 1 2 3 is one of the sequence for f(4, 3), but when looking from left, only
4 can be seen.
【在 m*****f 的大作中提到】
: ...if you say someone is wrong, at least also explain why...
in your notation, f(a, b) means the number of permutations of a numbers with
the longest increasing subsequence length being b.
4 1 2 3 is one of the sequence for f(4, 3), but when looking from left, only
4 can be seen.
【在 m*****f 的大作中提到】
: ...if you say someone is wrong, at least also explain why...
g*y
57 楼
这两重循环是主要的
假设所有的f(i,j)都已经算出来并存下来了：
最后一步就是算C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)对k求和的复杂度，也就是O（n)吧
【在 b****j 的大作中提到】
: 算f(i,j)是两重循环，那么算最终答案是几重循环？
假设所有的f(i,j)都已经算出来并存下来了：
最后一步就是算C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)对k求和的复杂度，也就是O（n)吧
【在 b****j 的大作中提到】
: 算f(i,j)是两重循环，那么算最终答案是几重循环？
b*j
58 楼
了解了
n)吧
【在 g*******y 的大作中提到】
: 这两重循环是主要的
: 假设所有的f(i,j)都已经算出来并存下来了：
: 最后一步就是算C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)对k求和的复杂度，也就是O（n)吧
n)吧
【在 g*******y 的大作中提到】
: 这两重循环是主要的
: 假设所有的f(i,j)都已经算出来并存下来了：
: 最后一步就是算C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)对k求和的复杂度，也就是O（n)吧
m*f
59 楼
你说得对, notation写错了, f(a,b)应该是a个元素从左边看有b个的数目, 不是简单的LIS, 但是好像想法还是正确的.
前面小尾羊的评论没错, 我没注意到
with
only
【在 b****j 的大作中提到】
: I explained before:
: in your notation, f(a, b) means the number of permutations of a numbers with
: the longest increasing subsequence length being b.
: 4 1 2 3 is one of the sequence for f(4, 3), but when looking from left, only
: 4 can be seen.
前面小尾羊的评论没错, 我没注意到
with
only
【在 b****j 的大作中提到】
: I explained before:
: in your notation, f(a, b) means the number of permutations of a numbers with
: the longest increasing subsequence length being b.
: 4 1 2 3 is one of the sequence for f(4, 3), but when looking from left, only
: 4 can be seen.
r*o
60 楼
这句是什么意思啊？
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
r*o
61 楼
这句能解释一下吗？
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
b*j
62 楼
递推，从高到低一个一个的放，现在放第i个高的
如果它被放到最左边，从左边看可看到的就多了一个
如果它被放到最右边，从右边看可看到的就多了一个
否则放到中间有i-2种方法，这块不能被看到了
【在 r****o 的大作中提到】
: 这句是什么意思啊？
: num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
如果它被放到最左边，从左边看可看到的就多了一个
如果它被放到最右边，从右边看可看到的就多了一个
否则放到中间有i-2种方法，这块不能被看到了
【在 r****o 的大作中提到】
: 这句是什么意思啊？
: num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
c*y
63 楼
I guess you want to say:
num[j][k] = num[j-1][k] * (i - 2) + num[j-1][k] + num[j-1][k-1];
~~ ~~
not
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
【在 b****j 的大作中提到】
: 递推，从高到低一个一个的放，现在放第i个高的
: 如果它被放到最左边，从左边看可看到的就多了一个
: 如果它被放到最右边，从右边看可看到的就多了一个
: 否则放到中间有i-2种方法，这块不能被看到了
num[j][k] = num[j-1][k] * (i - 2) + num[j-1][k] + num[j-1][k-1];
~~ ~~
not
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
【在 b****j 的大作中提到】
: 递推，从高到低一个一个的放，现在放第i个高的
: 如果它被放到最左边，从左边看可看到的就多了一个
: 如果它被放到最右边，从右边看可看到的就多了一个
: 否则放到中间有i-2种方法，这块不能被看到了
u*s
64 楼
No, you haven't fully understood his codes.
He used a common trick to reuse the variable/save space.
【在 c***y 的大作中提到】
: I guess you want to say:
: num[j][k] = num[j-1][k] * (i - 2) + num[j-1][k] + num[j-1][k-1];
: ~~ ~~
: not
: num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
He used a common trick to reuse the variable/save space.
【在 c***y 的大作中提到】
: I guess you want to say:
: num[j][k] = num[j-1][k] * (i - 2) + num[j-1][k] + num[j-1][k-1];
: ~~ ~~
: not
: num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
c*y
65 楼
if you think this way from another perspective:
f(a,b) can be constructed by either adding the lowest block (a-th) in either
the first or the other places based on existing (a-1) blocks, then
f(a,b) = f(a-1,b)*(a-1) + f(a-1, b-1)
this is the interative way for your method
【在 m*****f 的大作中提到】
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
: 设最大的那个数最终位置为x, 显然b<=x<=a, 得
: f(a,b) = f(a-1, b-1) (x=a的情况) + f(a-2, b-1)*(a-1) (x=a-1的情况, a位置可放
: 任一数) + f(a-3, b-1)*(a-1)*(a-2) (x=a-2, a, a-1位置可放任意数) ....
: until...f(b-1, b-1) * (a-1) * (a-2) ...(a-b)
: 声明一个axb的数组, 显然
: f(*,1) = 1
: f(a, b) = 1 if a = b
: f(a, b) = 0 if a < b
: 然后填满这个数组, 我刚才懒得写完, 现在就写完罢
f(a,b) can be constructed by either adding the lowest block (a-th) in either
the first or the other places based on existing (a-1) blocks, then
f(a,b) = f(a-1,b)*(a-1) + f(a-1, b-1)
this is the interative way for your method
【在 m*****f 的大作中提到】
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
: 设最大的那个数最终位置为x, 显然b<=x<=a, 得
: f(a,b) = f(a-1, b-1) (x=a的情况) + f(a-2, b-1)*(a-1) (x=a-1的情况, a位置可放
: 任一数) + f(a-3, b-1)*(a-1)*(a-2) (x=a-2, a, a-1位置可放任意数) ....
: until...f(b-1, b-1) * (a-1) * (a-2) ...(a-b)
: 声明一个axb的数组, 显然
: f(*,1) = 1
: f(a, b) = 1 if a = b
: f(a, b) = 0 if a < b
: 然后填满这个数组, 我刚才懒得写完, 现在就写完罢
b*e
66 楼
Some small improvement:
Instead of computing number of solutions, compute probability. Then you
don't have to compute the crap of C(n-1, x).
n-L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x= L-1, y >= R-1,
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
Instead of computing number of solutions, compute probability. Then you
don't have to compute the crap of C(n-1, x).
n-L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
r*o
67 楼
C(n-1,x)这里是什么意思阿，是组合数吗？
【在 b***e 的大作中提到】
: Some small improvement:
: Instead of computing number of solutions, compute probability. Then you
: don't have to compute the crap of C(n-1, x).
:
: n-L,
【在 b***e 的大作中提到】
: Some small improvement:
: Instead of computing number of solutions, compute probability. Then you
: don't have to compute the crap of C(n-1, x).
:
: n-L,
z*e
68 楼
。。。。。
这个...呃...我觉得没超过高考的难度啊。。。。
基本上，你能看到的（先不管左右，假设从左边吧）就是已经sorted了，就好像小学体
育课上老师说“最高的L个站出来”----（剩下的无视）；然后把这L个排序。
在这L个中最矮的一个肯定在最左边，这个位置固定，剩下L-1个站好，中间留空位，很
好，现在还剩N-L个人，有L-2个空位，每个空位可以容纳0-（N-L)个人，这就是典型的
高考水准排列组合题：有K个抽屉，M个球，问有几种放球的方法...
这个...呃...我觉得没超过高考的难度啊。。。。
基本上，你能看到的（先不管左右，假设从左边吧）就是已经sorted了，就好像小学体
育课上老师说“最高的L个站出来”----（剩下的无视）；然后把这L个排序。
在这L个中最矮的一个肯定在最左边，这个位置固定，剩下L-1个站好，中间留空位，很
好，现在还剩N-L个人，有L-2个空位，每个空位可以容纳0-（N-L)个人，这就是典型的
高考水准排列组合题：有K个抽屉，M个球，问有几种放球的方法...
e*l
69 楼
楼上想法不对，空位放的人不能比前面紧挨的高，但可以比前面的前面高。怎么算这个
组合？再说还有右边看的限制。
组合？再说还有右边看的限制。
z*e
70 楼
你说“前面的前面”，是指首先选出的Top L个人么？如果空位的人比这个高，那么这
top L就选错了。
嗯...不过我这个不能解决右边看的问题，要再想想。
【在 e***l 的大作中提到】
: 楼上想法不对，空位放的人不能比前面紧挨的高，但可以比前面的前面高。怎么算这个
: 组合？再说还有右边看的限制。
top L就选错了。
嗯...不过我这个不能解决右边看的问题，要再想想。
【在 e***l 的大作中提到】
: 楼上想法不对，空位放的人不能比前面紧挨的高，但可以比前面的前面高。怎么算这个
: 组合？再说还有右边看的限制。
e*l
71 楼
说说我的想法，设g(N,L,R)为最终所求，那么根据最高的block的位置i=(1...N)，有N
个情况。于是
g(N,L,R)=Σ C(N-1, i-1) * f(i-1,L-1) * f(N-i,R-1)
i=1,2...N
其中第一项C(n,r)是组合数记号，从n个里面选r个的选法，
第二项f(n,a)表示只考虑最高的左边那些block，用i-1个block摆出从左看，有L-1个
block可见的摆法。
第三项是从右看的情况，函数是同一个（因为对称）。
接下来再考虑f，同样根据最高的block的位置，f可以递归求得
f(N,L) = Σ f(i-1,L-1)
i=1,2...N
再有几个初始值就可以求出g，但是直接的解析式似乎很麻烦。。。
测试了几个例子基本正确，大家看看正确吗？
代码：
#include "stdafx.h"
//求x的阶乘
int factorial(int x){
if(x==0) return 1;
int r=1;
for(int i=1;i<=x;i++)
r=r*i;
return r;
}
//求组
个情况。于是
g(N,L,R)=Σ C(N-1, i-1) * f(i-1,L-1) * f(N-i,R-1)
i=1,2...N
其中第一项C(n,r)是组合数记号，从n个里面选r个的选法，
第二项f(n,a)表示只考虑最高的左边那些block，用i-1个block摆出从左看，有L-1个
block可见的摆法。
第三项是从右看的情况，函数是同一个（因为对称）。
接下来再考虑f，同样根据最高的block的位置，f可以递归求得
f(N,L) = Σ f(i-1,L-1)
i=1,2...N
再有几个初始值就可以求出g，但是直接的解析式似乎很麻烦。。。
测试了几个例子基本正确，大家看看正确吗？
代码：
#include "stdafx.h"
//求x的阶乘
int factorial(int x){
if(x==0) return 1;
int r=1;
for(int i=1;i<=x;i++)
r=r*i;
return r;
}
//求组
e*l
72 楼
看了下基本和楼主解法一样，呵呵
H*r
73 楼
当L+R==N+1时f(N,L,R)=C(N-1,L)
如果L+R 和 N 接近时可以节省一点。
int HoofNumber(int length, int numLeft, int numRight)
{
int result=0;
if (numLeft+numRight > length+1 || numLeft == 0 || numRight ==0)
{
return 0;
}
else if (numLeft+numRight == length+1)
{
result = Factorial(length-1) / (Factorial(numLeft-1) * Factorial(
length-numLeft));
return result;
}
else
{
result = (HoofNumber(length-1, numLeft-1, numRight)
+ HoofNumber(length-1
如果L+R 和 N 接近时可以节省一点。
int HoofNumber(int length, int numLeft, int numRight)
{
int result=0;
if (numLeft+numRight > length+1 || numLeft == 0 || numRight ==0)
{
return 0;
}
else if (numLeft+numRight == length+1)
{
result = Factorial(length-1) / (Factorial(numLeft-1) * Factorial(
length-numLeft));
return result;
}
else
{
result = (HoofNumber(length-1, numLeft-1, numRight)
+ HoofNumber(length-1
d*n
74 楼
My solutio for f(a, b):
f(a, b) = sum{(C(a-1,0)*f(a-1, b-1)*P(0,0), C(a-1, 1)*f(a-1-1, b-1)*P(1, 1),
C(a-1, 2)*f(a-1-2, b-1)*P(2,2), ..., C(a-1, i)*f(a-1-i, b-1)*P(i,i)}, i = a
-b;
P(i, i) is the permutation.
N
【在 e***l 的大作中提到】
: 说说我的想法，设g(N,L,R)为最终所求，那么根据最高的block的位置i=(1...N)，有N
: 个情况。于是
: g(N,L,R)=Σ C(N-1, i-1) * f(i-1,L-1) * f(N-i,R-1)
: i=1,2...N
: 其中第一项C(n,r)是组合数记号，从n个里面选r个的选法，
: 第二项f(n,a)表示只考虑最高的左边那些block，用i-1个block摆出从左看，有L-1个
: block可见的摆法。
: 第三项是从右看的情况，函数是同一个（因为对称）。
: 接下来再考虑f，同样根据最高的block的位置，f可以递归求得
: f(N,L) = Σ f(i-1,L-1)
f(a, b) = sum{(C(a-1,0)*f(a-1, b-1)*P(0,0), C(a-1, 1)*f(a-1-1, b-1)*P(1, 1),
C(a-1, 2)*f(a-1-2, b-1)*P(2,2), ..., C(a-1, i)*f(a-1-i, b-1)*P(i,i)}, i = a
-b;
P(i, i) is the permutation.
N
【在 e***l 的大作中提到】
: 说说我的想法，设g(N,L,R)为最终所求，那么根据最高的block的位置i=(1...N)，有N
: 个情况。于是
: g(N,L,R)=Σ C(N-1, i-1) * f(i-1,L-1) * f(N-i,R-1)
: i=1,2...N
: 其中第一项C(n,r)是组合数记号，从n个里面选r个的选法，
: 第二项f(n,a)表示只考虑最高的左边那些block，用i-1个block摆出从左看，有L-1个
: block可见的摆法。
: 第三项是从右看的情况，函数是同一个（因为对称）。
: 接下来再考虑f，同样根据最高的block的位置，f可以递归求得
: f(N,L) = Σ f(i-1,L-1)
l*o
75 楼
我认为这段程序是完全正确的。
不知道有没有解析的公式，写了个递推的：
#include
int N,L,R;
long long num[128][128];
int main() {
int i,j,k;
scanf("%d%d%d", &N, &L, &R);
num[1][1] = 1;
for (i=2;i<=N;++i)
for (j=i;j>=1;--j)
for (k=i-j+1;k>=1;--k)
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
printf("%lld\n", num[L][R]);
return 0;
}
blocks
}
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
不知道有没有解析的公式，写了个递推的：
#include
int N,L,R;
long long num[128][128];
int main() {
int i,j,k;
scanf("%d%d%d", &N, &L, &R);
num[1][1] = 1;
for (i=2;i<=N;++i)
for (j=i;j>=1;--j)
for (k=i-j+1;k>=1;--k)
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
printf("%lld\n", num[L][R]);
return 0;
}
blocks
}
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
y*i
76 楼
从高到低递归，好办法，赞一个。
【在 b****j 的大作中提到】
: 递推，从高到低一个一个的放，现在放第i个高的
: 如果它被放到最左边，从左边看可看到的就多了一个
: 如果它被放到最右边，从右边看可看到的就多了一个
: 否则放到中间有i-2种方法，这块不能被看到了
m*g
77 楼
想了一下。
这个是错的。
either
【在 c***y 的大作中提到】
: if you think this way from another perspective:
: f(a,b) can be constructed by either adding the lowest block (a-th) in either
: the first or the other places based on existing (a-1) blocks, then
: f(a,b) = f(a-1,b)*(a-1) + f(a-1, b-1)
: this is the interative way for your method
这个是错的。
either
【在 c***y 的大作中提到】
: if you think this way from another perspective:
: f(a,b) can be constructed by either adding the lowest block (a-th) in either
: the first or the other places based on existing (a-1) blocks, then
: f(a,b) = f(a-1,b)*(a-1) + f(a-1, b-1)
: this is the interative way for your method
l*i
78 楼
我有一个想法不知道正确不正确，如果用f(N,L,R)代表我们要求的数，那么可以写一个
递归式子：
f(N,L,R)=f(N-1, L-1,R) + f(N-1,L,R-1)
想法是首先最大数N肯定是放在中间的某个地方使得满足L，R的条件，如果我们把N拿掉
的话整个序列就变成了N-1的序列的子问题。这时有两种情况，如果N-1处在原先N的左
边区域的话，那么剩下的序列(以N-1为中心)是个从左看有L-1个，从右看仍有R个的序
列，这就是等号右边第一项，第2项同样道理是当N-1在N右边区域的情况。当然还要有
一些初始条件，最简单的f(1,1,1)=1,可能还需要其他的我没有再多想。不知道这个解
法行不行。
递归式子：
f(N,L,R)=f(N-1, L-1,R) + f(N-1,L,R-1)
想法是首先最大数N肯定是放在中间的某个地方使得满足L，R的条件，如果我们把N拿掉
的话整个序列就变成了N-1的序列的子问题。这时有两种情况，如果N-1处在原先N的左
边区域的话，那么剩下的序列(以N-1为中心)是个从左看有L-1个，从右看仍有R个的序
列，这就是等号右边第一项，第2项同样道理是当N-1在N右边区域的情况。当然还要有
一些初始条件，最简单的f(1,1,1)=1,可能还需要其他的我没有再多想。不知道这个解
法行不行。
相关阅读
著名人類學家胡家奇：人工智慧繼續發展可能滅絕人類Blazor有人玩吗？这东西要是成熟，所有的现有JS框架全得完蛋吧？GPU OpenCL 工作机会，可以remote工作open source ERP and CRMgoogle cloud卖什么公司能翻盘？算法面试大全开始学习Haskell请问网页app 能怎么实现多线程？整天忙一些破事TF-IDF能检查源程序抄袭吗？可能吗：盗用信用卡网上买货居然用了我的IP addressAzure UI 真是难受golang 真香 求叫醒从假杨清 李家 等看wudong的对比The American AI Initiative请教大牛一个很老的VISUAL STUDIO6.0 的问题来看看大佬们撕逼吧为啥Linux这种上古架构竟然能一统服务器的江湖？Perl会不会枯木返春？求教Ubuntu桌面版如何在recovery命令行时上网