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$ 之类的，三种方法：

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

23

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

高维前/后缀和/极值
（图论中）每个值向去掉某一位后连边

24

关于存图：

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

（当然也适用于 哈希表 和 存每个数的约数）

25

注意 数据范围

记得开 long long

26

线段相当于两条射线的交

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

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

27

常见打表找规律法：

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

28

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

29

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

dev 的 bin 目录下有一个叫做 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 下：

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

34

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

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

35

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

一般使用动态规划

36

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

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

（比如说判断大质数，跑了一次 费马测试 就跑过去的那种）

37

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

38

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

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

39

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

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

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

39

暴力大法好

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

40

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

41

二分图匹配是个好东西

42

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

（尤其是小数据都拍过去了，然后大数据跑一个挂一个）

43

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

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

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

44

只用 $1 \sim n$ 可以凑出来 $1 \sim \frac{n(n+1)}{2}$ 中的所有数（每个数只能用一次）

于是有一个鬼畜的题

定义 $n$ 是一个好数当且仅当 $\forall T \subseteq S=\mathbb{N} \cap [1,n]$，满足 $\sum T=(\sum S)-(\sum T)$

试判断 $n$ 是否是好数

$\sum T=(\sum S)-(\sum T) \Rightarrow \sum T=\frac{n(n+1)}{4}$

首先 $n$ 的先决条件是 $4 \mid n(n+1)$

有一种构造 $k$ 的方法（$1 \le k \le \frac{n(n+1)}{2}$）：

从 $n$ 到 $1$ 依次枚举 $i$，如果 $k-i \ge 0$，那么就把 $k$ 减去 $i$

（似乎这种方式构造出 $k$ 用的元素最少）