CSP-J/S 第二轮认证

CSP-J/S 第二轮认证将在下周六举行,认证采用上机测试,考生们需要认真阅读题目,按照要求为每道题编写出一个程序,这也是检验同学们算法学习效果的最好机会。

为了备战CSP,虽然同学们都非常地认真,但是每次考完总有同学出现意料之外的错误,导致最终得分和估分不符。

即使老师会反复强调,要求同学们细心检查,但仍有学生因为一些小错误,白白丢失20~150分。竞赛中人数最多的分数段就在一等奖分数线附近, 因此每一分都非常宝贵,一个小失误就会名落孙山。

同时我们也要注意到,真正的高手不管怎么考,分数都不会出现大的波动。模拟考出现失误不能用一句简单的”马虎了”就过去,一定要有流程化的检查机制确保以后不再丢分!本文基于笔者个人的多次参赛经验以及几百位学生在模拟考中出现的低级错误, 为大家总结比赛中常见的错误,并推荐一种检查流程,希望考生能重视检查程序,而不是写完程序后无所事事,白白浪费时间!

常见错误

1、文件夹、文件名、输入输出文件名出错 致命程度★★★★★

① 文件名拼写错误。考试中每道题名字都是英文,一般都是某个英文单词或者缩写。其对应的文件夹名、程序文件名、输入文件名、输出文件名,这四个部分的英文名称都是一样的,都是小写,一定要多检查几遍!

学生在比赛紧张的环境中容易脑补成自己熟悉的单词,例如,考试时有道题程序需要命名为stat,而学生写成了start。有的题英文名字较长,一眼可能将某些字母混淆了。例如有道题名字叫circuit,而学生写成了circult;有时候是学生的文件后缀名写错了,C++语言对应的后缀名是CPP文件,如果漏掉后缀名会导致程序无法正常编译。

② 输入输出文件名出错。每道题的输入输出文件名应该和题目名字完全相同。但是有些同学在调试过程中可能会修改文件名,例如有学生去年在第1题调试时将文件输入改成了power2.in最后忘了改回来,导致此题0分。

③ 忘建子文件夹。考生应该有自己文件夹,并且在文件夹里面,每道题也要单独建一个文件夹,文件夹与这道题同名,这个属于知道就不会犯的错误, 但每年总有人因此爆0。

2、输入输出出错 致命程度★★★★★

① 文件输入输出被注释。很多同学不习惯文件输入输出,因此把freopen语句注释掉了,最后忘记删除注释符号,导致0分。建议同学们最好习惯使用文件输入输出的方式测试程序,一方面杜绝这个问题的发生,另一方面减少重复的复制和调试工作。

② 文件输入输出没写对。一般是突然不记得具体写法了。考前一定再看一眼, 别考场犯傻。只需要记住两句话: freopen(“xxxx.in”,“r”,stdin); freopen(“xxxx.out”,“w”,stdout); 其中XXXX和题目的文件名相同。

③ freopen写的位置不对。虽然这个错误不常见,但也有几个同学出现了这样的问题。主程序开始后先进行了一部分读入再写的文件输入输出, 导致读入错位,0分。同学们一定要养成习惯,主程序刚开始第一行就写文件输入输出, 不要在最后添添补补。

3、读题出错 错误致命程度★★★★

① 题目太长不认真读,按照自己认知或根据样例脑补题意。这类问题非常常见,题面中经常会有很多背景描述,与具体做法关联较小,但是也会有非常重要的条件或者提示,混杂在题面中。漏看这些信息就会导致整个题理解有偏差甚至完全不对。例如, 模拟考中“字符串编辑器”这道题,有同学看到样例就以为是统计字符数量,没有发现是统计连续字符个数。

4、变量出错 错误致命程度★★★★

