1

对于一类期望类事件,比如说 hdu 5245

首先如果每个元素贡献独立,但如果产生多次贡献算一次,则可以算不产生贡献的概率,用 $1$ 减去这个值就是产生贡献的概率,然后乘以相应的权值即可

2

在一棵树上,如果给定一个点集 $S$,同时给定一个点 $p$

设 $(u,v)$ 是 $S$ 的直径,那么 $p$ 到 $S$ 的最远距离是 $\max(dis(u,p),dis(v,p))$

一般的,两个点集之间的最远距离等于两个点集的直径的交叉距离的最大值

3

如果某个求和不太好做的话,不妨枚举每一个元素,然后求其对答案贡献多少

【HAOI2012】高速公路

4

如果计算一个东西,有两种做法,一种复杂度是 $O(x)$ 的,另一种复杂度是 $O(\frac{n}{x})$ 的

此时可以将 $x \le \sqrt n$ 的用前者解决解决,而 $x \gt \sqrt n$ 的用后者解决

5

如果某个东西比较小,比如说:某个字符的出现次数、允许不匹配的次数

不妨考虑暴力

6

如果某题是要求枚举子集,但数据范围很大,不妨枚举每个元素会对答案产生的贡献

如果在序列上,还可以寻找相邻项的不同之处

7

对于括号序列的匹配问题,一般来说用栈就行了,而且是能匹配就匹配

8

枚举子集的子集的复杂度:
$$
\sum_{i=0}^{T} {T \choose i}2^i=3^T
$$
特别的,对于枚举 $k$ 重子集的方案数为 $(k+1)^T$

9

八数码 问题中,可能会遇到如何给 $9!$ 个状态哈希,当然双哈希是可以的

然而单哈希有时候也是可以的

1
2
const int base = 149, mod = 1e9 + 7; // 这个会有冲突
const int base = 137, mod = 998244853; // 这个神奇的不会产生冲突

10

设 $dia(T)$ 表示树 $T$ 的直径 $(a,b)$,那么 $dia(T \cup {c}) \in {(a,b),(a,c),(b,c)}$

11

如果正着思考不行的话,不如将操作反着来

Cut

12

判读 ${n \choose m}$ 的奇偶性:当 $n\&m =m$ 的时候是奇数,反之是偶数

3300. 奇数统计

如何判断组合数的奇偶

13

固定 $n$ 后的 ${n \choose m}$ 的最大值是 ${n \choose \frac{n}{2}}$

特别的,在 $n=20$ 的时候,${20 \choose 10}$ 大约是 $1.8 \times 10^6$

14

在爆搜的时候,状态数可能比你想象的要少许多

map 可能比你想象的要慢很多,但 哈希挂链 可能比你想象的要快很多

15

如果数据范围不大,比如说 $20 \sim 30$,而且爆搜一下极限数据后发现状态数不大

之后就可以小点暴力,大点直接 $map$ 或哈希表存状态后爆搜

当然也可能是 $bitset$ 暴力之类的

16

遇到 二进制 位运算 贡献位互不相关 后直接考虑拆位做就行了

17

Miskcoo 幂和

于是胡乱想了一个式子……不知道对不对……

若 $\forall x \in [0,n+1] \cap \mathbb{Z}$ 有 $f(x) \in \mathbb{Z}$ 成立,且 $f$ 连续又可积,则有:

$$
\sum_{i=0}^{n} f(i)=\left(\int_{0}^{n+1}f(x)dx \right)-\left(\sum_{i=0}^{n}\int_{i}^{i+1}\left(f(x)-f(i)\right)dx\right)
$$

upd: 然而这个式子的确没有什么用……

18

遇到图论不妨先缩个连通分量

19

看到 至少 最小值最大 或者 答案至少/至多为某个数存在单调性 后可以套二分

20

有选择 $k$ 个的限制后,打表找规律看能否带权二分

21

如果不会写正解,一定要记得去写部分分!!!

22

遇到输入只给 $n$ 之类的,三种方法:

  1. 数学方法推式子
  2. 暴力打表找规律
  3. 暴力dp跑矩乘

23

