首页 > 代码库 > 50题的一点感想

50题的一点感想

不知不觉在vjudge上也打了50来道题了。1月底注册的账号,已经三个月了。实际上是从3月份听说学校要搞校队(一个一般的文科为主的学校,作为弱势专业的学院第一年开始搞,泪奔)才开始刷,之前也就打了个位数的题。。。

作为一个刚入坑的新手,有些题虽然简单,在很多人眼里都是非常水的水题,可是我要从有思路到敲成代码再到AC也要花上很大的力气。

有时候看到Accepted,很开心,回头却发现自己的思维很乱,写出来的代码也很乱,有的时候为了解决边界问题,写的可谓东拼西凑,让我都有过了是不正常的感觉了。

还有时候时间压线过的题,看看题都是好几年前的题,考虑到现在硬件更新的进度(不知道这些服务器是不是更新的比较快),这些低效的算法或者常数大的,还是存在很多欠缺的。

记得有一题是2014 北京的题,很水,我用STL东拼西凑写出来了。慢的令人咂舌。700+ms。我想想,map nlgn,排序nlgn,不应该啊,别人也是nlgn的,也用了STL,怎么慢了那么多?

突然想起来map是RB Tree,自带排序,然后我对一个有序的序列调用一次sort,然而STL的sort总体上是快排实现,快排最怕有序的,结果就直接退化到n^2了。于是删了这句sort,快了好像200+ms,虽然常数还是很大的,但是跟别人用的STL也差不多了。毕竟200+ms也是不得了的数字了。

还有一个很要命的就是,我太依赖VS2015的IDE了,尤其是装了visual assist插件,各种自动补全,语法错误提示,当时感觉真尼玛爽,然后比赛都用的别的IDE,就试着换了个devc++,写完能出来五六个编译错误,调试起来更没2015的智能舒心(尤其针对数组越界、指针非法访问),直接火葬场了。

虽然说现在的水平还是不尽人意,但是这一个月下来也是有很多收获的。

单从解题来说吧,虽然现在属于各种不会的状态,但是起码拿到题目知道首先要去分析,而不是傻乎乎的直接做;能把描述复杂的题目拆成一个个小问题;知道看数据范围,大概预估一下复杂度;数据结构上面,二叉树动手写了好几次(指针的、数组的、动态内存分配的、静态的),自己推出来用前中序遍历递归求原树;能够大概感受一下图的BFS和DFS。。。对递归的理解又深了一点。除了解题,心理素质也是提高不少了。曾经有一晚上带第二天早上都无限WA和RE的,当时都开始怀疑人生了,后来下了UVA的测试数据,才发现一个万万没想到能错的地方居然手贱写错了。要是以前的心态,我估计直接就copy别人的代码,心里想着,起码我也WA了二十来次,至少有个心理安慰吧。实际上那样自欺欺人真的没意思,这样自己找到错误,感觉还是不一样的。我也发现欣赏别人的代码,也是一种乐趣。同样的算法,具体到实现方式,可能千差万别;看懂别人的程序,确实也是对自己水平的很大的提高(尤其是没有注释的情况)有时候也在想,ACM这种算法题并不是算法的全部,很多的算法并不能用简单的题目就能在赛场上重现;更多的特定领域的算法,可能需要更高深的数学知识,群里的一哥们研究生做模式识别在那恶补高数矩阵论,之前还看过要用什么复变函数、数值分析之类的数学工具的东西。。。so,数学基础课还是不能落下,虽然更多的时候可能不会用得到,但是也不能把自己限死在只会做ACM题上啊,万一哪天就派上用场了呢。。。再说CS类其他的东西,比如操作系统,计算机网络之类,也是不能太掉以轻心的,毕竟,算法也不是计算机的全部。

Anyway,这些题也能训练扎实的编程基本功(代码+基础数据结构算法),还有思维的灵活性,从这点上来看还是值得的,起码跟成天无所事事打游戏比起来(当然我其实只会一个游戏,汗)。其实现在感觉,AC一个题远比打游戏赢了谁谁谁开心多了。至于能不能拿到奖,身外之物了,有了更好,没有拉到。。。

2017.4.23

 

50题的一点感想