考试技巧-CSP二轮考前训练

# CSP二轮考前训练

---

既然是考试，总是想获得好成绩，什么样的成绩是好成绩

---

## 近几年山东省CSP-J成绩一二等奖分数线
|       年份        |  二等奖 | 一等奖 |
| :---------------: |  :----: | :----: |
| 2019 |  100   |  185   |
| 2020 |  100   |  165   |
| 2021 |  100   |  190   |
| 2022（口罩原因山东未考） |   |  |
| 2023 |  40 | 170 |
---

---

## 近几年山东省CSP-S成绩一二等奖分数线
|       年份        | 三等奖 | 二等奖 | 一等奖 |
| :---------------: | :----: | :----: | :----: |
| 2019（两试，6题） |   80   |  110   |  186   |
|       2020        |   30   |   65   |  110   |
|       2021        |   \\   |   30   |   90   |
| 2022（口罩原因山东未考） |  |  |  |
| 2023 | 55| 80 | 140 |

以上成绩线在NOI官网可查。
 1. 为什么选最近的这几年?
 这几年是新的CSP的形式进行的，尤其21年及以后的试题是在NOI大纲指导下的。   
 2. 每年基本上比较稳定,可能会因为题目难度不同导致稍有不同。

---

---

---
## 目标

可以根据对照NOI大纲要求的难度范围的知识点来检查，自己的目标可以是：

- CSP-S一等奖 ：T1、T2 AC，T3、T4得部分分，

- CSP-S二等奖：T1 AC,T2，T3得部分分，T4没有时间可以不看。

- 高分一等奖： T1、T2、T3 AC，T4 AC或得部分分

山东一般是没有三等奖的，因前几年山东总体水平大约在全国中等偏下（平均分低于全国平均分）。

---

##  实现目标的策略
1. 知识点的掌握程度：没有捷径，只能一个一个学习，学习一个要求掌握一个，不要贪多不精。
2. 能力提升
    1. 基本技能：打字速度与准确度、计算机操作系统的基本操作、命令行编译（g++，NOI大纲有要求）；（提升效率和速度，节约时间来思考难题）
    2. 代码能力和数学建模能力：能从题面中构建数学模型，用代码实现数学模型。打暴力的能力与速度。
    3. 阅读能力和英语能力

3. 习惯改变: 刷题时总是喜欢在IDE中直接编译运行，复制样例看结果，；不手动自己做小样例；样例一过就在OJ中提交，一交就错，不仔细思考细节，要提升一次通过率。（CSP-J2是OI赛制）

4. 考试技巧：时间分配、自己对每题得分的要求，部分测试点的得分。

---

## NOI大纲知识点
普及组知识范围：
1. C++语法知识：基础语法、常用函数、数组、字符串、函数等知识
2. 基础算法：模拟、枚举、贪心、递归、递推等基础算法和技巧，搜索算法与技巧
3. 数据结构入门：结构体、栈、队列、链表、图、树、二叉树等基础结构及其应用
4. 排序算法：sort函数及结构体排序，冒泡排序，选择排序，插入排序，桶排序
5. 数学入门：进制转换、编码、位运算、高精度，加法乘法原理，排列组合，杨辉三角
6. 初等数论：整除、质数、同余等概念，因子分解，欧几里得算法，埃氏筛法，欧拉筛法，快速幂
2. 动态规划：递推、递归与记忆递归，线性DP（一维、二维、高维），背包DP，区间DP
3. 图论算法：图与树的遍历，最短路算法（floyd、bfs、dijkstra、spfa等）
4. 考试技巧：输入输出、重定向，考试提交与爆零问题，测试、调试技巧，对拍技巧，数据范围分析，考试策略等

---

提高组知识范围：

1. 数据结构进阶：priority_queue、map、set等STL模板，单调栈，单调队列，树状数组，线段树，倍增表，并查集，二叉平衡树，哈希表等
2. 图论进阶：拓扑排序，最小生成树，次小生成树，次短路，欧拉道路和回路等算法，二分图，环与连通， 强连通缩点，割点与割边。最近公共祖先，树的序，树上差分，树链剖分等。
3. 动态规划进阶：树型DP，状压DP，图上拓扑DP，DP优化技巧。
4. 数论进阶：费马小定理，欧拉函数与欧拉定理，威尔逊定理，裴蜀定理，扩展欧几里得算法，中国剩余定理，逆元运算等。
5. 数学进阶：鸽巢原理，冗斥原理，二项式定理，可重集排列与组合，错排列与圆排列，卡特兰数，矩阵运算，高斯消元，凸包，矩阵快速幂
6. 分治思维：二分查找，二分答案，分治算法，归并排序，快速排序，逆序对问题，点对问题
7. 字符串进阶：字符串常见函数，hash函数，KMP算法，字典树，01字典树，异或问题，回文问题与Manache算法。

