小古比鱼

原文发布日期：2016-12-17

       今天是小古比鱼在洛谷连续打卡的第99天。今年9月17日，即中秋节小长假的最后一天，小古比鱼重回洛谷网站（详见第172篇日志），到今天为止，小古比鱼重回洛谷已经整整三个月了。记得自从去年秋天通过了计算机二级有关C语言的考试之后，小古比鱼便很少去做洛谷网站的编程题目了，还于去年10月18日后正式退出了洛谷。自那之后，虽然小古比鱼偶尔还会到洛谷打卡签到，但却再也没有提交过任何程序，平时也极少再去编程，直到今年9月17日当天，小古比鱼一时心血来潮，在洛谷网站提交了2个新程序，由此便开始了自己新一轮的编程之旅。

       这次重新回归编程领域，小古比鱼的重点放在了C语言的编程上，直接原因就是因为洛谷网站支持C语言。三个月的时间过去了，小古比鱼在洛谷网站也取得了很大的成就，请看：

【注】上图中“提交”上面的数字代表累计提交程序的次数，而“通过”上面的数字则代表累计通过的题目数。

       大家可以看到，截止到今天为止，小古比鱼在洛谷累计提交程序202次，目前已通过了洛谷网站的整整50道题目；贡献值为43，活跃度为672，积分为1137（当前等级为“大犇”，并且即将升级为“神牛”）；现已获得了橙色用户名（简称橙名，动态等级为“刷题健将”）。大家可能会想：小古比鱼在洛谷累计提交程序202次，但通过的题目数仅有50道，是不是意味着小古比鱼的通过率仅有不到25%呢？显然不是，首先，由于二者的单位不统一，因此计算比值实无多大意义；其次，对于洛谷的绝大多数题目，小古比鱼都有不止一次的提交记录，即使对于已经通过的题目，小古比鱼也很可能会对提交过的程序做进一步的修改，或是编写一个新的程序来实现题目中的要求，之后再度提交。因此，小古比鱼认为，提交次数的增多并不意味着通过率的降低。为了使大家更好地了解洛谷网站以及上述各项数据背后的含义，下面小古比鱼将对洛谷网站的基本情况及其各项机制向大家做一个简单的介绍。

       洛谷网站被誉为“富有亲和力的信息学在线学习网站”，创建于2013年6月15日，现已发展成为具有数万用户（用户的代号以字母U开头）和260余个团队（团队的代号以TEAM开头）的在线评测系统，深受广大编程爱好者的喜爱，同时也是尚处在学习阶段的朋友们的最佳选择。洛谷3.0版于2016年4月2日正式上线，增加了不少新功能，也完善了之前版本中的部分漏洞。小古比鱼在第172篇日志中曾提到过，洛谷常会举办一些比赛（比赛的编号以CON开头），有官方性质的比赛，也有团队和个人举行的比赛，不过现在看来，小古比鱼对此并不感兴趣，因而现阶段还是以做试炼场中的题目为主，偶尔也会随机选题来进行编程。

       下面我们来说说洛谷的题库和评测系统。就题库而言，洛谷有一个公共题库（题目的序号以字母P开头。大家在小古比鱼的博客相册《C程序》中，可以看到部分截图的描述里有类似“【P1001】”的字样，这表明该程序是小古比鱼解答洛谷网站中的题目时编写的程序，方括号里的内容即为题号），而每个用户还可创建个人题库（题目的序号以字母T开头。到目前为止，小古比鱼还从未上传过任何题目，同时也从未做过其他用户个人题库中的题目），把自己认为比较好的编程题目上传到洛谷与大家分享，同时还可以申请将其加入公共题库。洛谷的公共题库现包含有2400余道难度不等的编程题目！由此可见，到目前为止，小古比鱼获得通过的题目仅占公共题库题目总数的2%！前途任重而道远。除少数题目暂无评定外，公共题库中的绝大多数题目都有一套评测系统，可以对我们提交的程序进行评测，并将评测结果（序号以字母R开头）反馈给我们。那么，这个评测系统究竟是如何进行评测的呢？小古比鱼在刚刚注册洛谷的那一段时间内，也曾思考过这个问题，当时总认为一定是基于非常复杂的原理才设计出来的，其实不然，评测的方法非常之简单——洛谷的每道题目都由该题的提供者提供一系列的输入及其对应的输出结果，我们将其称为“测试点”，通俗地说也就是本题在几个不同的输入情况下相对应的正确答案，评测时，就是看我们所提交的程序在相应的输入下，其运行结果是否与这些正确答案相吻合，如果全部吻合，我们就可以得到100分，同时意味着通过了该题；若是仅有半数的运行结果与答案相吻合，那么得分便是50分。需要指出的是，对于任何一道题目，只有在所有的测试点全都通过，即拿到100分的情况下，该题才算通过（即Accepted），其余情况下均被视为不通过（即Unaccepted）。请看如下评测结果：

