【小码匠自习室】CSP-J/S复试高分秘诀经验分享

前言

这篇文章是今年3月份参加NOI Online测试之前和老码农一起整理的一份资料，分享给备战今年10月份复赛的OIer，

还有不到4个月，还有很多不会的知识点，没有退路，唯有努力坚持前行。

重点

• Step1：通读所有题目：确定大概算法、确定是否能打表或者暴力枚举
• Step2：草稿纸：仔细审题，标重点；梳理分支；梳理数据规模
• Step3：静态检查：先检查代码，再调试，省时间
• Step4：最后10分钟检查：C++程序名、输入文件名、输出文件名、去掉注释：freopen，fclose代码

准备

• 携带橡皮、笔，笔可适当带3种颜色不同，便于【标记重点】、【关键信息】

阅读题目：仔细审题

• 通读：题目2～3遍，判断
  • 难易度，通常从前往后越来越难
  • 大概使用算法：打表、枚举、排序、递归、递推、贪心、高精度、图、树、动态规划
• 标记：在纸上标记【重点信息】、【细节信息】、【特别注意事项】

梳理思路：三思而后行

• 阅读数据规模，分析样例数据分布：重要、重要、重要
  • 小：可能搜索算法
  • 大：可能考虑动态规划、数学算法
  • 比如long型数据太大，会用科学计数法输出
  • 极小值：0、1（0、1一定要重视）
  • 极大值：数组越界、数值溢出
  • 正常值
  • 异常值：边界值，例如：文具订购，三种都买14元，则边界值：13元、14元、15元
  • 数据规模
• 条件分支：草稿纸
  • 各条件分支结合样例数据及题目先梳理清楚，用笔在草稿纸上记录下来
• 确认算法
  • 根据数据规模，判断使用算法时间复杂度、空间复杂度（O(N^2 )、O(N log N)、O(N)）
• 遇到熟悉的题目要十分警惕，先在草稿纸上演算计算步骤，并测试其正确性
• 编写代码前要有充足思考时间，最好举例子通过草稿纸验证 -> 尽量不要边写边改
  • 比如递推怎么写
  • 比如动态规划方程怎么写
  • 比如？？？

编程

注意点

• 程序名和输入输出文件
  • 文件名是否和题目吻合，一定要注意大小写、扩展名 -> 一旦拼错，爆零
• 编程：保持思路清晰，参照样例数据分布和条件分支，尽量一次把程序编好
• 检查程序：静态检查 -> 动态来回调试程序是非常耗时的，多思考，更省时间
  • 变量名、函数名是否对上
  • 循环、条件分支是否得当
  • 输出文字时，大小写是否正确
  • 边界情况是否考虑周全
  • ...
  • 不着急直接调试，先重新阅读自己编写程序。
• 调试
  • 数据随机生成器
  • 输入数据格式是否正确
  • 样例数据所有分支依次跑到
  • 再次思考有无遗漏分支
  • 对拍：数据随机生成，与暴力程序相互验证正确性
• 空间、时间复杂度
  • 空间复杂度：sizeof(数组名字) 数组空间
  • 时间复杂度：clock：开始和结尾记录时间差、t1 = clock()、t2 = clock()
• 注意控制单题解题时间，别一条道跑到黑

暴力分全拿

• 写暴力、写暴力！，一定要正确的暴力!
• 对于难题，依据题目数据分布、条件分布，确定是否可以枚举部分分支，得到部分分数
• 确认是否可以打表得分

深呼吸放松，奇思妙想

• 遇到特别难的问题，不要气馁
• 遇到卡壳的情况，深呼吸，上厕所洗把脸，也许就会奇思妙想
• 尽力就行，不要给自己太大压力

最后十分钟

全面检查

• 命名是否和题目一致：程序文件名、程序中写的输入输出文件名 -> 必须一致，不一致就爆零
• 程序存放的目录是否按要求
• 输入输出格式与样例对照，特殊字符串（Yes，No，Impossible）的大小写
• 数组空间的大小，对比空间大小限制

骗分导论

• 骗分导论：打表 / 找规律 / 贪心 / 搜索 / 样例 / 无解 / 暴力+分段