CCF-CSP 备考攻略

(Updated: )
攻略

CCF-CSP 备考攻略

一、参考资料

  1. 【程序媛营业】CSP从入门到放弃——CCF优秀大学生的CSP认证高分经验分享

二、CSP考察内容概述

2.1 程序设计基础

  • 逻辑与数学运算
  • 分支循环
  • 过程调用(递归)
  • 字符串操作
  • 文件操作等

2.2 数据结构

  • 线性表（数组、队列、栈、链表）
  • 树（堆、排序二叉树）
  • 哈希表，集合
  • 图

2.3 算法与算法设计策略

  • 排序与查找
  • 枚举，贪心策略
  • 分治策略
  • 递推与递归
  • 动态规划
  • 搜索
  • 图论算法
  • 计算几何
  • 字符串算法
  • 随机算法，近似算法等

三、各题目特点与应对策略

3.1 难度概述

难度呈幂次增长（第一题难度n，第二题难度n²，第三题难度n³……）

3.2 第一题（基础题）

  • 输入 输出 if-else 一层循环
  • 20行代码左右
  • 注意细节，容易丢10分
    • long long 类型
    • 边界条件
    • 特殊情况
  • 会用文件读入很重要
    • 可以节省大量在终端敲入数据的时间 
      1
      2
      #include<stdio.h>
      freopen("in.txt","r",stdin);
  • 宏定义简化for循环书写耗时 
    1
    #define _for(i,a,b) for(int i = a;i < b;i++)
  • 声明数组大小的时候最好用const定义的伪常量方便修改 
    1
    2
    3
    const int N = 1007;
    int Num[N], Sum[N];
    char str[N];
  • 一般是数值方面的问题（一群整数）基本一个for循环可以解决的了，比较简单，学过C语言基本可以得分

3.3 第二题：小模拟（基础）

  • 多重循环 接近n²复杂度
  • 一般是时序题 通常要排序
  • 简单的数学运算
  • 对多元数组的熟练运用
  • 学会STL可能会有奇效
  • 最少得需要两个For循环，要说两个For循环也不难，难就难在一般是时序题、通常要排序，而且要用到多元数据
  • 例如18年3月的第二题碰撞的小球，涉及到长度、个数、时间、速度等不同单位的数据

3.4 第三题：大模拟（进阶）

  • 熟练掌握各种输入函数和字符串处理
  • 熟练掌握dfs bfs
  • 会设计复杂的层次化结构
  • 要相信题目本身不难，只是变态而已
  • 文明考试，请勿砸显示器、摔键盘
  • 一般会是字符串的处理，而且一般是对复杂文本的处理
  • 最好使用C++里边的String类做字符串处理，如果要自己用c语言写字符串处理函数，不仅不一定写对，而且还会相当麻烦，浪费时间

3.5 第四题

  • 一般会用到高等数据结构，比如树、图
  • 需要用到的算法也不是课本上学到的简单算法，得用更高级一点的时间、空间效率更高一点的算法

3.6 第五题

  • 一般是纯粹的算法题
  • 但是算法难度一般是ACM级别的，所以经过ACM训练的训练员也不一定能拿满分

四、备考准备指南

4.1 训练资料选择

  • ACM题库
  • CCF-CSP真题，总结每年题型

4.2 参考书籍推荐

CCF-CSP考试是可以带书进去的：

  • 如果对语法掌握不熟练的话可以带一本编程语言书
  • 最好带一本C++ STL方面的书（是STL工具书，STL怎么使用的书，而不是STL源码分析类的书）
    • STL方面的书可以帮助我们又快有准的写出想要的排序等代码，如果我们当场写的话会很浪费时间
  • 算法书，有资源的可以找一本ACM培训竞赛书，前面也说过书上的算法对付考试是不行的，需要更好的算法

4.3 日常练习规划

  • 每天写程序，不能手生
  • 最少得2h，适应4h的考试时间

五、得分技巧与考试策略

5.1 评分机制理解

CCF-CSP是机器阅卷评分，题目规定有代码运行用时，超时的测试用例是没有分的。给分目前最小单位是10分，按照对你的代码的一个测试，比如从10到100这个规模来20%测试用例，100-1000来30%测试用例，1000-10000来50%测试用例，通过一个测试用例给10分，也就是说：

  • 我们自己测试对的在评分的时候不一定能拿满分
  • 我们在3、4、5题上也可以通过实现简单数据集上的代码而得分，而不是一分得不了
  • 3、4、5题我们可以从最小规模开始，可以排除特殊情况来写代码，只要简单的测试用例能通过我们就能得分

5.2 核心能力训练

我们要想拿高分就要有针对性的训练：

  • 首先不能再出基础性错误，比如输入输出，要按照题目规定来，要求输入或输出两个数据间用空格分开我们不能使用回车分开，这样会导致0分
    • 我们可以通过真题训练自己所使用语言输入输出代码的格式，也不要在这上面浪费时间
  • 锻炼单步调试能力
    • 在平时编程的时候我们可以使用cout来输出看一下执行过程中变量的值，但是这样容易犯错——考试的使用万一没有把测试用的cout删除，这样就会误导机器判分，机器判断输出和正确输出不一样就是0分

5.3 考试注意事项

  • 通过所有题目样例不代表解法完全正确，很可能是存在漏洞的代码恰好满足了有限的测试用例，从而产生误导

六、特殊情况下的应对策略（骗分技巧）

6.1 骗分的本质

  • 利用好”分点给分”的规则
  • 抓住评测机”只看结果不看过程”的评分机制
  • 用简单的程序获得尽可能多的分数
  • 骗分是骗机器，不是骗自己

6.2 心态调整

  • 先完成简单的题目
  • 需要估计出有多少盈利 再分配时间

6.3 非完美算法应用

  • 有分总比没分好
  • 虽然写不出完美的算法，但是可以用贪心、搜索之类的算法，来骗到部分得分
    • ✓ 在许多动态规划题型中，贪心虽然是假算法，但在相当可观的数据中撞上正确答案
    • ✓ 搜索是个老实的笨办法，虽然慢但是正确，加上剪枝更加能打

6.4 数学规律寻找

  • 计算机竞赛中不需要有完美的证明
  • 对于输出答案或者中间参数只要你认为有规律不要管那么多用就完事了，能证明则更好
  • 暴力打表
    • ✓ 斐波那契数列
    • ✓ 杨辉三角
    • ✓ 卡特兰数

6.5 分类讨论技巧

  • 对不同数据量采用不同的算法
  • 对不同的输入数据采用不同策略
  • 考虑特殊数据

6.6 固定输出策略

  • 最后的最后，一点思路都没有，可以考虑只输出一个值，如果对了也有10分
  • 但这个值也不能乱输出，也要有一定的依据
  • 选择输出可能性最大的，骗也要骗的精彩
    • ✓ 无解输出”No”/“-1”
    • ✓ 若Bob获胜则输出”Bob wins.”，否则输出”Alice wins.”
    • ✓ example output

6.7 骗分的最高境界是不骗分

  • 第39届CCFCSP认证，采用子任务形式，只有子任务的所有样例都通过才给这一部分的分数
  • 所以只输入样例是没有分数的