A

B

C

D

       在图A所示的题目中，提供者为我们提供了4个测试点，但评测结果显示，只有1个测试点通过了，即注有AC（即Accepted）的那个测试点，而其余的测试点均未通过，因而该题只能拿到25分。其中，注有WA（即Wrong Answer）的那个测试点表示答案错误，而注有TLE（即Time Limit Exceeded）的两个测试点则表示超出了运行时间限制（洛谷一般限制每个测试点的运行时间不得超过1秒）。同理，图B中的20个测试点有10个通过，故得分为50分；图C中的10个测试点全部通过，因而得分为100分，即通过了该题；图D中的5个测试点均注有RE（即Runtime Error），这表示程序在运行时发生了错误（如返回值非0等），因而得分为0。当然，如果我们所提交的程序在编译的过程中便出现了问题（此时会提示Compile Error），显然就更谈不上测试点是否能通过了，这时的得分也必定是0分，我们在第172篇日志中也曾粗浅地讨论过这个问题。这就是洛谷的评测系统，是不是很简单？

       大家或许会问：如果洛谷的题目太难，想不到合适的解题方法该怎么办？不必担心，洛谷的每一道题都有一个叫做“题解”的模块，里面包含有很多用户提供的各类题解，如果我们实在想不出好方法来解题，就可以参考这些题解。但是，小古比鱼认为，参考题解不仅会降低自己的思维能力，使我们对其产生依赖，同时也大大削减了做题本身所具有的趣味性。因而，小古比鱼总是在通过了某道题目之后，再去参考该题的题解，这样既可以了解其他用户的解题思路，吸取他人的优点，同时也能使自己的编程水平得以提升。除此之外，洛谷还允许用户下载题目中未通过的测试点的数据，以便于用户根据其测试点的数据进一步调试并完善自己的程序，从而顺利通过该题。当然，下载的次数是有限制的，这点我们在下文中再做介绍。

       与网易博客和爱拍网站类似，洛谷同样也有积分和等级的设置，而积分则与活跃度、贡献值以及通过的题目数这三者相关。具体而言，有如下公式：

积分=活跃度+(贡献值+通过题目数)×5

       从公式中不难得知，我们每通过一道题目，积分便会增加5分。那么，活跃度和贡献值又是怎么回事呢？事实上，日常的打卡或是对题目进行评价都会使活跃度得以提高，而贡献值则需要通过撰写题解或是上传新的题目到公共题库来获得，显然，贡献值的获取难度较大，因为无论是撰写题解还是上传题目，都需要在通过洛谷管理员审核的前提下，才能拿到相应的贡献值。到目前为止，小古比鱼的活跃度主要来源于打卡，而贡献值则全都是通过撰写题解获得的（因为小古比鱼到目前为止还没有上传过任何题目）。值得说明的是，洛谷只允许每个用户对任意一道题目贡献1条题解，倘若多次提交某道题目的题解，即使审核通过，也会覆盖（刷新）掉之前通过的那条题解，同时贡献值也不会再增加。这从另一方面也说明，在通过的50道题目中，小古比鱼已经撰写并通过了其中43道题目的题解！由于现在仍有3道题目的题解处在审核过程当中，因此，如果它们也全都通过的话，就意味着小古比鱼所撰写的题解的通过率达到了90%以上！

       下面是洛谷网站积分和等级的对应关系：

   积分              等级

0~10               蒟蒻

11~30           小小牛

31~60           小小犇

61~100           小牛

101~180         小犇

181~280         中牛

281~460         中犇

461~740         大牛

741~1200       大犇

1201~1980     神牛

>1980             神犇

       大家最感兴趣和最关心的，要数洛谷的动态等级了，它与用户名的颜色相关，却与我们刚刚所介绍的那个等级不同。动态等级是根据用户在近一段时间内的活跃程度（如打卡、提交程序或是撰写题解等），综合各项指标来进行评定的，因其随时会有变动而得名。不幸的是，洛谷对于动态等级的评定算法并不公开，同时也不允许用户在讨论中过多地谈及有关用户名颜色的问题。下面是洛谷动态等级与用户名颜色的对应关系：

     动态等级              用户名颜色