注：知识范围很大，不一定要完全掌握，知识掌握情况与考试得分并不一定成正比。

---

## 命令行运行与G++编译
### 一.cmd的运行方式
1. win+R 打开运行框，输入cmd回车，出现命令行窗口
2. win 后在搜索中输入cmd回车，出现命令行窗口
3. 在文件夹窗口的地址栏中输入cmd回车，出现命令行窗口。
---
在命令行中，

| 内部命令 | 含义 | 参数 | 示例 |
| ---- | ---- | --- | ----- |
| md | make directory| 新建立的文件夹名称 | md 123 |
| rd | remove directory | 要删除的文件夹名称 | rd 123 |
| cd | change directory| 要进入的文件夹名称 | cd 123 |
| dir| 列出当前目录下的所有文件与文件夹 |||
| rename | 更改文件名 | 原文件名 新文件名| rename 123.cpp 456.cpp |
|del|删除一个文件|要删除的文件名称|del 123.cpp|

使用 `E:` 来改变盘

可以使用 ` echo #include > 456.cpp ` 来直接生成一个456.cpp,内容是```#include```

```start 456.cpp``` 使用cpp关联的程序打开```456.cpp```

```notepad 1.in ```使用记事本打开```1.in ```
---
### 二.设置path
在命令行中运行命令时，如果显示找不到此命令时，可能是环境变量path中没有此命令的路径，可以在我的电脑上右键属性中找高级属性设置，找到系统环境变量中path，修改path，注意，新加的目录与之前的要用英文状态下的分号（;）进行分隔。
---
### 三.命令行编译
将g++的路径加入path后，重启命令行窗口后可以使用g++ -v来测试成功与否。

成功后，可以使用命令 g++ 你要编译的源代码文件名 -o 要生成的可执行文件名 来编译，如：
```bash
g++ 123.cpp -o 123

g++ 123.cpp -o 123 -O2 (2级优化，俗称吸氧)
```
---

### 四、命令行重定向
- 命令 > 文件 ：将命令的输出重定向至文件中
- 命令 < 文件 ：将文件内容做为命令的输入

---

### 五、文件内容比较
fc 文件1 文件2 
如果有不同，会输出有那些不同，没有不同，fc返回0

---

## 爆零问题
原因有很多：
1. 程序有语法错误
2. 程序编译错误
3. 数组开小了
4. 输出不按要求输出
5. 变量命名冲突（万能头的问题等）
6. 少头文件
7. 。。。

---

## 程序中的输入输出重定向freopen
### freopen()
在程序中进行输入输出重定向。

freopen这个函数，在OI比赛中应用很广，因为OI试题中可能有大量输入数据，程序运行往往不是一次成功的，每次运行都重新输入很浪费时间，因此freopen就可以解决测试数据的重复输入问题。

函数声明：

```c++
FILE * freopen(const char *filename, const char *mode,FILE *stream);
//参数说明：
//filename：要打开的文件名；
//mode：文件打开的模式，和fopen中的模式（r/w）相同。
//stream：文件指针，通常使用标准流文件（stdin/stdout/stderr）
```
使用方法：

```c++
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
fclose(stdin);
fclose(stdout);
//freopen()函数重定向了标准流，使其指向指定文件，因此不需要修改scanf和printf。
```
---

## 测试、调试技巧（函数式编程，面向过程）
1. 尽可能的多使用函数来编程
2. 根据不同的数据范围选择不同的算法
3. 使用assert进行调试函数 
4. 使用cout等输出来调试
---
下面的代码是我常用的一个模板
```c++
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e4 + 5;
int n, a[N];

void initInput(void)
{
    cin >> n;
    // ...
}
void handle(void)
{
    // ...
}
int main(void)
{
    initInput();
    handle();
    return 0;
}

```
---
## 时间与空间复杂度计算
### 1、算法的目标
算法是对问题的解决方案，但一个问题会有很多种算法，通常一个好的算法需要具备以下目标：

