CSP-S 2020 考前总结
比利♂海灵顿
2020-11-04 19:54:18
[TOC]
# CSP-S 2020
$2020$ 是我学习 OI 的第三年, $2018-2020$, 比赛从 $NOIp 2018$ 到 $CSP 2019$ 再到 $CSP 2020 \And NOIp 2020$
## Ⅰ Dev-C++
在 CSP 中, 提供的 IDE 环境为 Dev-C++, 每个 OIer 梦开始的地方, 但自从在 VSC 这条不归路上越走越远, 最初的 Dev 却变得陌生了.
由于平时主要用 VSC, 不常用 Dev-C++, 所以提前3天用 Dev-C++ 熟悉操作.
### 1. Exterior
由于 Dev-C++ 的外观实在有些不适应, 所以只能在考场现调, 提前自己配一个比较舒服的预设, 使用 Obsidian 配色, 当前行黑色高亮, 字体默认 Consolas, Windows7 还可能要配置 ClearType, 还有取消`使用Tab字符`选项, `Tab位置` 改为 $2$, `Astyle` 中也把 `缩进风格` 改为 `Spaces`, `Tab宽度` 改为 $2$.
### 2. Stack
为了测大样例, 需要将Windows系统的栈空间开至题目空间限制, 编译命令加入`-Wl,--stack=1024000000`表示将栈空间开至 $1GB$
### 3. Warning
对于能通过编译但可能不正确的地方, 肉眼不能及时发现, 可以打开更多编译警告, 在编译命令中加入`-Wall`, `-Wconversion`, `-Wextra`, 以开启更多警告
所以在编译选项中要打的所有命令为:
```
-Wl,--stack=1024000000 -Wall -Wconversion -Wextra
```
### 4. Debug
某些未配置好的 Dev-C++ 一调试就闪退, 对此, 在`编译器选项\代码生成/优化\连接器\产生调试信息`中将 `No` 改为 `Yes`.
### 5. Ctrl
由于 Dev-C++ 有一套不同于 VSC 的快捷键系统, 熟练后能大大提高做题效率.
可能用到的快捷键:
`F5` $\Rightarrow$ 调试
`F9` $\Rightarrow$ 编译
`F10` $\Rightarrow$ 运行
`F11` $\Rightarrow$ 编译运行
`F12` $\Rightarrow$ 全部编译
调试时 + `A` $\Rightarrow$ 添加查看
`Ctrl` + `Shift` + `A` $\Rightarrow$ Astyle 格式化
`Ctrl` + `/` + 选定 $\Rightarrow$ 多行注释
`Ctrl` + `M` $\Rightarrow$ 视图分栏
`Ctrl` + `N` $\Rightarrow$ 新建
`Ctrl` + `S` $\Rightarrow$ 保存
`Ctrl` + `Shift` + `S` $\Rightarrow$ 全部保存
### 6. Auto Save
记得存盘, 由于一个题可能在由暴力到正解的过程中经历几个版本的迭代, 当一个算法锅了, 要退回之前的算法就会增加很多工作量, 所以利用 DEV-C++ 自动保存功能, 每隔 $5min$ 保存一份副本(附加格式化时间戳), 这样就能随时查看历史版本.
### 7. Others
1. 结构体/类中的元素自动补全出了问题, 重写变量名就能解决.
2. `Program received signal SIGSEGV`这是调试时 Dev-C++ 报 RE 的弹窗, 这时就要看看哪个数组或指针越界了.
3. `[Error] ld returned 1 exit status` 大部分情况是程序没关, 但是第二种情况比较恶心, 是某些编译器玄学原因(应该时因为我本地有~~一万~~多个编译器, 考场上只有 Dev, 应该不会出这个问题), 关了重开就好了, 或者是随便改改代码就好了.**注意`main()`不要打成`mian()`**
## Ⅱ 试机
这次的试机在正式考试之前, 所以打的代码可以用到考试中, 那么在考试开始前打出一些可能用得到的代码就成了明智之举.
一共有 $20 - 30 min$, 这个时间长度还是十分可观的, 要提前写的代码一定是最有可能有用的优先.
### 1. 头文件
在 CSP 中, 头文件打的越多越好 (卡评测机的非法头文件除外), 所以要提前全头文件哪怕只是写 IO 优化.
另外, `<ctime>`库中和时间有关的函数都会影响后期申诉, 所以不在要提交的答案代码中写
可能用到的头文件
```cpp
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
```
### 2. IO 优化
#### ① 快读
快读基本上用到的概率为 $100\%$, 所以在这段时间是一开始就要打的.
```cpp
inline int RD() {
int Itmp(0), Isig(1);
char Ichr(getchar());
while ((Ichr != '-') && ((Ichr > '9') || (Ichr < '0'))) {
Ichr = getchar();
}
if (Ichr == '-') {
Isig = -1;
Ichr = getchar();
}
while ((Ichr >= '0') && (Ichr <= '9')) {
Itmp = Itmp * 10 + Ichr - '0';
Ichr = getchar();
}
return Itmp * Isig;
}
```
#### ② 快写
但是由于输出优化常数较读入优化大, 所以和 `printf()` 相比优势不大, 又存在一些问题 (如: 不能输出大部分末位 $\geq 4$ 的 $10$ 位数, 不能输出某些末位 $\geq 2$ 的 $20$ 位数, 也就是说不能将在当前数据类型范围内的数全部正确输出).
我虽然也试着写了一个, 但是对拍出了刚刚提到的问题. 又有风险, 又不能提升很多效率, 又浪费时间, 所以不决定提前写快写
```cpp
inline void PR(long long Prtmp, bool SoE) {
unsigned long long Prstk(0), Prlen(0);
if (Prtmp < 0) {
putchar('-');
Prtmp = -Prtmp;
}
do {
Prstk = Prstk * 10 + Prtmp % 10;
Prtmp /= 10;
++Prlen;
} while (Prtmp);
//printf("%d", Prtmp);
do {
putchar(Prstk % 10 + '0');
Prstk /= 10;
--Prlen;
} while (Prlen);
if (SoE) {
putchar('\n');
} else {
putchar(' ');
}
return;
}
```
### 3. 对拍
如果一道题过了大样例, 那么这个题基本上就是过了, 即使不满分也不会因答案错误出问题, 但是为了防止毒瘤出题人给一个非常弱的大样例, 对拍还是很有必要的.
在这段时间里, 可以提前打出框架, 到时候根据题目修改即可.(可以借此机会测试快读正确性和效率)
#### ① 数据生成器
对拍的基础, 生成随机数据给暴力和优化后的代码.
向 `main()` 传入参数以保证一秒内的多组数据种子不同.
但是显然这样的操作我是打不出来的, 不过如果忘了这种打法也无妨
```cpp
int n(1000000);
char k[10001];
int main(int argc,char** argv) {
unsigned long long s;
if(argc>=1) {
sscanf(argv[1],"%llu",&s);
printf("%llu\n",s);
} else {
printf("sto");
s=1;
}
freopen("IO.in", "w", stdout);
srand(time(0)*s);//Seeds
for (register int i(1); i<=n; ++i) {
printf("%d\n", (long long)(rand() - rand()) * (rand() - rand()));
}
return 0;
}
```
#### ② 对拍器
大部分人用批处理, 但是由于我比较菜, 所以用更加熟悉的 C++ 写.
利用`<ctime>`中的`clock()`分别计算优化和暴力的效率, 对于优化效果有把握.
向 `main()` 传入参数以保证一秒内的多组数据种子不同. $*2$
```cpp
long long Ti;
char k[100001];
int main() {
for (unsigned long long i=1;; i++) {
sprintf(k,"BD.exe %llu",i);
system(k);//Seeds
Ti = clock();
system("T.exe");
printf("T_Time = %lld\n", clock() - Ti);
Ti = clock();
system("Tfc.exe");
printf("Tfc_Time = %lld\n", clock() - Ti);
if(system("fc IO.out IOfc.out")) {
printf("Error!");
MessageBox(NULL,"error!!!!!","tql",MB_YESNO);//MB
break;
}
else {
printf("AC %d\n");
}
}
return 0;
}
```
#### ③ 暴力 $\And$ 优化
编译自己一开始的暴力和新打出的代码, 注意写好`freopen()`接口
### 4. 图
一般这 $4$ 道题怎么样都得有一道和图有关的, 所以接下来就可以把邻接表存图打出来备用. 支持图的存储, 遍历.
#### ① Node $\And$ Edge
```cpp
struct Edge;
struct Node {
Edge *Fst;
int DFSr;
}N[10005];
struct Edge {
Node *To;
Edge *Nxt;
}E[10005], *cnte(E);
```
#### ② Lnk()
```cpp
void Lnk(const int &x, const int &y) {
(++cnte)->To = N + y;
cnte->Nxt = N[x].Fst;
N[x].Fst = cnte;
return;
}
```
#### ③ DFS()
```cpp
void DFS(Node *x) {
//printf("To %d %d\n", x - N, Dcnt);
x->DFSr = ++Dcnt;
Edge *Sid(x->Fst);
while (Sid) {
if(!Sid->To->DFSr) {
DFS(Sid->To);
}
Sid = Sid->Nxt;
}
return;
}
```
### 5. 数组清除器
在多组数据的题目中, 通常会需要清空数组的操作, 数组清不干净, 危险又难以察觉, 将变量开在一起, 然后紧接着写一个清除函数 `Clr()`
以 Tarjan缩点 + 拓扑序 的 `Clr()` 为例
```cpp
void Clr () {
memset(N, 0, sizeof(N));
memset(E, 0, sizeof(E));
memset(N_, 0, sizeof(N_));
memset(E_, 0, sizeof(E_));
memset(Stk, 0, sizeof(Stk));
memset(Stk_, 0, sizeof(Stk_));
cnte = E;
cnte_ = E_;
Dcnt = 0;
Dcnt_ = 0;
Scnt = 0;
Hd = 0;
Hd_ = 0;
return;
}
```
## Ⅲ 复习
一些算法和数据结构已经好长时间没打了, 考场现打会消耗很多时间调试甚至直接打不出来, 所以考前要把可能会考的板子打一遍
### 1. 数据结构
#### ① 并查集
用来维护集合中元素的关系, 支持 $O(log_2n)$ 加入 $O(log_2n)$ 查询在哪个集合中
但是有时候可能被卡到 $O(n)$, 于是有了一种技巧: 路径压缩
路径压缩后, 并查集支持 $真 \bullet O(log_2n)$ 插入, $真 \bullet O(log_2n)$ 查询.
查询
```cpp
int Fnd(const int &x) {
int x_tmp(x);
while (x_tmp!=Fthr[x_tmp]){
x_tmp = Fthr[x_tmp];
}
Fthr[x] = x_tmp;//路径压缩
return x_tmp;
}
```
插入
```cpp
void Add(const int &x, const int &y) {
Fthr[Fnd(x)] = Fthr[y];
return;
}
```
#### ② St 表
**St 表好在快**
$O(n)$ 预处理, $O(1)$ 查询, 能在 $10^5$ 的数据中跑 $10^7$ 的查询.
**St 表好在简**
$10min$ 打出, $10min$ 调好的简单数据结构.
**St 表好在整**
St 表可以存储查询部分重合的两个区间合并不影响答案的数据, (如最值, gcd, 或运算和等)
**St 表坏在不变**
不支持修改
预处理
```cpp
for (register int i(1); i <= n; ++i) {
St[0][i] = RD();
}
Log2[1] = 0;
for (register int i(2); i <= n; ++i) {
Log2[i] = Log2[i - 1];
if(i >= 1 << (Log2[i - 1] + 1)) {
++Log2[i];
}
}
```
建表
```cpp
void Bld() {
for (register int i(1); i <= Log2[n]; ++i) {
for (register int j(1); j + (1 << i) <= n + 1; ++j) {
St[i][j] = max(St[i - 1][j], St[i - 1][j + (1 << (i - 1))]);
//printf("%d %d %d\n", i, j, St[i][j]);
}
}
return;
}
```
查询
```cpp
int Fnd () {
int len = Log2[B - A + 1];
return max(St[len][A], St[len][B - (1 << len) + 1]);
}
```
#### ③ 线段树
非常实用的数据结构, 可以维护所有可以将两个区间合并的区间信息(如和, 积, 最值等), 支持区间/单点修改($O(log_2n)$), 区间/单点查询($O(log_2n)$), 能处理 $10^6$ 的数据.
考前再打加调试也是花了近 $1h$, 但是出锅较少, 而且还是忘了开`long long`, 唯一的锅是在区间修改时忘记下传标记, 所以十分庆幸在有大样例的场下发现了这个细节, 否则场上可能根本没法发现.
存储
```cpp
struct Node {
Node *Ls, *Rs;
long long Val, Tag, L, R;
} N[200005], *cntn(N);
long long a[100005];
int A, B, C, n, m, k, DWt;
void Clr () {}
```
上/下传
```cpp
void Udt(Node *x) {
if(x->L == x->R) {
return;
}
x->Val = x->Ls->Val + x->Rs->Val;
return;
}
void Dld(Node *x) {
if(!(x->Tag)) {
return;
}
if(!(x->L == x->R)) {
x->Ls->Tag += x->Tag;
x->Rs->Tag += x->Tag;
x->Ls->Val += x->Tag * (x->Ls->R - x->Ls->L + 1);
x->Rs->Val += x->Tag * (x->Rs->R - x->Rs->L + 1);
}
x->Tag = 0;
return;
}
```
区间修改(修改的区间和加数是全局变量, 所以不传入函数, 查询同)
```cpp
void Chg(Node *x) {
if(OtRg(x)) {
return;
}
if(InRg(x)) {
x->Tag += C;
x->Val += C * (x->R - x->L + 1);
return;
}
Dld(x);//就是这句忘写了qaq
Chg(x->Ls);
Chg(x->Rs);
Udt(x);
return;
}
```
区间查询
```cpp
long long Fnd(Node *x) {//不开 long long 见祖宗
if(OtRg(x)) {
return 0;
}
if(InRg(x)) {
return x->Val;
}
Dld(x);
long long tmp (Fnd(x->Ls));
return tmp + (Fnd(x->Rs));
}
```
#### ④ 树状数组
### 2. DP
动态规划的特点就是方程巨长, 代码单一, 不好调. 但是应用范围广, 暴力容易想, 所以说得 DP 者得省一.
#### ① 背包
背包是一种最简单的 DP, 但是一旦有问题, 就不容易发现, 就像这道题, 本来十分钟打出来, 结果调了 $2H$, 最后竟然是题读错了.
```cpp
struct Stf {
int Val, Wei, num;
int Lw1V, Lw1W, Lw2V, Lw2W;
} S[65];
int n, m, A, B, C, f[40005], cntn(0), ans(0), tmp;
int Gt(const int &x) {//没调好的原因
for (register int i(1); i <= cntn; ++i) {
if(S[i].num == x){
return i;
}
}
}
int main() {
Clr();
n = RD();
m = RD();
for (register int i(1); i <= m; ++i) {
A = RD();
B = RD();
B *= A;
C = RD();
if(C == 0) {
S[++cntn].Val = B;
S[cntn].Wei = A;
S[cntn].num = i;
} else {
tmp = Gt(C);
if(S[tmp].Lw1W) {
S[tmp].Lw2V = B;
S[tmp].Lw2W = A;
} else {
S[tmp].Lw1V = B;
S[tmp].Lw1W = A;
}
}
}
for (register int i(1); i <= cntn; ++i) {
for (register int j(0); j <= n - S[i].Wei; ++j) {
f[j] = max(f[j], f[j + S[i].Wei] + S[i].Val);
if(j + S[i].Wei + S[i].Lw1W <= n && S[i].Lw1V) {
f[j] = max(f[j], f[j + S[i].Wei + S[i].Lw1W] + S[i].Val + S[i].Lw1V);
}
if(j + S[i].Wei + S[i].Lw2W <= n && S[i].Lw2V) {
f[j] = max(f[j], f[j + S[i].Wei + S[i].Lw2W] + S[i].Val + S[i].Lw2V);
}
if(j + S[i].Wei + S[i].Lw1W + S[i].Lw2W <= n && S[i].Lw1V && S[i].Lw2V) {
f[j] = max(f[j], f[j + S[i].Wei + S[i].Lw1W + S[i].Lw2W] + S[i].Val + S[i].Lw1V + S[i].Lw2V);
}
}
}
printf("%d\n", f[0]);
return 0;
}
```
#### ② LIS & LDS
#### ③ 区间DP
### 3. 图论
#### ① Kruskal
最简单的图论算法, 用来求无向连通图的最小 (瓶颈) 生成树. 最初每个节点各自为一个生成树, 通过并查集合并已有的 $n$ 个生成树为 $1$ 个.
存储(邻接矩阵)
```cpp
int n, m, A, B, C, Ecnt, Fthr[305];
struct Edge {
int Val, To_1, To_2;
bool operator <(const Edge &x) const {
return this->Val < x.Val;
}
} E[100005],*cnte, *a[305][305];
```
并查集(路径压缩)
```cpp
int Fnd(const int &x) {
int x_tmp(x);
while (x_tmp!=Fthr[x_tmp]){
x_tmp = Fthr[x_tmp];
}
Fthr[x] = x_tmp;
return x_tmp;
}
void Add(Edge *x) {
Fthr[Fnd(x->To_1)] = Fthr[x->To_2];
return;
}
```
预处理(以邻接矩阵为索引, 防止重边)
```cpp
for (register int i(1); i <= m; ++i) {
A = RD();
B = RD();
C = RD();
if(a[A][B]) {
if(a[A][B]->Val > C) {
a[A][B]->Val = C;
}
continue;
}
(++cnte)->To_1 = A;
cnte->To_2 = B;
cnte->Val = C;
a[A][B] = cnte;
a[B][A] = cnte;
}
```
排序(保证当前边为最小游离边)
```cpp
sort(E + 1, cnte + 1);
for (register int i(1); i <= n; ++i) {
Fthr[i] = i;
}
```
算法本体(外边则加, 内边则跳)
```cpp
void Kruskal(Edge *x) {
if(Fnd(x->To_1)==Fnd(x->To_2)) {
return;
}
Add(x);
++Ecnt;
return;
}
//In 'main()'
for (register Edge *i(E + 1); i <= cnte; ++i) {
Kruskal(i);
if(Ecnt == n - 1) {return 0;}
}
```
#### ② Dijkstra
本以为 $10min$ 随便打的算法, 结果交了一面, 着实不是太体面, 最后还是在苏巨神的指导下 AC.
不要忘记标记最短路已经被确定的点, 否则会超时.
```cpp
void Dijkstra() {
q.push(make_pair(-N[s].Dst, s));
Node *now;
while (!q.empty()) {
now = N + q.top().second;
q.pop();
if(now->InStk) {
continue;
}
now->InStk = 1;//就是这里没判
for (Edge *Sid(now->Fst); Sid; Sid = Sid->Nxt) {
if (Sid->To->Dst < now->Dst + Sid->Val)
if (!Sid->To->InStk) {//还有这
Sid->To->Dst = now->Dst + Sid->Val;
q.push(make_pair(Sid->To->Dst, Sid->To - N));
}
}
}
return;
}
```
#### ③ Tarjan
断断续续写了一个小时, 发现的问题主要有: 注意栈的操作, 不要忘了弹栈最后把强连通分量根节点弹掉, 不要忘记进栈.
最后缩点时, 由于要再建一张图, 所以变量名和结构体比较错乱.
而且在建新图的时候, 不要在一个强连通分量内部连边, 否则就会导致新点入度错误.
存储
```cpp
struct Edge;
struct Edge_;
struct Node N[10005], *Stk[10005];
struct Node_ N_[10005], *Stk_[10005];
struct Edge E[10005], *cnte(E);
struct Edge_ E_[10005], *cnte_(E_);
int n, A, Dcnt(0), Dcnt_(0), Scnt(0), Hd(0), Hd_(0);
void Clr () {}
void Lnk(const int &x, const int &y) {}
void Lnk_(const int &x, const int &y) {
++N_[y].IDg;
(++cnte_)->To = N_ + y;
cnte_->Nxt = N_[x].Fst;
N_[x].Fst = cnte_;
return;
}
```
Tarjan(DFS)
```cpp
void Tarjan(Node *x) {
printf("To %d %d\n", x - N, Dcnt);
if (!x->DFSr) {
x->DFSr = ++Dcnt;
x->BkT = x->DFSr;
x->InStk = 1;
Stk[++Hd] = x;
}
Edge *Sid(x->Fst);
while (Sid) {
if (Sid->To->BlT) {
Sid = Sid->Nxt;
continue;
}
if (Sid->To->InStk) {
x->BkT = min(x->BkT, Sid->To->DFSr);
} else {
Tarjan(Sid->To);
x-> BkT = min(x->BkT, Sid->To->BkT);
}
Sid = Sid->Nxt;
}
if(x->BkT == x->DFSr) {
++Scnt;
while (Stk[Hd] != x) {
Stk[Hd]->BlT = Scnt;
Stk[Hd]->InStk = 0;
--Hd;
}
Stk[Hd]->BlT = Scnt;
Stk[Hd--]->InStk = 0;
}
return;
}
```
缩点(新图)
```cpp
void ToPnt(Node *x) {
//printf("To %d %d\n", x - N, Dcnt);
Edge *Sid(x->Fst);
while (Sid) {
if(x->BlT != Sid->To->BlT) {
Lnk_(x->BlT, Sid->To->BlT);
}
Sid = Sid->Nxt;
}
return;
}
```
#### ④ 拓扑序
由于 Tarjan 缩点后是个 DAG (有向无环图) 所以正好可以用来测试拓扑序.
在删点的时候, BFS 所用的队列
(接Tatjan)
排序
```cpp
void TPR() {
for(register int i(1); i <= Scnt; ++i) {
if (N_[i].IDg == 0) {
Stk_[++Hd_] = &N_[i];
}
}
while (N_[++Hd_].IDg == 0) {
Stk_[Hd_] = &N_[Hd_];
}
--Hd_;
while (Hd_) {
Stk_[Hd_]->Tpr = ++Dcnt_;
Edge_ *Sid(Stk_[Hd_--]->Fst);
while (Sid) {
if(!Sid->To->Tpr) {
--(Sid->To->IDg);
if(Sid->To->IDg == 0) {
Stk_[++Hd_] = Sid->To;
}
}
Sid = Sid->Nxt;
}
}
return;
}
```
新图遍历
```cpp
void DFS_(Node_ *x) {
x->_ed = 1;
printf("To %d %d\n", x - N_, x->Tpr);
Edge_ *Sid(x->Fst);
while (Sid) {
if(!Sid->To->_ed) {
DFS_(Sid->To);
}
Sid = Sid->Nxt;
}
return;
}
```
### 4. 数学
#### ① Euclid
最基本的数学算法, 用来 $O(log_2n)$ 求两个数的 `GCD` (最大公因数).
```cpp
int Gcd(int x, int y) {
if(y == 0) {
return x;
}
return Gcd(y, x % y);
}
```
#### ② 快速幂(Fibonacci)
#### ③ Merge
#### ④ Exgcd
#### ⑤ 高精度运算
### 5. Stl
Stl 的语法大同小异, 但是如果忘记可是很难调的.
一些 Stl 需要传入数组里操作位置的头尾指针, 遵循左闭右开的规则, 如 `(A + 1, A + 3)` 表示的是 $A[1]$ 到 $A[2]$ 范围.
#### ① sort
`sort(A + 1, A + n + 1)`
表示将 $A$ 数组从 $A[1]$ 到 $A[n]$ 升序排序.
其他规则可通过重载结构体的 $<$ 或比较函数 `Cmp()` 来定义.
#### ② priority_queue
`priority_queue <int> q`
定义一个元素为 `int` 的默认优先队列 (二叉堆)
`q.push(x)`
$O(log_2n)$ 插入元素 $x$
`q.pop()`
$O(log_2n)$ 弹出堆顶
`q.top()`
$O(1)$ 查找堆顶, 返回值为队列元素类型
默认容器为对应数据类型的 `<vector>`, 一般不需要修改, 也可以通过重载 $<$ 或比较函数来定义规则
#### ③ lower/upper_bound
`lower_bound(A + 1, A + n + 1, x)` 查找有序数组 $A$ 中从 $A[1]$ 到 $A[n]$ 范围内最小的大于等于 $x$ 的数的迭代器.
`upper_bound()` 同理, 只是大于等于变成了严格大于, 其他用法都相同
值得一提的是, 如果整个左闭右开区间内都没有找到合法的元素, 那么返回值将会是传入区间的右端点, 而右端点又恰恰不会被查询区间包含, 这样如果找不到, 它的返回值将不会和任意一个合法结果产生歧义.
也可以用一般方法定义比较规则.
## Ⅳ 策略
### 1. 得分目标
目标是省一, 也就是说要在山东省得前 $200$ 名.
以之前模拟赛的时间和难度来看, 一般 T1 签到题大部分情况都能签到成功. T2 会花较长时间得到一半以上的分数, T3 除了极少数情况以外, 基本 AC 不了. 更不用说T4了, 能得分就已经赚了.
总结就是: ~~切一, 解二, 暴三, 骗四~~ (不要再玩这个梗了)
期望得分 $100~200$ (我菜得深沉)
### 2. 时间管理
之前几次模拟赛, T2 是第二难的甚至是最难的 (毒瘤出题人按字典序排序题目), 导致花大量时间做 T2 却做不出来, 最后陪了夫人又折兵. 但是 CSP 一般就是按难度排序, 所以不存在这个问题.
今年考试时间是 $14:30 - 18:30$, 由于加上了试机打的代码, 所以时间相对校内模拟赛充裕一些, 留下了对拍的时间.
一份代码要先保证正确再追求效率, 所以在一时想不出正解时, 先打一个部分分的暴力, 这样既能通过对拍验证优化的正确性, 又能减小正解的难度, 毕竟在已有的算法上做优化比凭空写要简单 (某些类型的题如 DP, 正解就是从暴力一点点优化来的)
一共 $4h$, $240min$, 一开始在 $45min$ 之内, 完成 T1 读, 切, 写, 调, 拍的工作.
接下来先读完所有题, 然后做 T2, 在还剩下 $2H$ 的时间, 如果 AC 遥遥无期, 先放下 T2 去做 T3, T4, 等把 T3, T4, 能得的分得了, 再去做T2.
这时, 有了 T1 的正解和三个题的部分分, 就会塌实很多.
### 3. 代码管理(空间管理)
所有自己写的, 生成的文件放在`D`盘, 个人文件夹名称格式为`考号+姓名`, 如`SD-20117曹翠芬`(~~€€￡~~)
由于关于一道题的所有文件都在它的文件夹中,
今年要求个人文件夹中只留四个题目对应的子文件夹, 每个子文件夹中只放提交的`.cpp`文件, 所以最后要清空文件夹.
## Ⅴ 杂项
### 1. 部分拼写
1. `#include`
2. `priority_queue`
3. `<algorithm>`
4. `operator`
5. `conversion`
6. `register`
7. `freopen`
8. `vector`
9. `unsigned`
### 2. 模拟赛出锅汇总
> "不开long long见祖宗"
> "不清数组见祖宗"
> "乱改代码见祖宗"(但是这次就是自动保存历史版本让我快速找回正解)
> "不读题见祖宗"
### 3. 考场大坑
#### ① `<cstdio>`
由于要写 `freopen()`, 所以 `<cstdio>` 是必然要写的, 但是 Windows 本地不写也能过编译, 所以是无形威胁, 最为致命.
#### ② 敏感变量名
主要出现在开 C++11 的情况, 但是我不会写小写英文单词作为变量名, 所以基本上撞不上这种坑.
#### ③ 数组开爆
在线题库评测时, 只会计算当前程序用到的内存, 但是在 CSP 中, 会计算所有定义的变量的空间, 所以一定要计算好空间, 即使最后几十分不要了也不能冒险.
#### ④ `freopen()`
这便不必多说了, 虽然没有因为这个挂过, 但是后果之严重不容忽视.
#### ⑤ `time(0)`
随机数种子还是用自己的生日等固定数字吧, 凡是和时间有关的操作, 都会影响后期申诉.
## Ⅵ 结语
```cpp
CSP-S 2020->RP += 0x3f3f3f3f
```
安得广厦千万间, 大庇天下 OIer 俱欢颜
希望每天~~朝五晚九~~朝五晚B($B_{16} == 11_{10}$)的我们身体健康
<p align="right">2020.11.6</p>
$$
\mathfrak{Wild\ Donkey}
$$