0：见习用户                  灰名

1：普通用户                  蓝名

2：算法爱好者               绿名

3：刷题健将                  橙名

4：虐题狂魔                  红名

       那么，动态等级又有什么用呢？事实上，当用户的动态等级较高时，其所享有的权利也会随之增多，我们上面所提到的打卡以及评测点的下载便是与此直接相关的——用户在不同的动态等级下，打卡所获得的积分也不同，而24小时内可以下载的评测点数据的次数也不同。举例说明：如果某用户为蓝名，那么他打卡一次只能获得1活跃度，24小时内也只能下载1次测试点的数据；如果另一个用户是红名，那么他打卡一次就可以获得4活跃度，24小时内也可以下载4次测试点的数据。洛谷还指出：如果用户长时间不使用洛谷或者有违规行为，就可能会降级；但除非用户有严重的违规行为，否则用户只要达到蓝名，就不会再掉回到灰名。

       如果没有记错的话，小古比鱼是在连续打卡第91天的时候获得了橙名。其实，只要小古比鱼能保持住“刷题健将”这一动态等级，并且坚持打卡，那么每天便可获得3活跃度，即3分的积分；如果每周通过2道题目，并且为这2道题目撰写的题解也均能通过审核的话，那么小古比鱼每周便可拿到3×7+5×2+5×2=41分的积分！照这种速度，小古比鱼在半个月之后便可跃升为“神牛”等级，而到达洛谷的最高等级“神犇”，也只需要五个月左右的时间！当然，这些都是以小古比鱼不离开洛谷，并且坚持每天打卡、每周刷题和撰写题解作为前提的。

       下面小古比鱼再为大家介绍一下洛谷的试炼场。目前，洛谷试炼场总共有六个大关，其中除了第五大关“NOI神殿”现仍处于建设当中，尚未开放以外，其他的每个大关都有不少小关，每个小关就是一个关卡，其中又包括一定数量的题目。上文中我们提到，对于洛谷题库中的任何一道题目，只有当其所有的测试点全都通过时，该题才算通过；但是，对于洛谷试炼场中的绝大多数关卡，只要我们通过了其中的任意3道题目，便可以点击该关卡下方的“关卡完成了！”按钮（当然也可以不点这个按钮），从而完成该关卡。部分关卡有先决条件，需要我们先完成某些特定关卡后才可解锁。另外，如果我们没有能力完成某一关卡，还可选择跳过该关卡，但最多只能跳过3个关卡。

【部分内容因无法过审，待补充】

下面是小古比鱼完成各关卡的情况记录：

小古比鱼完成洛谷试炼场中各关卡的情况记录

【注】本记录截止到2016-12-17。 

  1、2015-05-23：完成关卡1-1，该关卡共3题，现已通过3题。

  2、2015-06-07：完成关卡1-2，该关卡共3题，现已通过3题。

  3、2015-06-28：完成关卡1-3，该关卡共6题，现已通过6题。

  4、2016-09-16：完成关卡1-4，该关卡共4题，现已通过4题。

  5、2016-09-16：完成关卡1-5，该关卡共6题，现已通过6题。

  6、2016-10-21：完成关卡1-6，该关卡共4题，现已通过3题。

  7、2016-11-11：完成关卡6-1，该关卡共4题，现已通过4题。

  8、2016-11-12：完成关卡2-1，该关卡共6题，现已通过5题。

  9、2016-11-26：完成关卡1-7，该关卡共4题，现已通过4题。

10、2016-12-14：完成关卡2-2，该关卡共5题，现已通过5题。