- 正确性：对合法输入、非法输入、边界输入都能正确处理，输出合理的结果。
- 可读性：算法应该描述清晰，方便阅读、理解和交流。
- 健壮性：算法应运行一致，对于相同的输入始终输出相同的结果。
- 高效性：算法应占用最少的cpu和内存得到满足的结果，这通过时间复杂度和空间复杂度进行判定。

---

### 2、算法复杂度
算法复杂度用来衡量算法的高效性，简单的说就是：

算法运行的有多快（时间效率）
内存占用的有多少（空间效率）
然而，运行时间和语言、机器、机器的状态、数据量的大小都有关系，不好横向比较，为此通常使用一个时间复杂度（相对度量）的概念来衡量算法有多快。

我们假设其它状态不变，仅当问题规模（数据大小）增长时，指令执行的次数也在增长，那么指令执行次数相对于问题规模来说，会构成一个函数T(n)。

---

例如－对于以下数组求和的算法$1+2+3+...+n：$

```c++
int sum = 0; //指令数为1
for(int i=0; i<n; i++)
  sum += n; //指令数为 n
cout << n; //指令数为1
```

显然，总的指令数为$T(n) = n + 2$
---
### 3、大O函数
假设一个算法的$T(n) = 4n^3 - 2n + 5$

当n越来越大时，对于T(n)增长的贡献来说，最高阶的n^3会占据主导地位，其它项可被忽略。

例如：

n=100时，$n^3$是n的的1万倍，因此可忽略掉n的贡献。
当n从100变成1000时，$n^3$会增长1000倍，此时$4n^3$前面的4也可倍忽略。
我们一般用大O函数来表示最主要的贡献部分：$O(T(n)) = O(n^3)$，也即算法的时间复杂度。

数学定义：当存在正常数c和某个规模n0，如果对所有的n>=n0，都有f(n) <= c T(n)，则称f(n)为T(n)的大O函数，写成：f(n) = O(T(n))。
---
### 4、常见大O函数
| 函数       | 名称            | 例子           |
| ---------- | --------------- | -------------- |
| O(1)       | 常数阶          | 交换算法       |
| O(logn)    | 对数阶          | 二分查找算法   |
| O(n)       | 线性阶          | 求和算法       |
| O($nlogn$) | 线性对数阶      | 快速排序算法   |
| O($n^2$)   | 平方阶          | 冒泡排序算法   |
| O($n^c$)   | 多项式阶（c>1） | 多重循环的算法 |
| O($c^n$)   | 指数阶          | 汉诺塔问题     |
| O(n!)      | 阶乘阶          | 旅行商问题     |
---
### 复杂度计算与例子
### 1、计算方法
对算法（或代码）的指令次数进行计算组成$T(n)$，只保留最高阶项，然后去掉最高阶项前面的常数。

例如以下代码的$T(n) = 3$, 时间复杂度为O(1)：

```c++
int a=20;
int b = a*3 + 4;
cout << b;
```
---

### 2、O(n)的例子
输出数组元素：

```c++
for(int i=0; i<n; i++)
  cout << a[n] << " ";
```
---

### 3、 O(logn)的例子
给定n，求2的指数p，使得p <= n < 2p

```c++
int p = 1;
while(p < n) {
  p *= 2;
}
cout << p; 
```
---
### 4、O($n^2$)的例子
打印二维数组：

```c++
for(int i=0; i<n; i++) {
  for(int j=0; j<n; j++)
    cout << a[i][j] << " ";
  cout << endl;
}
```
### 5、O(nlogn)的例子
```c++
for(int i=0; i<n; i++)
  for(int j=0; j<n; j *= 2)
     ...

```
---

### 6、O($2^n$) 的例子
汉诺塔问题－代码略。

递归表达式：

1. 将n-1个盘子从A经过C移动到B
1. 将第n个盘子从A移动到C
1. 将n-1个盘子从B经过A移动到C

显然$T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = ....$，最高阶项为$2^n$，即O(2^n)。
---
### 7、O(n!)的例子
旅行商问题：从一个城市出发，经过所有城市后返回出发地，求最短的路径。

