月度归档：2013年09月

Mandelbrot Set 字符画

发表回复

松本一书10.2节介绍优化Ruby运行速度的一个小例程。

运行结果如下，是字符画形式的曼德博集合。看了源码也不清楚为何能做到这样的效果……实在是太神奇了：

[POJ 3159]

发表回复

Candies

差分约束系统。

偶尔发现的很好的题目，对最短路径算法的优化要求较高。

敲了一个SPFA+SLF。其中双端循环队列是手写的，int读入用了getchar处理以节省时间，作了去重边处理。但即使这样也才250ms(g++)。

之后又考虑了用dijkstra。没有优化过直接交果然TLE了。然后开始考虑改进。直接用最小堆来实现最优的dijkstra不太好写，而折中地每次将可能更新最短路径值的点全部push进优先队列的做法是相对比较好实现的，也不会耗损太多时间。第一次写这样的dijkstra，调试了挺久。最后在g++下235ms，c++下1297ms。

吐个小槽……priority_queue里面自定义仿函数时，若比较用的是<，建出来的竟然是大根堆……直觉上怎样也觉得<对应的应该是最小元素在上的小根堆才对……>__< 后记：第二天过来后被Usozki教育了下，他的代码仅仅是SPFA+栈，没有太多优化……但是直接跑出79ms进入第一版了…… 附POJ 3159 by Usozki：

[POJ 3101]

发表回复

Astronomy

分类里写的是扩展欧几里德，但完全用不到。倒是被高精度稍微卡了下。

题意是共有n个星体各以vi的速度绕同一中心公转，问所有星体排成一条直线的周期。

这里注意“排成一条直线”，可以是在圆周的一侧或是另一侧。这里可以取速度最快的星作为运动参照物，求其他星体相对该星的速度，并计算各星体(v0-vi)*x可同时被0.5除尽的最小倍数值x。x即为所求周期值。0.5是因为可在圆周的任意一侧。

用题意vi = 1/ti来表示的话，则1/t0 – 1/ti = (ti-t0) / (t0*ti)，那么取所有分母的lcm为nu，所有分子的gcd为de，则nu/(2*de)则是所求的x了。

思路出来之后，还有部分细节，首先就是去重，然后是计算素数表大小和估计高精度数组最大长度，最后每次求出某分数值时要约分到最简。这里所谓的“高精度”比较有意思的是，用质因数分解的方式保存各个值，这样可非常简便地求gcd和lcm。

Google Round A China New Grad Test 2014

1条回复

早上做了一场Google的在线笔试。

赛制都很熟悉了，和之前的GCJ一样的。比赛时长3小时，共5题，每题都分small和large两组数据。

Problem A. Read Phone Number

读入两个字符串，根据第二个串给出的分段方式，对第一个串进行分析并输出结果。

写第二个串的读入那部分时卡了很久很久。真是对字符串处理太不熟练了，之前北大校赛的时候也是卡很久在字符串处理上。最后还是借鉴了之前用getchar()代替scanf(“%d”,&d)来读入整数以节省时间的方式来读入了每个串分段长度值。提交大数据时一直报含有非ascii字符，结果发现自己数组越界了，如果不是提示这里也就WA掉了。这题做完时已经整整41分钟了。

Problem C. Sorting

随后很自然的看了下board，看到C题过的人很多。点开发现是大水题，两次排序后重构数组输出即可。

Problem B. Rational Number Tree

C题过了后，心态稳下来了。开始读B，发现也是只需要在树上寻根即可，非常简单的处理。大数据提交前看了眼输出，发现竟然有负数。分析到long long最多是2^63-1，遂改成unsigned long long提交。

Problem D. Cross the maze

到这时候已经完全进入状态了。机器人走迷宫的题目，读完后发现也不需要太复杂的处理。分析完之后可以发现，机器人每一步的走法是确定的，而所需要做的就是模拟它走完10000步，看是否经过终点。这里处理写得很凌乱，因为当时以为只有两个小时敲得比较仓促。但提交完发现竟然还有1小时。。。

Problem E. Spaceship Defence

最后一题了，这是唯一稍微考虑了下复杂度的问题。这里大数据是100个源点，图有80000个点，若是稠图最坏情况O(M*N^2)是会TLE的。过了小数据后想了很久怎么对问题进行抽象，但始终没有太好思路。这个时候时间也不多了，想想大数据有8min时限，下下来碰碰运气好了。结果SPFA没有任何优化，1分钟不到就跑出结果了，遂提交之。