……

       关于洛谷网站，小古比鱼就给大家介绍到这里。下面小古比鱼要和大家分享一些编程的技巧。看过小古比鱼第172篇日志的朋友们一定都知道，小古比鱼编写的程序总是在某些方面显得与众不同，虽然其中的一些写法甚至违反了编程的常规，即我们平时所说的“耍小聪明”，但小古比鱼本人却特别偏爱在这些细节之处做文章。记得在这次重回洛谷的半个月前，小古比鱼曾编写了一个名为“幻幻球单次射击主体得分计算”的程序。现在想来，或许就是这个程序燃起了小古比鱼新一轮编程的热情！然而，由于当时长时间未编程的缘故，小古比鱼对于编程过程中各类技巧的使用，甚至连最基本的运算符和语句都有所淡忘，因而，小古比鱼只能循规蹈矩地进行编程，而“幻幻球单次射击主体得分计算”这个程序虽然看上去比较长，但却非常易于理解。如今，经过三个月的不断练习，小古比鱼不但将已然遗忘的知识重新拾起，还找回了从前编程的那份目无全牛的感觉，因此，现在小古比鱼所编的程序运用到的技巧非常之多，只是在可读性方面，反倒不如初回洛谷的那段时间所编出的程序要强！下图是小古比鱼的程序“幻幻球单次射击主体得分计算”。

       大家或许会问，小古比鱼现在编程时，到底遵循的是什么样的原则呢？其实，小古比鱼所遵循的原则也很简单，那就是：在基本满足C语言编程规范的前提下，最大限度地使程序看上去显得简短、精炼，并且要体现出独特之处。其主要有以下几点：

1、尽可能少地使用大括号；

2、尽可能少地使用if、else、break、continue语句；

3、尽可能少地使用变量；

4、尽量优化算法；

5、用好宏定义。

       以上几点说起来容易，但做起来却并不简单，需要对C语言熟练掌握后方能应用自如。小古比鱼逐一进行解释和举例：

1、尽可能少地使用大括号。

       严格来讲，这点违反了C语言的编程规范，但从某种意义上说，它又可以使小古比鱼的程序变得简短许多。常来阅读小古比鱼程序的朋友们不难发现，在小古比鱼所有的程序中，几乎都有这一点的体现。事实上，我们只要将语句进行压缩，使用复合语句，或是采用调整语句顺序的方式，使得for、while、if等语句模块中仅含有一条语句，这样便可省略掉本应有的一对大括号。如下程序“给定区间内的回文质数(2)”是一个最为典型的例子，该程序中，小古比鱼省略掉的大括号多达15对。想象一下，如果把这些括号全都加上的话，虽然符合了编程规范，但程序将会加长30行。

2、尽可能少地使用if、else、break、continue语句。

       小古比鱼认为，对于程序中较为简单的if语句和else语句，可以通过使用条件运算符“? :”，获是采用直接将关系表达式嵌入到赋值语句中的方式来代替。举一个最简单的例子，对于如下的条件语句块：

if(a>0)

{

    b=b+1;

}

       小古比鱼会将其改为：

if(a>0)

    b++;

       进而改为：

b=a>0?b+1:b;

       最后改为：

b+=a>0;

       就是这么简单！至于break语句和continue语句，若是在循环语句块中，则完全可以通过修改循环条件的方式来避免；若是在switch语句块中，小古比鱼往往不在最后一条case语句或是default语句之后再添加break语句。如下的几个程序“斐波那契分数列的求和”“纸牌的平均分配”“小鱼是否有危险”和“字符串的展开”中，小古比鱼多次通过上述方法减少了if、else、break、continue语句的使用：

（1张图片未显示）

（1张图片未显示）

3、尽可能少地使用变量。

       要想做到这一点，小古比鱼的方法有两个：其一是不声明不必要的变量，其二是重复利用不再使用的变量。例如，在如下程序“求两数之和”和“哥德巴赫猜想的验证（升级版）”中，小古比鱼通过在函数中嵌入表达式的方法，减少了不必要的变量的声明；而在上文中的程序“纸牌的平均分配”，以及下面的程序“多多采花生”和“字母柱状统计图”中，小古比鱼分别对变量i、变量I、J和变量c进行了重复利用。还有上下文中的不少程序，小古比鱼采用“while(n--)”这样的写法，避免了多余的循环变量的声明。

（1张图片未显示）

4、尽量优化算法。

       这一点的意义想必大家都有所体会。对于同种功能，实现的方法可能有很多种，虽然它们殊途同归，但其间的差异往往不可同日而语。请看如下三个鲜明的对比：上文中的程序“给定区间内的回文质数(2)”和下面的程序“给定区间内的回文质数”，虽然前者的代码较长，但其运行的时间比后者要短得多；程序“火车上的人数”与“火车上的人数(2)”，后者的代码比前者要简洁许多，运行的时间也有所减少；程序“由1—9组成的3个三位数”“由1—9组成的3个三位数(2)”和“由1—9组成的3个三位数（升级版）”，三个程序的功能类似（前两个程序的功能完全相同），但算法完全不同，实现的功能以“由1—9组成的3个三位数（升级版）”最为高级，但代码却最为简单。不过说老实话，这个程序中的算法小古比鱼是借鉴了题解的。