如果遇到关于位运算的子集之类问题,有如下方向:

  1. 高维前/后缀和/极值
  2. (图论中)每个值向去掉某一位后连边

24

关于存图:

vector 慢到无法想象,手写链表大法好

(当然也适用于 哈希表存每个数的约数

25

注意 数据范围

记得开 long long

26

线段相当于两条射线的交

多边形相当于若干个半平面的交

于是一些求交集最小的问题可以转化为若干简单图形的交的问题

27

常见打表找规律法:

  1. 瞪眼法:将所有小数据都用暴力跑出来,然后瞪着它们直到发现规律
  2. 扰动法:差分/前缀和
  3. 假设可以递推法:若系数是常数,直接无脑算系数,否则用瞪眼法
  4. 容斥系数找规律
  5. $f_i=\sum g_jf_j$,当然 很有可能 是 $f_o=\sum(j+t_j)f_j$
  6. 遇到多维限制,比如说求的是 $f(x,y)$,不妨固定一维,然后就转化成了降一维度后的问题了,即 $g_x(y)$

28

树状数组记得下标不能为 $0$

29

在数据分治的时候小心爆空间

devbin 目录下有一个叫做 size 的命令,十分好用

30

关于输出:

long long%lld

float/double%f,当然可以 printf("%Lf", (long double) x);

long dobule%Lf

当然可以:cout << fixed << setprecision(n) << x;

31

提交前一定要编译一下,CE 就很惨了

注意看编译命令,有没有开 -std=c++11 之类的

32

约数个数很少

你以为是 $O(\sqrt T)$ 级别的?然而 $1 \sim T$ 中所有数的约数个数之和才 $O(T \log T)$ 级别

33

Linux 下:

  1. -fsanitize=address 可以查RE(G++ 4.8+)
  2. -fsanitize=undefined 可以查UB(比如说爆int什么的)(G++ 4.9+)
  3. 最新的NOI Linux 只有G++ 4.8.4

34

遇到最优解问题注意初值!!!

比如说 51nod 1444 破坏道路,若如果两条路径没有交集,注意赋相应初值

35

遇到排列计数问题,然后数据范围 $1000$,不妨考虑从 $1$ 到 $n$ 依次插入进去后的改变量

一般使用动态规划

36

一些出题人可能由于种种原因胡乱造数据(@cmd2001)

于是正解往往会被奇怪的骗分给跑过去

(比如说判断大质数,跑了一次 费马测试 就跑过去的那种)

37

看到数数题,如果数据范围不超过 $10^{10}$,可能暗示需要手动每隔 $1000$ 个数左右打个表,剩下的暴力

38

一定不要忘了还有一种叫做记忆化搜索的东西

转移如果有环的话不妨想一想 $spfa$ 优化转移

39

如果给定矩阵,然后问有多少个子矩阵符合某种条件,一般有两种做法:

  1. 枚举左上角,枚举右下角,然后判断是否合法
  2. 枚举上边界,枚举下边界,然后考虑顶着上下边界的矩形中有多少合法的

一般来说,第二种做法比较通用

39

暴力大法好

  1. 枚举答案/二分答案/三分答案
  2. 求所有答案的交集?TJOI2014 匹配,不妨直接枚举删掉某个边后答案会不会不是最优,如果不是最优那么就是必要边
  3. 静态区间询问:先想暴力,然后看看能不能改成分块/莫队

40

注意审题,比如说 【六省联考2017】期末考试,影响答案的只有最后一科考试结果的产生时间有关,和之前的无关

41

二分图匹配是个好东西

42

小心变量覆盖 这个是致命的

(尤其是小数据都拍过去了,然后大数据跑一个挂一个)

43

$kmp$ 的 $next$ 数组是可以倍增的,于是可以强行做一些神奇的事情,如:【NOI2014 动物园】的一种神奇做法

如果要求 $s$ 在 $t$ 中出现的所有位置,那么可以构造一个字符串 $s\$t$,显然所有 $next$ 值等于 $\mid s \mid$ 的地方都是合法的右端点

注意 $next$ 数组的定义:最长的前缀长度,使得该前缀等于对应长度的后缀,同时前缀严格不等于整个字符串,即 $next_i < i$