CSP高分说 | 中南大学许宸哲：CSP考场高效得分策略分享

细想起来，第一次接触到算法竞赛课程还是小学四五年级，当时还完全不了解算法竞赛，一直以为自己只是在上一门午休时间开设的“编程课”，使用的还是符合入门组水平的QuickBasic语言。也是在那时候，我就懵懵懂懂地踏上了算法竞赛的路，参加了第一次正式的、由CCF举办的面向小学生的算法竞赛（全国青少年信息学（计算机）奥林匹克联赛初级组），印象里在市里还取得了不错的成绩。也就是在这时，我开始意识到，电脑在这个新时代（2015年）能够帮助人们实实在在地快速解决问题，而使用电脑解决问题，就必须学习算法有关的知识。似乎从那个时候开始，我就已经在为未来的道路选择埋下了伏笔，做出了铺垫。

进入初中之后的第一节微机课，我就迫不及待地向老师询问算法竞赛有关事宜。由于组别的更换，我也从基础的QuickBasic语言过渡到了当时普及组比较流行的Pascal语言。当时认为，算法一定是复杂的，都需要死记硬背才能够像课文一样“默写”出来。直到当时的教练教授了我求最大公因数用的“辗转相除法”，我被震惊了：原来真正有用的算法也可以有一种简洁而又优雅的美。也因如此，我越来越对算法，这个实用而又优美的事物起了兴趣，这也增加了我之后学习算法竞赛的动力。

但碍于我在初中时的基础知识实在过于浅薄，我在初中并没有取得多亮眼的成绩。而到了高中，在翻开询问过高中竞赛教练后借到的参考书（信息学奥赛一本通）的算法部分后，我才可以说是真正开始学习算法：Dijkstra、Kruskal…一个个算法在学习前看似天方夜谭，学习后却发现看似复杂的流程每一步都有它的合理之处，学习起来并不算困难。为了学习算法，几乎整个高中我的午休时间都在机房度过，而这份努力终究有了回报：在高三那一年我终于获得了CCF主办的全国青少年信息学（计算机）奥林匹克联赛提高组省级一等奖。虽然高三才拿到省级一等奖注定与省队、NOI、国集等等梦想中的事物无缘，但对于资质平平的我来说也是一种莫大的幸运。

许宸哲NOIP2020获奖证书

就这样带着未熄灭的热情来到了大学，我依旧投身于各种算法竞赛，但由于同时需要在转专业和考研间发力，成绩也不是很理想。感谢CCF，让我有了参加CSP和CCSP的机会，让我能够继续在算法竞赛的舞台上继续我的梦想。

专业级CSP的试题虽然有一定难度，但是本身难度阶梯明显，并且每题之间的部分分划分也可以有效区分不同水平的选手。这就意味着，即使一道题的正解没有办法第一时间想出来，也依然可以通过部分分的额外约束做出一些部分分数。所以，只要在考场上把自己会的部分全都写上代码并且全部做完，分数就还是比较可观的。

那么如何在CSP赛场上获得尽量高的分数呢？对于此，我有几点备考建议：

第一，CSP每道题目之间的难度跨度较大。一般来说，第一题和第二题相对后面三道题来说较为简单。所以说，对于目标分数在200+的考生来说，在完成前两题之前专心攻克前两题是较好的选择。

CSP认证的第一题一般来说是一个比较简单的模拟题目，对于有语言基础的考生来说，根据题目的意思写一个模拟原题进程的程序几乎就可以通过。而第二题相对第一题会稍微难一些，但是仔细研读题意的话，一般来说能观察到一个显著减少复杂度的方法，而即使没有观察到，也可以先使用枚举等“暴力”的办法拿取部分分，之后想到了再回来更改，毕竟CSP是多次提交取最高分的实时显示成绩的考试模式。

第二，CSP乃至程序设计竞赛的题目大多由一些算法知识点结合而组成，如果没有时间系统学习这些知识点的考生可能会难以应对。我的建议是，在备考时可以选取CCF提供的往年CSP的真题进行训练，如果还是难以做出来的话，可以搜索其他人的题解学习参考思路，并且活用于下一次。

第三，CSP认证的第三、第四和第五题可能比较难在短时间内想出可以获得100分的正解，但是一般来说都会提供可观的部分分，很多部分分甚至类似于第二题的难度。这个时候，可以不用立马朝着正解的方向想，而是把部分分当作一道完整的题目写完，再逐步优化，这样可以在稳扎稳打的情况下获得可观的分数。

第40次CSP认证在数据上来看是较难的一届。但是，只要掌握好答题的方法，想获得一个相对较好的成绩还是并不难的。在考试时，我用了约一半的时间通过了前三题，并且剩下的时间用于解决第四题和第五题的部分分，成效也比较可观，第四题获得了50分，第五题35分。

许宸哲CSP40成绩单

第一题看似是一个数学题，实际上只需要根据给出的公式进行模拟计算集合的异或和，再验证是否正确即可。需要注意的是并不是单纯的判断两个集合的异或和是否相等，而是判断“用这个方法进行判断的正确性”，即与真实结果是否相同。

第二题初看也是眼花缭乱，实际上是一个在[0,511]范围内的数通过一系列O(m)的变换可以得到另一个该范围内的整数，需要根据变换后的数输出变换前的数。看似不方便倒推，而且每次询问都枚举的话，复杂度无法接受，实际上由于变换前的值和变换后的值一一对应，所以可以预处理每个变换后的值对应的变换前的值，这样就可以接受了。

第三题是一个代码量比较大的模拟题，给定了加密方法，要求还原一个加密的矩阵。这题较难调试，需要注意细节，调试不成功的话可以自己手写一些人工能看出来的测试样例进行测试。另外，在写程序时某些显然的优化要注意优化，由于评测机性能较好，复杂度稍差的程序即使不能通过整题，也可以通过更多测试点。

第四题是数学题，考察满足一些条件的七元组的价值的和。实际上，通过对条件给定的等式进行整理，我们可以知道B=F，这就变成了一个六元组。事实上，当op=0时，题目只有一个输入变量n。记大小正好为n的C形阵的价值和为f(n)，我们将暴力得出的f(n)输出，发现f(6)=f(2)*f(3)、f(15)=f(3)*f(5)…这提示我们应该进行质因数分解，最后把答案相乘。而对于f(p^k)，我们设B=F=n，A=x，则C=n^2/x；E=y，则G=n^2/y，价值D=n^3/xy，利用组合数学的知识对D求和，我们就得到了op=0的一个可以通过n<=10^5的做法，加上暴力部分分可以拿到30+20=50分。

第五题难度较大，而且我在考试时由于第四题推算次数过多导致时间剩余较少，于是果断决定写枚举程序，获得了n、m极小条件下的35部分分。实际上，我在写完这部分的部分分后距离考试结束只有5分钟，证明我的决策是正确的。

回顾整个考试过程，多亏了CSP的多次提交取最高分的赛制，即使没有多少知识点储备也能拿到一个不错的分数。

感谢CCF搭建了一个让即使像我一样没什么天赋的人也能踏上算法竞赛之路的算法竞赛舞台，也感谢CCF能给我这次机会分享自己的故事和心得感悟。祝愿CSP认证越办越好，吸引更多人研究算法，让更多像我一样的学生领略到算法的美。在这之后，我也希望能在CCF的这个舞台上，打一辈子算法竞赛，我什么都会做的（笑）。