5、用好宏定义。

       这点小古比鱼不作过多解释，只给大家展示一个最为典型的例子——在如下程序“烤鸡配料的配比”中，小古比鱼通过宏定义的使用使程序变得非常简洁。倘若不使用宏定义，并且在所有的for语句中添上大括号，那么程序可能将会加长近60行！

       关于这些技巧，小古比鱼在这三个月以来想了很多，诸如直接在主函数的return语句中使用printf()函数输出结果啦，如何采取各种方法避免使用类似“for(a=0;a<n;a++)”这样传统的写法啦，等等。虽然这些看似奇怪的技巧和做法在大家看来或许难以理解，但小古比鱼却将其作为编程的一大乐趣，平时也往往会在编程过程中不自觉地加以运用。至于这样做究竟是利大于弊，还是弊大于利，那就由大家来评判吧！下面小古比鱼给大家展示两个近期所编的程序“13日是星期几(2)”和“最大公约数与最小公倍数(2)”，这也是小古比鱼认为自己对于上述技巧运用最多的两个程序：

（1张图片未显示）

       不难体会，上面的第一个程序还勉强算作合格，但第二个程序未免太过精简，已然不满足小古比鱼所说的“基本满足C语言编程规范”的前提！因此，类似这样的程序小古比鱼在今后也不会编得太多，但对于上面的第一个程序，小古比鱼认为还是很有价值的，而且似乎还能进一步精简……不管怎样，虽然程序本身的代码变得精炼了，但小古比鱼在写程序的注释方面却丝毫没有偷工减料；恰恰相反，现在小古比鱼所编的几乎每一个程序都有很详细的注释，尤其是对于洛谷网站的题目，小古比鱼还要力求在注释中完全反映出题目本身的背景和要求，以便让那些没有看过题目的读者也能够很清楚地了解到程序所实现的功能。大家可能已经发现，当在程序代码的后面写注释无法把题目描述清楚的时候，小古比鱼会在程序结束后空一行，写一条以“说明”为开头的注释，进一步描述遗漏的题目背景和要求；更有的时候，小古比鱼还会写一条以“解析”为开头的注释，说明该程序的解题思路，这些在上下文所展示的程序中都有所体现。可这么一来，详尽的注释未免与过于精简的代码发生了冲突，颇有喧宾夺主的感觉！当然，当二者发生冲突时，其中的一方必须做出让步，即要么注释写得不要太详尽，要么代码写得不要太精简！就是这样！以下三个程序“断链取珠”“教室里的通道”和“补贴与税收”中的注释都非常详细，其中程序“补贴与税收”编写于6天前，是小古比鱼今年重回洛谷后编写的最为复杂的一个程序——该程序前前后后共花费了小古比鱼十几个小时的时间，现虽然已通过评测，但其本身存在的漏洞仍不可否认。

（1张图片未显示）

【部分内容因无法过审，待补充】

       小古比鱼的编程经历就给大家介绍到这里。在接下来的日子里，小古比鱼还会继续在洛谷网站做题，并遵守洛谷答题上限原则（详见第172篇日志），认真对待其中的每一道题目，尽可能想出两种甚至更多的方法来实现同一道题目中的要求，尤其是对于看似非常简单的题目，更要认真把每一条语句都编好，同时也要体现出小古比鱼特有的编程风格。说到简单题，小古比鱼计划将自己下一步的重点放在洛谷公共题库中较为简单的题目上，即多做一些简单的题目，在做题的过程中继续积累经验，不断总结技巧，这样循序渐进，难题也终归会变成简单题！同时，小古比鱼也建议有兴趣的朋友可以考虑来注册洛谷，和小古比鱼一起挑战试炼场中的习题。等到小古比鱼在洛谷的用户等级达到最高级“神犇”，并且通过的题目达到100道题的时候，或许也就是小古比鱼发布下一篇关于编程的日志的时候，届时，小古比鱼的编程水平一定又会比现在有大幅度的提高。在日志的最后，小古比鱼为大家推荐自己到目前为止发布过的唯一的一期与编程有关的爱拍视频——水仙花数的枚举，拍摄于去年暑假。等到明年寒暑假，小古比鱼可能还会给大家发布与编程有关的视频，敬请大家期待吧！