CSP-J复赛备考策略

CSP-J复赛题目的特点是：

• 第一题：算法比较明显，或者和数学关系比较大的题目。
• 第二题：好上手，但程序量稍大，考虑全面有一定难度。
• 第三和四题：一般是搜索，或者算法不明显的题目。

算法方面，可能考到的有：穷举、搜索（回溯即可）、动态规划（几乎必考）、贪心、递推、递归等，以及简单的数据结构，需熟悉字符串的操作和排序。

1、知识体系回顾，多做经典题目

在算法方面可能考到的是：穷举、搜索（回溯就可以了）、动态规划（几乎必考）、贪心、递归、简单的图论算法（dijkstra等），熟悉字符串的操作（包括字符串的几个常用函数）和排序算法就差不多了。记住：信息学不是看会的，是练会的。一定要多看多想多练。

2、养成编码和调试习惯

复赛考查的算法并不困难，选手在实现上的问题往往更大。因此建议：

• 充分利用草稿纸，不要对自己的“心算能力”太自信。做信息学竞赛题的思维过程丰富且曲折多变，考虑问题必须全面。
• 编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误之处。思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视）。
• 多做套题，做单个题目和套题感觉不同。做套题要涉及到时间分配和做题顺序等，这些同样十分重要。

3、最大限度发挥水平

• 认真审题：审题对于信息学竞赛尤其重要。同一题目数据限制不同，难度差异可能很大。例如：输入A、B，输出A + B的值。若题目说0 <= A, B <= 10000，这是一道简单题目；但如果题目说0 <= A, B <= 10¹⁰⁰ ，则显然要用到高精度数的处理。从某种意义上说，数据限制暗示了可能的算法，数据小，也许适合搜索，数据大了，可能只能考虑动态规划、数学方法等高效算法。
• 正确估计题目的难度和自己的水平：平时最熟悉和有把握的题，一定要做对。熟悉的题目要加强编程熟练度、准确度、测试和调试能力，把自己有能力拿到的分拿稳。
• 重视测试：测试的数据既要考虑一般情况，也要考虑特殊情况，评分的唯一标准是测试数据。一道困难的题目如果无法下手，在时间允许的情况下一定要写一个能解一些特殊情况的程序。很多最优化题目，不要一个字都不写，根据“直觉”算法（如贪心），虽得不了满分，也能得一定分数。
• 编程过程中注意随时存盘：最好保留一些不同版本（如算法不同）的程序，便于选择修改。比赛时首先设置编程环境的工作路径，保存文件的文件名以及程序中引用的输入输出文件名一定要按要求命名，包括文件名的大小写。程序中标识输入输出文件时，一定要用相对路径，绝不可用绝对路径。

CSP-J复赛必学知识点

1. 模拟算法（暴力枚举），按照题目的要求做，保证时间和正确性即可。

2. 搜索与回溯，主要是DFS（深度优先搜索）和BFS（宽度优先搜索），基本没有直接的暴力搜索。一般是记忆化搜索加剪枝，普及组第三题难度。

3. 简单操作：如筛法、前缀和、快速幂、高精度、辗转相除法等，掌握全面即可应对大部分处理数据上的问题。

4. 队列（单调队列）、栈、堆、链表等基础数据结构。

5. 简单二分和分治（快速排序，归并排序）。

6. 贪心，要保证贪心的正确性，如果无法证明也可以用来骗分。

7. 数学知识、公式计算，要点在于公式的化简与变形，经过反复操作后也许就能得出重要结论。

8. 简单的动态规划，容易推出状态转移方程，要注意初值与计算边界条件。

9. 字符串基本操作，插入、删除、查找等。

10. 经典例题变形加深：八皇后、马的走法、背包问题等。

在程序设计方面，需要具备以下几个能力：

1. 算法的实现能力

2. 程序调试基本能力

3. 设计测试数据的基本能力

4. 程序的时间复杂度和空间复杂度的估计