12点封榜的时候，好像是排50名左右吧。。。Arios比我快2分钟，能离伟神这么近我也很满足了。睡过午觉过来一看，发现自己AK了。。。。。。最后排名29。其实题目不难的，但貌似很多ACM神牛都没有来玩，不知为何了。。。

最后的board。

事后马上收到了Google的邮件，恭喜通过笔试云云。

不禁也在问自己，这个时候如果要选择，是继续读完研究生，还是去Google工作？

心里面作出回答只用了10秒。而且非常清楚，自己这一决定，怎样也不后悔。

祝自己好运吧。

books and reading

发表回复

最近也是在啃松本的书，越读越喜欢。

作为Ruby语言的作者，其书中对程序语言的看法非常独到。比如拿“面向对象”来说，我在之前看的书里面大多只是讲：类怎么写，继承怎么用，虚函数的作用是什么，诸如此类等等等玲琅满目堆砌了一大堆细节。很少涉及到非常关键的一点：为什么要用面向对象？当然某些书里会含糊其辞地写到，用“对象”的思想对客观事物进行模拟，会让写出来的程序更加合理。“但真的是这样吗？”这是我知道有面向对象以来一直存有的疑问。直到在本书中，读到松本写到的“从实用主义的观点来看，面向对象的精髓就在于对OCP的实践。至于把对象看做物体理解起来比较容易，能够建立现实世界的模型等，这些都只不过是些锦上添花的东西。”（P111)，对我来说，这句话犹如醍醐灌顶，很多问题霎时间就明白了。（这里的OCP指的是open-closed principle，指程序对功能扩展要是开放(open)的，而修改则要对外呈现封闭(closed)）

这本书里，作者还写到“但是不管过去怎样，现在对面向对象最好的理解是，面向对象编程是结构化编程的延伸。”(P32)。作者认为，我们写程序时，最初所用的结构化编程是非常自然的。但是当时仅能够做到“程序的结构化”，而无法做到“数据的结构化”，也即数据无法随着程序一起“流动”，造成了处理上的困难。而面向对象的出现，使得数据可以与程序捆绑在一起，由此便实现了程序完全意义上的“结构化”。

我无法判断这种思想是对是错，但若是反过来从头看程序语言的演变，由以上思想作为出发点的话，很多事情都变得容易理解了。甚至让我怀疑“面向对象是为了根据现实进行抽象建模而出现的编程思想”这种思路反而才是牵强附会。

另外，这本书里还讨论了其他很有意思的设计，包括“Duck Type”，也即动态类型，还有对多重继承的处理（对比了RUBY、C++、JAVA、SMALLTALK、JAVASCRIPT和LISP等多种语言解决多重继承问题背后的思想，以及优劣所在）等等。实在是让我眼界大开……

当然，我还不敢肯定自己到底理解了作者想表达意思的程度，而无法判断作者所言是否有理，但这种思想碰撞的过程，太让我享受了

惯例也贴一份有趣的程序，用Ruby实现微秒级别的时钟，以前用C时只能调用到毫秒，还以为系统不支持呢。另外本程序也是为了表现Observer模式的思想。

[POJ 2065] & [POJ 1166]

发表回复

SETI

The Clocks

两题都是高斯消元法。（也都1A了^^）

两题题面都很有意思，分别描述了确定有唯一解的模运算线性方程组，唯一解是因为前者是范德蒙行列式，后者则是给定了满秩系数矩阵。

两题都没有太大难度的，代码也相近。

2065的：

1166的：

好久没来了……这几天都在看书+帮人折腾VPS。Linode用久了就以为主机商都该是这样的，现在算认识到很多产品还是良萎不齐的（而且还死贵……）

books and reading

发表回复

最近在啃Effective C++。

虽然一直以来都很喜欢写C++（其实是不会其他语言），也确实体会到C++语言的各种好处（清晰的变量类型，灵活的内存处理，强大的STL等等等等），但发现确实对面向对象的C++没有任何好感。

主要是书里面讲到的太多解决问题的“巧妙”方法，在我看来却是太投机取巧了。换言之，我认为如果非要这样才能写出高效的代码，那对程序员的要求实在是太苛刻了，况且这里还没有涉及实际项目的要求以及和他人的协作。当然，这本书还是让我明白到了C++设计时的一些思想，这是仅仅粗读C++ primer所无法领会的。