如果用朴素算法，第一个城市有n种选择，第二个有n-1种选择，依次类推，复杂度为O(n!)。
---
### 8、空间复杂度
空间复杂度指算法运行过程种临时所占用的内存大小，例如变量、数组等的开销，规则与时间复杂度一样。

在noi竞赛里，对于内存限制一般为128M（或256M），一般都足够使用。
---
## 数据范围分析
### 1、数据范围与算法复杂度
在noi竞赛环境，一般规定每个试题要在1秒内运行通过，而测评机每秒大概运行$10^7$~$10^8$次指令左右，因此对于给定的数据范围，与算法复杂度的对比关系大致如下：
---
| 数据范围     | 算法复杂度 |
| ------------ | ---------- |
| >10^7        | O(logn)    |
| 10^7         | O(n)       |
| 10^5 ~5*10^5 | O(nlogn)   |
| 1000 ~ 5000  | O(n^2)     |
| 200 ~ 500    | O(n^3)     |
| 20 ~ 24      | O(2^n)     |
| 12           | O(n!)      |
---
用上表做参考，可以用来：

在看到数据范围的时候，就知道大概需要选择什么算法了。
选择一个算法实现后，大概知道能通过多少测试点。
例如：一个排序的试题，30%数据<1000，50%数据<3000，100%数据<300000，则：

如果想AC(100分)，需要用O(nlogn)的算法，例如快速排序。
如果只会冒泡排序（O(n^2)），能拿到50分。

---

### 竞赛策略
#### 解题
仔细阅读试题，通过小数据模拟理解试题，大致明白试题的输入->输出之间的逻辑。

要求-在模拟、理解试题之后：

能提炼出试题对应的问题（去掉试题里的业务描述）
能自己生成更多的输入和输出样例。

---

#### 2.2 朴素算法
实现一种朴素算法，通过所有的样例，先不考虑性能。

要求：通过所有的测试样例，包括自己设计的样例，确保结果无误。

---

#### 2.3 优化和复杂度理解
根据数据的范围，分析出复杂度分级，并对朴素算法进行优化，大致划分出不同优化方案对应的复杂度分级，以及得分范围。

要求：

根据自己的能力积累，尽可能设计出更大得分范围的优化算法。
用所有测试样例对优化算法进行测试，确保结果无误。

---

### 2.4 分支和对拍
对拍是指用脚本来调用朴素算法和优化算法两个程序，对所有输入数据做运算，比较其输出是否一致。

对拍被用来确保优化程序不会出现结果错误的情况，因为优化程序往往用到比较复杂的思路，难免编码出错。

不会对拍的情况，也可以通过对不同的数据范围实现分支控制，比如小数据调用朴素算法，大数据调用对应的优化算法，各施其责。

---

#### 2.5 测试数据
为确保代码正确及性能测试通过，需要编写程序生成符合数据范围的各级测试数据，以便对优化算法进行性能测试，以及对拍所用。

---

## cin与scanf
### 1、cin与优化

C++一般使用cin输入，cout输出，如
```c
cin>>n; //读入整数到n
for(int i=1; i<=n; i++)
  cin>>a[i]; //读入n个整数的序列到a[]数组

cout<<n; //把变量n的值输出
```
但竞赛题如果n比较大，cin输入的速度比慢，测评就容易出现tle。

例如题目时间要求1秒，光读入数据就花了800毫秒，那剩下200毫秒不够运行。

可以用`ios::sync_with_stdio(false)` 来为cin、cout加速，这句话放到main函数的一开始。

---

### 2. scanf

如果输入数据量达到 $10^6$，就有必要使用scanf函数来输入。

```c++
#include <cstdio>
for(int i=1; i<=n; i++)
  scanf("%d", &a[i]);
```

---
3、printf
同样，如果有超过 $10^5$ 量级输出的，用cout也会慢，需要改成printf。
```c
for(int i=1; i<=n; i++) printf("%d ", a[i]);
```
---
## 对拍

对拍是一种进行检验或调试的方法，通过对比两个程序的输出来检验程序的正确性。可以将自己程序的输出与其他程序的输出进行对比，从而判断自己的程序是否正确。

对拍过程要多次进行，因此需要通过批处理的方法来实现对拍的自动化。