① 没计算变量的最大值。最常见的是学生不知道数据超过了int,如果题目读入的所有数据都在10^9之内,而这是否说明本道题不需要用long long呢?不是的, 核心是要检验每个算式中间结果的最大值会不会超 long long。例如,模拟考中“加密算法”那道题读入的a,n < 10^9, 但程序中需要求出p和a的乘积,需要计算出p<10^6,那么乘积肯定会爆int范围。再举个例子, int x = 50000 * 50000 / 2; 这个语句x能得到正确结果吗? 是不能的, 因为算式从左向右计算, 中间50000 * 50000已经爆int了, 即使最后没有超过int范围也没用了, 得写成 int x = 1LL * 50000 * 50000 / 2; 才能正确运行。

② 变量类型没定义全或者使用错误。有些学生想到了long long,但是有些地方忘记使用long long,比如说函数返回值没写long long,或者函数调用的时候用的int。再比如在“买不如造”这道题中,某同学想到了满分做法,但是没有注意到p<10^15这个数据范围,输入的时候使用了%d,导致了60分的严重失分。

③ 变量初始化不正确。比如说求最小值的时候,如果最小值的变量类型是long long,应该将ans的初始值设为足够大的数,例如9e18。求最大值时,如果答案可能为0,那么ans应该初始化成负数。在18年普及组第2题龙虎斗中, 很多同学都想到了要开long long,然而题目有一步要求最小值,不少同学想当然的写成了long long d_min = 1e9; 这会使得初值不够大,无法准确更新最小值变量导致出错。

④ 多组数据出错。对于多组数据,应该在处理每组数据之前将所有的变量都初始化一遍。否则,第一次运行由于变量定义在全局有默认初值为0,答案没有出错,多次运行就会出现问题。

⑤ 变量名出错。我们通常会使用using namespace std;这导致我们定义的变量名可能会跟std命名空间里的名字冲突,而且在Windows环境下编译器是不报错的,但考试时在Linux环境下评测会出错,因此同学们的变量名不要使用hash、x0、x1、y0、y1、time、next、pipe等。为了防止同学们使用变量时出现混淆,建议同学们在同一个程序中不要定义任何同名变量。

5、数组出错 错误致命程度★★★★

① 数组大小出错。这是考试中十分经典的错误,数组大小少开一个0或者与题目中其他值的范围搞混导致数组开小了非常常见,基本每次考试都有同学说我数组开小了。有时候是这个数组开对了,另一个数组有开小了。这种情况建议同学们定义1~2个常量,所有数组定义时大小都使用常量,方便统一修改,最后直接检查常量大小即可。常量大小可以用1e6+10这种写法,这样就不会出现零的个数没写对的情况,具体每个数组用哪个常量的值一定仔细考虑这个数组下标是对应着题目中哪个量,它的范围是多少。

② 数组占用内存太大。通常情况下,题目的空间限制都是128MB,空间限制在128MB时,数组元素类型为int时,元素个数最多千万级别(约3*10^7,二维数组或多维数组的每个维度的大小要相乘),并且大型数组必须要定义在到main函数外面的全局变量区。

③ 多维数组维度的意义没想清楚。例如, 模拟考“扑克大师”那道题某同学定义了一个二维数组大小是a[5][15],a[i][j]表示花色为i,点数为j的扑克牌数量,而这个同学在使用时却把2个维度用反了, 导致了数组越界,拿到0分。

④ 数组下标调用时使用加法或减法没注意数组越界。最常见的是对下标做减法, 例如做背包DP时会使用到dp[j-w[i]],这时必须在引用前判断 j – w[i] >= 0,否则就可能出现运行时错误。

6、做题习惯出错 错误致命程度★★★★

① 输出格式错误。输出字符串的时候一定要确定大小写是否正确,不要输出多余空格和换行。输出数字时要看清是每行一个还是每行多个。写题之前必须细心检查输出格式要求。

② 没有及时保存。有些同学没有养成及时保存的习惯,导致考试中如果电脑出现故障,损失很大,建议同学们至少每10分钟保存一次程序。北京今年有提交系统,如果写完了一道题,建议同学们及时提交,不要等到最后几分钟再交。

