面试题目 好像不太一样, 我的是这样的 小红去参观跑步比赛了，场上一共有n个人在赛跑，所有人的速度都不一样。由于规则的原因，第i个人在第i米的位置起跑。如果第i个人被别人超过的时候，第i个人就会被淘汰。假设跑无限长时间，最开始n个人站位从n个人的所有排列中等概率选出一种，那么留在场上的人的数量的期望是多少呢? $n \in [1,1000]$ 当时我的想法 看 n < 1000, 以为是个O(n^2)的dpdp[i] 能从 dp[i+1] 转移过来,然后怎么怎么算,,2333 但是后来发现应该求贡献,把每个位置上的人活下来的期望算出来 然后求和就行了 假设现在1,2,3...n个人都向右跑 对于第i个人来说i+1,i+2,...n都是无影响的.然后考虑i活下来的期望,活下来的情况只有1,2,...i-1没有比i大的,那么第i个人是这些里最大的.也就是说这i个人中最大的那个人的位置是固定的的.那么期望就是 frac{(i-1)!}{i!} = frac{1}{i}; 所以答案就是 \sum_{i=1}{n} = frac{1}{i}; 当时脑抽想的很乱,,233. 一棵树,n个点,边权,q次询问 问两点间边权最大值. 我是 树链剖分+线段树 做的,没仔细看数据范围最小值设成了0 WA了好多发.... 还可以 倍增做, 类比倍增求LCA.