具体而言，对拍需要一个**数据生成器** 和**两个要进行输出结果比对的程序**。

每运行一次数据生成器都将生成的数据写入输入文件，通过重定向的方法使两个程序读入数据，并将输出写入指定文件，最后利用 Windows 下的 `fc` 命令比对文件（Linux 下为 `diff` 命令）来检验程序的正确性。如果发现程序出错，可以直接利用刚刚生成的数据进行调试。

---

## 对拍的步骤

1. 建立编写brust程序
2. 建立编写opt程序
3. 编写数据生成器程序
4. 编写对拍程序并运行此程序进行对拍

---

## brust程序（正确的程序或别人正确的程序)

644差分（模板）题目示例

```c++
/* created by chjshen, date: 2023-04-18 11:02 */
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1E5 + 5;
int n, m, a, b, s[N];
int l, r, t;
void handle()
{
    for (int i = l; i <= r; i++)
    {
        if (t == 0)
            s[i] -= b;
        else
            s[i] += a;
    }
}
void initInput(void)
{
    cin >> n >> m >> a >> b;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= m; i++)
    {
        cin >> l >> r >> t;
        handle();
    }
    for (int i = 1; i <= n; i++) cout << s[i] << " ";
    cout << endl;
}
int main(void)
{
    initInput();
    return 0;
}
```

---

## opt程序（优化后的程序或自己其他的程序）

644差分（模板）题目示例

```c++
/* created by chjshen, date: 2023-04-18 16:19 */
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1E5 + 5;
#define debug cout << "DEBUG" << endl
int n, m, a, b, s[N], d[N];
void handle(int l, int r, int c)
{
    if (c == 0)
        d[l] -= b, d[r + 1] += b;
    else
        d[l] += a, d[r + 1] -= a;
}
void show()
{
    for (int i = 1; i <= n; i++)
    {
        d[i] = d[i - 1] + d[i];
        cout << d[i] << " ";
    }
    cout << endl;
}
void initInput(void)
{
    cin >> n >> m >> a >> b;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        d[i] = s[i] - s[i - 1];
    }
    for (int i = 1; i <= m; i++)
    {
        int l, r, c;
        cin >> l >> r >> c;
        handle(l, r, c);
    }
}
int main(void)
{
    initInput();
    show();
    return 0;
}
```

---
## 数据生成器

- 最好是保证数据随机，可以生成大样例，但是在对拍时我们应该生成小样例数据，方便调试和查错。
- 如何生成随机数据：seed rand RAND_MAX ect..
示例程序：
```c++
 #include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
int n, m;
int main(int argc, char * argv[])
{
     int t = 10;
     if(argc > 1)
     {
         t = atoi(argv[1]);
     }
     srand(time(0) + t);
     n = rand() % 10 + 1; // 0 - RANDMAX
     m = rand() % 5 + 1;
     while(n <= m)
     {
         n = rand()% 10 +1;
     }
     cout << n << " " << m << endl;
     int a[11];
     for(int i = 1; i <= m; i++)
         a[i] = i;

for(int i = m + 1; i <= n; i++)
     {
         a[i] = rand() % m + 1;
     }

random_shuffle(a + 1, a + n + 1);
     for(int i = 1; i <= n; i++)
         cout << a[i] << " ";
     
     cout << endl;
     return 0;
}
 
```

---

## 对拍程序

- 程序化（脚本化）实现 数据生成器生成的随机 样例数据用a程序和了程序运行得结果a.out 和 b.out,自动对比是否相同。
 示例程序：
```c++
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

int main()
{
    // 1. 先编译3个文件 force.cpp, solve.cpp, data.cpp
    system("g++ force.cpp -o force");   
    system("g++ solve.cpp -o solve");   
    system("g++ data.cpp -o data");
    // 2. 生成输入文件 pai.in
    system("./data > pai.in");
    for(int i = 1; i <= 10000; i++)
    {
        // 1. 用force生成答案 pai.ans 
        system("force < pai.in > pai.ans");
        // 2. 生成pai.out
        system("solve < pai.in > pai.out");
        // 3. 比较两个生成的文件
        if(system("fc pai.ans pai.out >null"))
        {
            cout << i <<  ": WA!" << endl;
            break;
        }
        else
            cout << i << ": AC" << endl;
    }
    return 0;
}
```