③ 调试语句没删。有些粗心的同学在调试完题目后,就直接做下一道题,结果这道题的调试语句都没有删,导致此题结果出错。

④ 题目没有验证正确性就写。很多同学想到的做法通过样例之后就满足了,但是事实上是错的,比如去年有一道“三国演义”,有同学直接计算三个国家的兵力和就算出答案,虽然可以过样例,但是自己设计几组不太平衡的数据就能发现错误很严重。

⑤ 题目没有验证时间复杂度就写。很多同学读懂题目后,发现题目流程比较简单,就大喜过望,立马写完了程序,通过几组数据之后就搞定了,其实有时候,最简单的方法忽略了很多优化,时间复杂度是不过关的。比如“加密算法”这道题,m<10^5,因此判断n是否有效必须在1000次以内完成,而n<10^9,因此O(根号n)的方法判断n是否有效是不能拿到满分的,必须要想到至少O(三次方根n)的方法。但是很多同学写出自己的方法后觉得没问题了,直接去做下一题了,导致了40~70分的丢分。

7、没写部分分做法 错误致命程度★★★

① 总以为自己的高级算法一定是对的。如果20分钟的暴力能拿到30分以上的分数,这个做法一定要写。一方面可以找规律为高级算法做铺垫,另一方面可以与高级算·法进行对拍验证正确性,最重要的是不会因为高级算法写炸了直接0分,可以在输入后特判数据的类型,小数据或简单数据用暴力做法, 起码有个兜底的分数。一等奖不在于做出多少难题, 而在于不丢应得的分数!

② 总以为暴力没有多少分。事实上,有些题目的暴力方法很简单,并且数据很难构造,因此暴力总是能拿到很多分数。比如“字符串编辑器”这道题,只要用数组模拟一下题目中的5种操作,就能很轻松的写出程序,并且拿到很高的分数,甚至有同学通过暴力拿到了95分。

③ 时间来不及没有写暴力。每次考试结束,总有同学跟笔者说:“老师,我没有时间写第四题暴力了!” 而第四题的暴力通常都比较容易写,只要写了能获得20~40分,如果前三题完成情况和其他同学差不多,那么第四题的分数就非常关键了!在考试的时候,建议同学们先通读一下四道题,尤其评估一下后两题的暴力好不好写,如果做完第一题(如果时间很足可以再做第二题),先把三四题的暴力写完,确保自己能拿到容易的分数。

检查流程

1、检查程序正确性。每道题至少举出3组数据,验证自己程序的正确性,其中的2组是自己能算出来的稍大的数据,出错时方便找到问题在哪,剩下1组是边界数据,验证特殊情况下程序是否能正确运行。另外,有能力的同学可以写个暴力程序与自己高级做法进行对拍,更有效的验证程序正确性。最好是随机出一个极限数据,方便检验算法是否超时,还有数组是否开得够大。

2、检查文件名,对照首页题目名检查文件夹、程序文件、输入文件、输出文件这四个位置的名字是否正确。

3、检查文件输入输出格式,确保自己定义了cstdio头文件。

4、重新读题,看有没有漏的重点条件。

5、重新一一核对所有数组每个维度的大小与题目对应的数据范围。

6、检查程序里每个数组下标会不会越界。

7、计算程序中每个变量的最大值,考虑会不会超过int或者long long,对于使用long long的题,检查设计到的每个环节是否都是 long long。

8、有时间一定要写部分分做法。

9、确认以上没有问题后,最后编译一次,以免手滑导致程序运行不了,编译成功后关闭编程软件中的这个文件防止误操作修改。

10、最后打开子文件夹内的程序文件,确认文件保存在了正确位置。

11、部分城市的考生需要确认自己提交在系统中的程序都是自己检查无误的正确程序,确认文件保存正确后可以再提交一次检查过的程序。