CSP-S 2020 考前总结

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, 以开启更多警告

所以在编译选项中要打的所有命令为:

1	-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

结构体/类中的元素自动补全出了问题, 重写变量名就能解决.
Program received signal SIGSEGV这是调试时 Dev-C++ 报 RE 的弹窗, 这时就要看看哪个数组或指针越界了.
[Error] ld returned 1 exit status 大部分情况是程序没关, 但是第二种情况比较恶心, 是某些编译器玄学原因(应该时因为我本地有一万多个编译器, 考场上只有 Dev, 应该不会出这个问题), 关了重开就好了, 或者是随便改改代码就好了.注意main()不要打成mian()

Ⅱ 试机

这次的试机在正式考试之前, 所以打的代码可以用到考试中, 那么在考试开始前打出一些可能用得到的代码就成了明智之举.

一共有 $20 - 30 min$ , 这个时间长度还是十分可观的, 要提前写的代码一定是最有可能有用的优先.

1. 头文件

在 CSP 中, 头文件打的越多越好 (卡评测机的非法头文件除外), 所以要提前全头文件哪怕只是写 IO 优化.

另外, <ctime>库中和时间有关的函数都会影响后期申诉, 所以不在要提交的答案代码中写

可能用到的头文件

#include <algorithm>
#include <cmath> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

2. IO 优化

① 快读

快读基本上用到的概率为 $100\%$ , 所以在这段时间是一开始就要打的.

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$ 位数, 也就是说不能将在当前数据类型范围内的数全部正确输出).

我虽然也试着写了一个, 但是对拍出了刚刚提到的问题. 又有风险, 又不能提升很多效率, 又浪费时间, 所以不决定提前写快写

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() 传入参数以保证一秒内的多组数据种子不同.

但是显然这样的操作我是打不出来的, 不过如果忘了这种打法也无妨

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$

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

struct Edge;
struct Node {
  Edge *Fst;
  int DFSr;
}N[10005];
struct Edge {
  Node *To;
  Edge *Nxt;
}E[10005], *cnte(E);

② Lnk()

void Lnk(const int &x, const int &y) {
  (++cnte)->To = N + y;
  cnte->Nxt = N[x].Fst;
  N[x].Fst = cnte;
  return;
}

③ DFS()

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() 为例

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)$ 查询.

查询

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(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 表坏在不变

不支持修改

预处理

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];
  }
}

建表

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;
}

查询

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, 唯一的锅是在区间修改时忘记下传标记, 所以十分庆幸在有大样例的场下发现了这个细节, 否则场上可能根本没法发现.

存储

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 () {}

上/下传

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;
}

区间修改(修改的区间和加数是全局变量, 所以不传入函数, 查询同)

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;
}

区间查询

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$ , 最后竟然是题读错了.

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$ 个.

存储(邻接矩阵)

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];

并查集(路径压缩)

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;
}

预处理(以邻接矩阵为索引, 防止重边)

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;
}

排序(保证当前边为最小游离边)

sort(E + 1, cnte + 1);
for (register int i(1); i <= n; ++i) {
  Fthr[i] = i;
}

算法本体(外边则加, 内边则跳)

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.

不要忘记标记最短路已经被确定的点, 否则会超时.

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

断断续续写了一个小时, 发现的问题主要有: 注意栈的操作, 不要忘了弹栈最后把强连通分量根节点弹掉, 不要忘记进栈.

最后缩点时, 由于要再建一张图, 所以变量名和结构体比较错乱.

而且在建新图的时候, 不要在一个强连通分量内部连边, 否则就会导致新点入度错误.

存储

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)

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;
}

缩点(新图)

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)

排序

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;
}

新图遍历

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 (最大公因数).

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. 部分拼写

#include
priority_queue
<algorithm>
operator
conversion
register
freopen
vector
unsigned

2. 模拟赛出锅汇总

“不开long long见祖宗”

“不清数组见祖宗”

“乱改代码见祖宗”(但是这次就是自动保存历史版本让我快速找回正解)

“不读题见祖宗”

3. 考场大坑

① `<cstdio>`

由于要写 freopen(), 所以 <cstdio> 是必然要写的, 但是 Windows 本地不写也能过编译, 所以是无形威胁, 最为致命.

② 敏感变量名

主要出现在开 C++11 的情况, 但是我不会写小写英文单词作为变量名, 所以基本上撞不上这种坑.

③ 数组开爆

在线题库评测时, 只会计算当前程序用到的内存, 但是在 CSP 中, 会计算所有定义的变量的空间, 所以一定要计算好空间, 即使最后几十分不要了也不能冒险.

④ `freopen()`

这便不必多说了, 虽然没有因为这个挂过, 但是后果之严重不容忽视.

⑤ `time(0)`

随机数种子还是用自己的生日等固定数字吧, 凡是和时间有关的操作, 都会影响后期申诉.

Ⅵ 结语

1	CSP-S 2020->RP += 0x3f3f3f3f

安得广厦千万间, 大庇天下 OIer 俱欢颜

希望每天~~朝五晚九~~朝五晚B( $B_{16} == 11_{10}$ )的我们身体健康

2020.11.6

\mathfrak{Wild\ Donkey}