自己的一点粗浅体会，也写在这里吧：总体感觉就是，C++最初被设计出来时，是在考虑执行效率的前提下为程序员尽可能地提供了自由的功能实现方案。然而随着时间的推移，越来越多的技术被发明/发现出来，而C++也在不断进行扩充。直到今天在我学习的时候，发现她身上存在着太多的历史包袱，从一开始的继承C的语法以及面向过程，到后面的面向对象和模板泛型编程，虽然包罗万有，却又让人无所适从。做项目不比做题目，当一个庞大系统要实现出来时，往往代码的规范一致性和可维护性要比执行效率更重要，这也导致了很多高效的写法事实上无法应用于工程。而且，作为一门古老的语言，它提供的很多功能其实是累赘的（例如在本书P151中作者明确表示“protect继承的意义至今仍然困惑我”），并不能真正反映软件设计的需求。

相比起来，更为“现代”的语言，比如pyhton，在这一点上做得要好很多。其开发者相信“应当只用一种——而且是最好的一种——明确的方式去做一件事。”（“There should be one – and preferably only one – obvious way to do it.”），大概也是其得到广泛普及的重要原因。但个人认为，就语言学习来说，python这种“单调”的语法也对暂时不需要写项目的我没有太大吸引力。接下来想看的是Ruby作者写的松本行弘的程序世界。

还是贴几段书中有趣的小例程，第一次知道C++还可以这么写：

模板编程（这里最多只能500，不知道为何）：

用boost的：

以及：

编译这个还要专门写makefile（用的是os x下brew安装的boost库）：

但貌似用clang编译时还是报找不到库…不管了反正不用xcode

[POJ 3020]

发表回复

Antenna Placement

二分图匹配。

其实是很久以前做的题目了。今天被Usozki问了下这题怎么做，看了他的代码，感觉值得改进的地方不少……便自己着手重做了下这题，希望能讲清边表的写法。由于之前hackerhank出过一题很刁钻的匈牙利，觉得已经把这个算法弄得很透彻了（包括递归改非递归、每轮匈牙利时局部链表指针改全局、每次不重新memste标记数组等等），但这次重写这题还是用了很久。

这里用了一个题目的特点（可以染色成国际象棋棋盘那样的二分图），使得每个匹配的共算了两次；又或者其实可以每次仅从一种颜色的点出发，这样就只算一次匹配。

这是今天写的代码：

这里建图是先编号，再检查上方和左方是否存在点，然后加边的。代码里函数功能应该都区分得很明显了。这样写出来的边表，是做很多图论题时必须使用的数据结构（甚至其他类型题目里也经常用到）。无论是时间、空间，还是代码实现难度方面都是很好的。

另外也贴下以前写的，当时不会用边表，但是代码还算是比较齐整了：

[POJ 1487]

发表回复

Single-Player Games

还是高斯消元法。

这题的特点是输入是用树来表示的，并且需要做类似编译原理那样的词法和语法分析。处理字符的时候小心一点，问题不会太大（但还是被负数的’-‘阴到了。。）。用递归来表示每个括号的匹配情况，符号移到等式右端（取负），数值直接累加，递归返回时每个值除去子树规模再累加到父节点数组上即可。由于输入规模不大，除了字符串处理也没有其他麻烦了。

解线性方程组的时候，注意每个方程已经指定了主元了，如果系数为0即对应变量无解，所有依赖于该变量的其他变量也无解。但其他剩余有解的变量还是要解出来的。这题比之前那题取模的要好处理，方程比较整齐，而且可以直接用浮点数。

另外这题也是我在POJ上有记录的第200题，貌似里面夹杂的水题不少。。。但还是值得纪念：

296_0

[POJ 2947]

发表回复

Widget Factory

高斯消元法。

其实就是线性代数里解线性方程组，但这题还要求等式两边mod7。

解向量中xi的取值范围是[3,9]，共有m个方程，判断是否有解，如果有解，要判断是否有唯一解。

这题一开始走了弯路，想象以前解普通线性方程组那样用浮点数依次选列主元后化成上三角来求解。但发现在这题mod7条件下，行不通。

后来发现可以用一个很差的时间复杂度完全使用整数进行处理。。。由于数据规模不大，发现这样是可行的。每次消元处理后都也要注意各种取模，不然很易RE。

反正最后就是各种暴力。。。就过了。。。