jo32
2012-06-03 00:20:13 +08:00
虽然一开始不知道 OI 是什么，刚才查了之后才发现。
虽然没有搞过 OI，但是我却觉得搞好 OI 对编程有关的事情很有好处，然后我想说：搞 OI 的同志 keep going, it's well worthy.
举个例子，之前在做网站的时候遇到了一个问题：网站中有 N 条条目，然后我给这 N 条条目根据用户偏好定义了一个偏序关系并排序了，我想把 N 条条目每次登录时候都推送给用户若干条，就像豆瓣做的一样，并不是只返回前几条，一个简单想法是按照在序列中的顺序定义一个概率函数 f(n) = y。这样的概率函数有很多，我选择了轮盘赌, 既 f(n) = n / ((1 + n) * n / 2)
然后我们在选择一个的时候我是这样实现的：
在 1 ~ (1 + n) * n / 2 生成一个随机数 y，然后求 (x + 1) * x / 2 = y 的根 x 然后取整，这个数就是按照轮盘赌概率选择出来的序列号。
可以这样做的原因是因为：在 1 ~ (1 + n) * n / 2 中生成一个数必定落在某个区间 (k + 1) * k / 2 ~ (k + 2) * (k + 1) / 2 内，而落在这个区间的概率是 k / ((1 + n) * n / 2)。而易知 f(k) = (k + 1) * k / 2 是一条递增函数（高数中可以求导，高中生可以用两式相减），那么 (x + 1) * x / 2 = y （y 属于 [(k + 1) * k / 2 ~ (k + 2) * (k + 1) / 2]） 的根必落在 [k, k+1] 这个区间内。
如果没有学好 OI 的话，或者没有任何数学知识，可能更会倾向生成一个随机数，然后写个循环判断在哪个区间内然后求 k。前后两者的复杂度分别为 O(1) 和 O(n)，而两者是有区别的。
我举这个例子的目的是为了说明:做 web 也好，做什么都好，要做得比较出色，肯定会遇到很多问题，但是这些问题往往可以形式化到常见的问题上面，很多问题实质上都是例如求最短路径诸如此类的。然而 OI 平时训练的的，就是训练如果形式化问题和如何处理形式化过后的问题。
(好吧，我承认我将 OI 和 ACM 作对比了，虽然我也没搞过 ACM)