Menu Sidebar
Menu

Archive: August 7, 2015

[SPOJ] TEST – Life, the Universe, and Everything

原题: http://www.spoj.com/problems/TEST/ 题目大意: 输出序列, 直到42 分析: 开始刷spoj. 最后一个学期也没TA了, 最后一个学期, 各种老师不给Master TA/RA. 烦恼 烦恼. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); while (n != 42){ out.printLine(n); n = in.readInt(); } }

Reservoir Sampling 水塘抽样

水塘抽样是一组解决数据流取样的方法, 有很多的变种. 它适用的问题有如下特点: 对象为无法在内存中放下的数据, 如不间断数据流, 或者巨大的文件, 数组等. 样本集的大小为k, 并且要求每个样本的取样概率相等. 取样概率可以通过添加权重(weight)来改变取样概率. 一般(无weight)水塘抽样的每个样本的取样概率为: k/(n+1) 水塘抽样的算法实现非常简单, 而且证明简练. 算法如下: 预设数组A, 大小为k. 先取样k个元素. 放入A中. 从k+1元素开始, 每次取得随机数r, 范围为(0,k+1). 如果r <= k, A[r] = S[k+1], S是当前数据流.

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

August 2015
M T W T F S S
 12
3456789
10111213141516
17181920212223
24252627282930
31