目录

  1. 引言
  2. 前言
  3. 语法类
    1. 数据范围
    2. 基本语句
      1. 循环语句
      2. 条件语句
      3. 分支语句
    3. 宏定义
    4. 排序相关
    5. STL
      1. set
      2. map
      3. priority_queue
      4. lower_bound/upper_bound
    6. 结构体
      1. 构造函数
      2. 初始化
  4. 算法类
    1. 前缀和/积
    2. 快速幂
    3. 动态规划(DP)
    4. 图论
    5. 数据结构
      1. 树链剖分
      2. Link-Cut-Tree
      3. 字典树(Trie)
      4. 线段树
      5. 可持久化线段树/主席树

引言

妙妙妙妙不可言<( ̄︶ ̄)/

前言

大概就是许多常见错误的汇总,每次考试前仔细的看一看,认真地记一记,应该会有很大的好处

注意,下面的每个错误都很重要,时间允许的话一定要一字一字地看!

语法类

数据范围

  • 随时都要注意是否应该使用更大的数据类型以防止溢出,这一点至关重要

    • 常见的需要用到long long int的地方
      • 算术表达式里面的计算中间结果
      • 与取模有关的几乎所有题目
      • 对程序计算答案的累计(即最终结果)
      • 对于满足条件的n元组个数的统计
      • 组合数学相关题目
      • 一些数据范围很大的数论题以及需要用到杜教筛的数论题
      • 总之每次都仔细的判断一下,程序完成后特别考虑一下这个问题,应该就没问题了
  • 随时都要注意是否由于使用了较大的数据类型导致内存超限

  • 注意输入输出是否使用了正确的类型表标识符

基本语句

循环语句

  • 注意内外层循环变量的冲突
  • 注意内部语句循环变量的正确使用
  • 注意循环变量与全局变量(循环外部变量)的冲突

条件语句

  • 注意if…else的对应性,不要把内层的if对应到外层的else上,为避免这一错误可多使用’{}’
  • 注意运算符的优先级

分支语句

  • 保险起见,在每个分支后面加上break;

宏定义

  • 严重问题:注意宏定义的不安全性,代码示例如下:

我们想计算$(a + b) * c$

1
2
3
4
5
6
7
8
#include <cstdio>
#define A a + b
int main(){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
printf("%d", A * c);
return 0;
}

但这样做的结果是$a + b * c$
要想得到正确结果,多使用’()’:

1
2
3
4
5
6
7
8
#include <cstdio>
#define A (a + b)
int main(){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
printf("%d", A * c);
return 0;
}

排序相关

  • 严重问题:绝对不要使比较方法出现循环比较现象,必须保证排序结果唯一

    ,相关链接:BZOJ 3712: [PA2014]Fiolki

  • 在priority_queue的自定义比较用结构体中,注意运算符()的比较方法是:(a, b)在a的优先级小于b时返回True

    ,即相当于重载大于运算符

STL

  • 尽可能避免在任何STL中存放比较方法定义与外部数组存在关联的元素,否则会导致排序紊乱产生错误

set

  • 严重问题:绝对不要使用STL的二分查找功能来查找set中的元素,只能使用set自带的二分查找成员函数,否则会导致严重的TLE问题

map

  • 不要在未对要访问的map键值赋值的情况下访问它,否则会RE

priority_queue

  • 注意cmp的定义方法:当$a$比$b$优先级小的时候返回true
1
2
3
4
5
6
struct cmp{
bool operator () (int a, int b){
return a < b;
}
};
priority_queue<int, vector<int>, cmp> p;

$p$是一个大根堆

lower_bound/upper_bound

  • 严重问题:绝对不要使用这两个函数来查找set中的元素,只能使用set自带的二分查找成员函数,否则会导致严重的TLE问题,本处再强调一遍

  • 注意这两个二分查找函数只能作用于一个有序数组,即已经排好序的数组,而不能是任意数组(二分算法本身也要求有序...)

结构体

构造函数

  • 注意构造函数前面简化赋值语句的正确使用方法,相关链接:BZOJ 4502: 串

初始化

  • 即使是定义在全局的结构体,内部变量初始时也不一定都为$0$,需要在构造函数中手动初始化

算法类

前缀和/积

  • 不要使最开头累加/乘的操作访问不该访问的内存
  • 如果是求前缀积,一定不要忘记第一个元素应该手动设为$1$

快速幂

  • 注意不要忘记每次对幂数进行的右移操作,否则会TLE(当然,这个本地也是很容易测试出来的,但可能会不知道问题出在哪里)
  • 严重问题:注意绝对不要使幂数为一个负数,如果容易出现此错误,最好提前判断一下
  • 在取模的题目中,不要忘记每次乘法都是需要取模的

动态规划(DP)

  • 在边界值问题上要特别注意,边界值需要经过计算与论证方可确定

  • 注意情况讨论的不充分或是相互重叠的问题

  • 在取模的问题中时刻记住对结果及时进行取模处理

  • 严重问题:在记忆化搜索时,时刻记住在跳出当前计算层之前把vis数组设置为$true$,否则会导致严重的TLE问题
  • DP的状态转移不能存在环,否则需要使用最短路式更新法

  • 注意:在题目卡常时,要将递归形式的DP改造为迭代形式,以大幅提高运行速度

图论

  • 注意有些时候边与点数目的差异会很大,不要直接对存储点与边的数组直接使用相同大小的宏定义进行声明

数据结构

树链剖分

  • 注意题目的要求,仔细严谨地设置链上操作方法,相关链接:BZOJ 3319: 黑白树

字典树(Trie)

  • 严重问题:时刻注意Trie的空间占用大小并非$O(n)$而是$O(n\log n)$,要计算后声明足够的内存空间,同时防止内存超过限制

线段树

  • 严重问题:注意不要让查询的区间为不合法区间,否则会RE,这种错误往往比较隐蔽,所以可能出现此情况时最好提前判断一下
  • 注意线段树的基本架构不要写错:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void Operate (int l, int r, int o){
    //pushdown(l, r, o);
    if (qx <= l && r <= qy){
    //do something
    return;
    }
    int mid = ((r - l) >> 1) + l;
    if (qx <= mid) Operate(l, mid, o << 1);
    if (qy > mid) Operate(mid + 1, r, o << 1 | 1);
    }
  • 有的时候,当题目卡常数时,我们需要把线段树改写为迭代形式,以加快运行速度

可持久化线段树/主席树

  • 严重问题:时刻注意可持久化线段树/主席树的空间占用大小并非$O(n)$而是$O(n\log n)$,要计算后声明足够的内存空间,同时防止内存超过限制