Category: 程序设计

使用Google Reader API

Google Reader是非常强大的RSS阅读器,更强大的是他提供了很多API,方便开发第三方应用。最近尝试了调用Google Reader API,发现网上资料不是很全,尤其是中文的,就再总结一下。

Continue reading »

TopCoder Asia-Pacific 2012 解题思路

上月偶然看到网上有提到TopCoder Asia-Pacific 2012 (TopCoder亚太2012),比赛形式为马拉松,题目和传感器定位问题有些类似。因为我今年比较忙,没报名KDD CUP,也没报名TCO,GCJ,这次感觉应该有时间把这个题目做完,就尝试了一下。
题目在此 http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15137&pm=11942
题目大致是说有$n (100 \le n \le 2000)$ 个10维空间上的点,每一维坐标从[0, 1000]的整数中随机选取。对于每一个点,你知道到它最近和最远的点的距离,也知道其他点到这个点距离的远近排序。每个点的每个维度都有一定概率已知,需要算出不知道的维度。

Continue reading »

SFF Compression 纪念第一次TC Marathon

第一次做TC Marathon,基本上可以说是与$擦肩而过,可能是500$或者1000$,有点遗憾。我的算法在Coding Phase可以达到第五名,刚好有$的名次,最终测试掉到了第七名,很杯具。差不多有一半人都挂在了97.sff这个测试文件上,貌似是因为出现了example中没有的情况,于是就0分了(后来下载到数据发现Global Header中的key length是5,但之前所有example都是4)。这个实在太坑爹了。其实算法稍微差一些(最终的第五名其实压缩成绩一般的,但是没挂数据)最后也能进前五的。搞的世界观都改变了……看来应该求稳,不是一直改进就可以的。结果因为那组数据另外还有点其他的问题,管理员删除了,所以杯具消失,又回到了第五名,刚好有$,很圆满,估计不会再改名次了吧。
题目在此
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15023&pm=11734
大致是说有一类文件希望能又快又高效的压缩。文件是一类和DNA测序有关的文件,文件说明在此
http://www.topcoder.com/contest/problem/SFFCompression/sff.html
主要策略是利用文件特征。由于文件中Read Header和Read Data都出现过很多次,因此压缩他们是最重要的。这里主要说我压缩Read Data的策略。

Continue reading »

自己实现64位整数输出

高精度整数是常见的问题之一。但实际上有的时候只是需要比现有整数精度高一点。比如需要128位整数,256位整数等。这个时候就有可能比起去写任意精度整数而言,针对特殊需求写比较好。因为位数比较少,所以好的方式是模仿现有的整数存储方式去实现,用二进制存储。这里面比较麻烦的一步就是输出,因为输出需要写成十进制数,但运算和存储都是二进制形式。于是我自己实现了一个64位整数的输出作为练习。实现64位的原因是为了便于和原有的64位整数输出效率进行对比。

Continue reading »

用C语言玩JSON

JSON是网络上常见的数据传输格式之一,尤其AJAX常用。最近想用C++解析JSON,查了一下JSON的官方网站,翻出来一个不错的库——cJSON库。貌似使用的人不是很多,但是只有两个文件,代码量不大,基本实现了常见的所有功能,用起来还是挺方便的。

Continue reading »