那些年，我们写错的代码
Nickel_Angel
2019-05-16 13:32:33
在OI中，代码在细节问题上出错，虽是正常，但紧随其后的调试工作付出的时间和经历是巨大的……
~~有时，你与电脑蓝屏就差一行代码~~
本篇旨在记录自己在写代码时的各种出现频率频繁的~~智障~~错误（也算个错题集吧$qwq$）……
本文情绪化~~吐槽~~内容可能会很多……请予以理解$QAQ$
#### 程序相关
1. 在启用 `#include <cmath>` 后切忌使用全局变量名 `y1`！~~虽然可以自己写个 namespace 回避就是了~~
2. 注意检查是否会在**条件语句后**多打一个**多余的分号**！
3. 注意检查是否在代码中混淆**赋值符号 `=` 和逻辑运算符 `==`**！
4. 写 `for` 语句时，注意**末尾循环体**是否需要与**单次表达式**初始化的变量**一致**！
5. **多组数据**检查一下是否**所有需要清空的数组**每次都被清空了！
6. 考试时记得检查 `freopen` 是否打错了！
#### 最小生成树(Kruskal)
##### 1. 将边按边权排序&&并查集初始化
```cpp
sort(e + 1, e + /*n*/ m + 1, cmp);//这里n（点数）应为m（边数）
```
```cpp
for(int i = 1; i <= /*m*/ n ; ++i) fa[i] = i;
//这里m为边数，应以n（点数）为上界初始化并查集QwQ
```
##### 2.统计边数
```cpp
if(cnt /*>*/ >= k) break;//cnt为目前选了几条边，k为需要几条边
```
故其中“>”应改为“>=”……
#### 单源最短路径(dijkstra)
```cpp
typedef pair<int, int> P;
//...
int head[maxn], to[maxn], nxt[maxn], val[maxn], tot;
inline void add_edge(int u, int v, int w)
{
to[++tot] = v;
val[tot] = w;
nxt[tot] = head[u];
head[u] = tot;
}
int dis[maxn], vis[maxn]
priority_queue<P, vector<P>, greater<P> > q;//注意是小根堆,需要vector和greater重载
void dijkstra(int S)
{
memset(dis, 0x3f, sizeof(dis));//注意需先将dis数组里的值变为无限大
memset(vis, false, sizeof(vis));
dis[S] = 0;//注意初始化dis[S]
//和spfa不同的是，这里不用使vis[S] = true...
q.push(P(0, S));
//注意入队的是二元组,由于二元组默认以第一关键字排序,故第一个元素是距离,第二个为节点编号
int u;
while (!q.empty())
{
u = q.top().second;
//注意priority_queue的取堆顶的操作是q.top(),这里取得是节点编号,应为second
q.pop();//这里先出队,简化代码
if (vis[u]) continue;
vis[u] = true;//先判断,后打标记
for (int c = head[u], v; c; c = nxt[c])
{
v = to[c];
if (vis[v]) continue;
if (dis[v] > dis[u] + val[c])//注意比较符号
{
dis[v] = dis[u] + val[c];
q.push(P(dis[v], v));
}
}
}
}
```
#### 字符串哈希
其公式为$hash[i] = (hash[i - 1] \times k + string[i])\,mod\,p$
其中$k$宜选用：$31,131,13131,174,233,\cdots$
$p$宜选用：$200209171,200207261$
~~但事实上STL中的prime_list能给我们很大启发~~
```cpp
// std::__detail and std::tr1::__detail definitions -*- C++ -*-
// Copyright (C) 2007-2018 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
namespace __detail
{
// The sentinel value is kept only for abi backward compatibility.
extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
{
2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, 1725587117ul,
1866894511ul, 2019773507ul, 2185171673ul, 2364114217ul, 2557710269ul,
2767159799ul, 2993761039ul, 3238918481ul, 3504151727ul, 3791104843ul,
4101556399ul, 4294967291ul,
// Sentinel, so we don't have to test the result of lower_bound,
// or, on 64-bit machines, rest of the table.
#if __SIZEOF_LONG__ != 8
4294967291ul
#else
6442450933ul, 8589934583ul, 12884901857ul, 17179869143ul,
25769803693ul, 34359738337ul, 51539607367ul, 68719476731ul,
103079215087ul, 137438953447ul, 206158430123ul, 274877906899ul,
412316860387ul, 549755813881ul, 824633720731ul, 1099511627689ul,
1649267441579ul, 2199023255531ul, 3298534883309ul, 4398046511093ul,
6597069766607ul, 8796093022151ul, 13194139533241ul, 17592186044399ul,
26388279066581ul, 35184372088777ul, 52776558133177ul, 70368744177643ul,
105553116266399ul, 140737488355213ul, 211106232532861ul, 281474976710597ul,
562949953421231ul, 1125899906842597ul, 2251799813685119ul,
4503599627370449ul, 9007199254740881ul, 18014398509481951ul,
36028797018963913ul, 72057594037927931ul, 144115188075855859ul,
288230376151711717ul, 576460752303423433ul,
1152921504606846883ul, 2305843009213693951ul,
4611686018427387847ul, 9223372036854775783ul,
18446744073709551557ul, 18446744073709551557ul
#endif
};
} // namespace __detail
```
#### 树状数组
##### 1.初始化
1.如果使用的是**区间修改**版本的树状数组，有爆$int$的风险，**请使用$long$ $long$ !**
~~2.请自行加入以下代码：~~
```cpp
struct BIT
{
#define lowbit(x) ((x) & -(x))//注意x两边须加括号（尤其是写线段树的时候QAQ）
//do something...
#undef lowbit
}
```
##### 2.add
```cpp
inline void add(int pos, int x)
{
for (int i = pos; i <= max_size; i += lowbit(i))//i += lowbit(i) 不要写作 ++i !
v[i] += x;
}
```
##### 3.query
```cpp
inline int query(int pos)//不要写作void !
{
int res = 0;
for (int i = pos; i; i -= lowbit(i))//注意这里为 -= !
{
res += v[i];
}
return res;
}
```
#### ST 表
##### 1.初始化
```cpp
inline void init(int *a, int bound)
{
for (int i = 1; i <= bound; ++i) st[i][0] = a[i];//不要忘记初始化 st[i][0] !
for (int j = 1; (1 << j) <= bound; ++j)//注意循环 i, j 的位置
{
for (int i = 1; i + (1 << j) - 1 <= bound; ++i)//注意 i 的边界
{
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
//注意是 1 << (j - 1),因为 (1 << (j - 1)) + (1 << (j - 1)) = (1 << j)
}
}
}
```
##### 2.查询
```cpp
inline int query(int s, int e)
{
int k = log_2[e - s + 1];//注意取的是区间长度
return max(st[s][k], st[e - (1 << k) + 1][k]);//注意这里 e - (1 << k) 需要 +1
}
```
#### 倍增LCA
##### 1.dfs_init & log_2数组的预处理(初始化)
这里$log_2[i]$中存的是$\lceil\log_2{i}\rceil$的值……
```cpp
void dfs_init(int u, int pre)
{
fa[u][0] = pre;
depth[u] = depth[pre] + 1;
//do something...(like record vartexs' messages, and so on ...)
//这里记录其他信息时请勿混淆……
for (int i = 1; (1 << i) <= depth[u]; ++i)
fa[u][i] = fa[fa[u][i - 1]][i - 1];//切忌写反……
for (int c = head[u]; c; c = nxt[c])
{
if (to[c] != pre) dfs_init(to[c], u);
//这里操作不多,不需申请临时变量 v,但用了一定要初始化QAQ
}
}
int log_2[maxn];
void log_2_init(int n)
{
log_2[0] = -1;
for (int i = 1; i <= n; ++i) log_2[i] = log_2[i >> 1] + 1;
log_2[0] = 0;//不将其清零有RE风险
}
```
##### 2.跳LCA
```cpp
inline int lca(int x, int y)
{
if (depth[x] < depth[y]) swap(x, y);
//由于跳lca应先跳深度较深的节点(x),故不满足depth[x] > depth[y]时应将x,y交换,注意"<"和">"的区别
while (depth[x] > depth[y])
x = fa[x][log_2[depth[x] - depth[y]]];
//由于x要先跳到和y同一深度,不能跳过,所以每次跳的层数为log_2[depth[x] - depth[y]],注意不要写错!
if (x == y) return x;
for (int i = log_2[depth[x]]; i >= 0; --i)//注意不要写为++i QAQ
{
if (fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
}
//x,y一起向上跳直到fa[x][0] == fa[y][0]为止,故它们的lca为fa[x][0]!
return fa[x][0];
}
```
#### 树链剖分
##### 1.dfs_1 & dfs_2
1.最重要的一点:写完这两个函数后,不要忘了在主函数中调用……~~(要不然你写它干什么→_→)~~
```cpp
void dfs_1(int u, int pre)
{
fa[u] = pre;
depth[u] = depth[pre] + 1;
Size[u] = 1;//注意初始化……
for (int c = head[u], v; c; c = nxt[c])
{
v = to[c];
if (v == pre) continue;//死循环预警QAQ
dfs_1(v, u);
Size[u] += Size[v];//这两句语句 u, v 容易写反，请小心qwq
if (Size[son[u]] < Size[v]) son[u] = v;
}
}
void dfs_2(int u, int tp)
{
++dfs_t;//dfs的时间戳记得+1
Top[u] = tp;
id[u] = dfs_t;
//do something...(like record vartexs' messages, and so on ...)
if (!son[u]) return;//无孩子的节点(叶节点)无需剖分
dfs_2(son[u], tp);
//由于重链除链顶节点是轻儿子外,其他节点均为重儿子,而又要求我们先剖分重儿子,所以剖分重儿子时链顶不变
for (int c = head[u], v; c; c = nxt[c])
{
v = to[c];
if (v == fa[u] || v == son[u]) continue;
dfs_2(v, v);//每条重链链顶需为轻儿子,故dfs新链链顶时应换为 v
}
}
```
##### 2.跳链(以“将树从x到y结点最短路径上所有节点的值都加上z”的操作为例)
```cpp
inline void route_modify(int x, int y, int z)
{
while (Top[x] != Top[y])//注意 while 和 if 的区别QAQ
{
if (depth[Top[x]] < depth[Top[y]]) swap(x, y);
//由于每次跳是所在链链顶较深的节点 x 向上跳,故这里写作 <
tree.modify(id[Top[x]], id[x], z);
//由于dfs_2处理时是由链顶向链底重新标的号,故有 id[Top[x]] < id[x],不要写反……
x = fa[Top[x]];
}
if (depth[x] > depth[y]) swap(x, y);//这与跳链时的比较相反!应写作 >
tree.modify(id[x], id[y], z);
}
```
#### AC自动机
##### 1.初始化
1.tot注意清0!
2.有多少种不同的字符ch的第二维就开多少个孩子的数组，否则越界就会QAQ~~于是就调了3天~~
```cpp
int ch[20100][26], fail[20100], tot;//ch的第二维要开足……
inline void Init()
{
tot = 0;//注意清0!
memset(ch, 0, sizeof(ch));
memset(fail, 0, sizeof(fail));
}
```
##### 2.add(添加字符串)
目前还未发现错误……
##### 3.build（建fail树）
1.记得写q.pop()!~~上次电脑就因为这个差点蓝屏~~
2.注意bfs时需要入队的操作
3.bfs前注意需让根节点（即0号节点，这是特定节点!!!）的孩子进队……
```cpp
inline void build()
{
queue<int> q;
for (int i = 0; i < 26; ++i)
{
if (ch[0][i]) q.push(ch[0][i]);//注意这里是0
}
int u;
while (!q.empty())
{
u = q.front();
for (int i = 0; i < 26; ++i)
{
if (ch[u][i])
{
q.push(ch[u][i]);//不要忘记入队QAQ
fail[ch[u][i]] = ch[fail[u]][i];
}
else ch[u][i] = ch[fail[u]][i];
}
q.pop();//不写会死循环
}
}
```
#### 其它错误
2019.5.16
[P3966 单词](https://www.luogu.org/problemnew/show/P3966)
这题注意字符串长为$1 \times 10^6$!
于是………
```cpp
const int maxn = 1e6 + 10;
char s[/*1010*/ maxn];
```
注意**dfs**不要写**inline**!
upd：由于inline很智能，编译器会自动判断inline会不会速度更快，是否需要inline，~~但为保险起见还是多注意些~~
```cpp
/*inline*/ void dfs(int u)
{
//do something...
dfs(v);
//do something...
}
```
***
2019.5.28
[P3533 [POI2012]RAN-Rendezvous](https://www.luogu.org/problemnew/show/P3533)
由于是英语题，首先看一下题目大意：
给定一棵内向基环树森林，多次询问两个点$a$和$b$，求点对$(x, y)$满足：
1.从$a$出发走$x$步和从$b$出发走$y$步会到达同一个点
2.在1的基础上如果有多解，那么要求$max(x, y)$最小
3.在1和2的基础上如果有多解，那么要求$min(x,y)$最小
4.如果在1、2、3的基础上仍有多解，那么要求$x \geq y$
**输入格式：**
第一行有两个整数$n$和$k$（分别代表基环树森林的节点数和询问的个数，其中$1 \leq n, k \leq 5 \times 10^5$）；
第二行$n$个整数，表明编号为的$i$节点向以第$i$个整数为编号的节点连一条单向边；
接下来$k$行，每行两个整数表明本次询问的两个点$a$和$b$
**输出格式：**
输出$k$行，每行两个整数，表明对应询问的答案，无解输出"-1 -1"（不包括引号）
本题显然是倍增跳LCA，后判断：
如果$a, b$均不在环内且它们的最短路径不过环，显然LCA为最优解
否则需要在环内讨论（下文$root_a, root_b$分别表明的是$a, b$两节点向上走，走到环内所遇到的第一个节点）
注意以下坑点：
1.由于输入时每个节点连的是一个**单向边**，故在环上只有两个可选择的较优解，分别为$root_a$到$root_b$和$root_b$到
$root_a$，由于点之间为单向边，在环上只可**单向通行**（即只能按照顺时针，逆时针中一个方向走，当然这个方向题
目在建图时已给定）故不可以取环上$root_a, root_b$之外的点为较优解
2.如果$root_a$到$root_b$和$root_b$到$root_a$的这两组解均满足题目中的条件1,2,3
即若设$root_a$到$root_b$和$root_b$到$root_a$的答案分别为$(ans_{ab}.x, ans_{ab}.y)$和$(ans_{ba}.x, ans_{ba}.y)$且已满足：
$max(ans_{ab}.x, ans_{ab}.y) = max((ans_{ba}.x, ans_{ba}.y)), min(ans_{ab}.x, ans_{ab}.y) = min(ans_{ba}.x, ans_{ba}.y)$
仍然需要判断$ans_{ab}.x \geq ans_{ab}.y$和$ans_{ba}.x \geq ans_{ba}.y$从而取得最优解……
~~然而第一次提交时我没注意这个条件，但交上去却A掉了，望加强数据qwq~~
***
2019.6.1
[CF311B Cats Transport](http://codeforces.com/problemset/problem/311/B)
```cpp
void example_input()
{
long long a;
int b;
scanf("%lld%d", &a, &b);//在使用scanf和printf时请注意适配符与输入变量格式的匹配qwq
//do something...
}
```
写题时没注意……然后本来正确的答案因为适配符与输入变量格式不匹配导致出错$QAQ$
~~但这似乎跟本题的考点斜率优化没有什么关系~~
***
2019.6.5
判断两个数$a,b$是否互质时，在不保证$a,b$为质数的情况下，要直接判断它们的$gcd$是否为$1$，~~而不是简单判断$a\,mod\,b$是否为零~~
***
2019.6.9
[P1757 通天之分组背包](https://www.luogu.org/problemnew/show/P1757)
请注意变量意义$QAQ$
```cpp
vector<int> K[101];
for (int i = 1, k; i <= n; ++i)
{
scanf("%d%d%d", v + i, c + i, &k);
K[k].push_back(/*k*/ i);
//k是第i个物品所属的组,而vector<int> K[k]记录了第k组所含物品编号,这里明显写错了(混淆了变量意义)
maxnum = max(maxnum, k);
}
```
请注意循环变量的边界和使用的正确性（错误多发地）……
```cpp
for (int i = 1; i <= maxnum; ++i)
{
for (int j = V; j >= 0; --j)
{
for (int k = 0; k < (int)K[i].size(); ++ /*i*/ k)//内层循环使用的是k!不是i!
{
if (j >= v[K[i][k]])//注意边界，RE警告
dp[j] = max(dp[j], dp[j - v[K[i][k]]] + c[K[i][k]]);
}
}
}
```
~~然而这次数组越界严重到没有RE直接WA掉~~
***
2019.6.16
写数学题请注意数据范围，记得开long long!
如题目中$q\leq10^{18}$就直接开long long吧$QAQ$
~~编译器提醒您：数据千万条，范围第一条，不将long long开，出错两行泪~~
***
2019.6.19
在写chkmin时，不小心写反了比较符号$\cdots$~~却歪打正着的A了一道题QAQ~~
```cpp
template<typename T>
inline bool chkmax(T &x, const T &y) {return x < y ? (x = y, true) : false;}
template<typename T>
inline bool chkmin(T &x, const T &y) {return x > y ? (x = y, true) : false;}
```
****
2019.7.3
在写快速幂时又将while写成if了……
```cpp
inline int power(int a, int b, int p)
{
int res = 1;
/*if*/ while (b)
{
if (b & 1) res = 1ll * a * res % p;
a = 1ll * a * a % p;
b >>= 1;
}
return res;
}
```
***
2019.7.7
本来想用bitset写[P2757 [国家集训队]等差子序列](https://www.luogu.org/problemnew/show/P2757)练手，然后RE……
后来才发现是break的位置写错了QAQ……
**要注意continue,break等语句的位置问题!**
细节如下：
```cpp
//...
while (T--)//这里是多组数据
{
bool flag = false;//flag记录本组数据的答案
//do something...
for (int i = 1, x; i <= n; ++i)//这里是题目中要求的输入n个数
{
scanf("%d", &x);
//do something...
if (check())//这里check为判断解的函数
{
flag = true;
//break;
//注意这里不能break...这会导致本组数据未读入完毕而直接被当做下一组数据读入,从而出错
}
}
}
```
~~这种错误总是在自认为这么写可以优化的情况下出现的~~
****
2019.7.9
在树上倍增预处理时，这里以取某区间的最大值为例，要像ST表那样更新：
```cpp
inline void multi_init()
{
for (int i = 1; i <= log_max; ++i)
{
for (int u = 1; u <= n; ++u)
{
fa[u][i] = fa[fa[u][i - 1]][i - 1];//这里是更新2的(i - 1)次方级祖先
Max[u][i] = max(Max[u][i - 1], Max[fa[u][i - 1]][i - 1])
//这里类似于ST表更新,尤其注意第一个参与max比较的元素是Max[u][i - 1]
}
}
}
```
在询问时，注意别忘了跳链……
```cpp
inline int query(/*...*/)
{
for (int i = log_max; i >= 0; --i)
{
if (depth[fa[x][i]] >= depth[y])
{
//update answer...
x = fa[x][i];//这句话一定要加上QAQ
}
}
}
```
***
2019.7.12
~~static什么的都去死吧 (╯°Д°)╯~~
```cpp
template<typename T>
inline void input(T &x)
{
x = 0;
/*static*/ char ch = getchar();
/*static*/ bool f = false;
//这里由于是static,故f只会在第一次执行该函数时被初始化为false,而在第二次调用时不会再被初始化!
//从而导致一旦读入负数,后面的数会也被看成负数,从而出错...
while (!isdigit(ch))
{
if (ch == '-') f = true;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = f ? -x : x;
}
```
***
2019.7.18
如果并查集拥有链表等**指示方向**的作用时，**不能写按秩合并!** ~~连续被坑了两次QAQ~~
***
2019.7.20
注意tarjan缩点后的图是 $DAG$，而不是树，还要注意有可能有重边和自环，需要判掉……
重边：数据范围小可以用邻接矩阵直接 $O(1)$ 判，数据范围大可以时间换空间，用map可以做到 $O(\log n)$
自环：只需连边时判断两点是否在一个联通分量中即可。
***
2019.8.1
> 艾莉芬经过**仔细阅读题面、认真分析数据范围**后，开始编写程序求解这个问题。
>
> ——[十二省联考2019]春节十二响
***
2019.8.4
Dinic 在 dfs 时一定要减去当前已用过的流量！
```cpp
res = dfs(v, min(val[c], flow - used/*注意将 used 减去*/), T);
```
***
2019.8.15
建图时双向边一定要开双倍空间！QAQ
***
2019.8.16
斜率优化时注意在将形如 $\frac {y_i - y_j} {x_i - x_j} \geq k$ 转化为 $y_i - y_j \geq k \times (x_i - x_j)$ 时，注意 $x_i - x_j$ 可能为负数，符号方向需改变。
***
2019.9.7
注意在矩阵乘法中，非 $n \times n$ 矩阵不能用缓存优化！（被坑了一晚上 QAQ）
```cpp
friend Matrix operator * (const Matrix &A, const Matrix &B) const
{
Matrix res = Matrix(B.n, A.m);
for (int i = 0; i < res.n; ++i)
{
for (int j = 0; j < res.m; ++j)
{
for (int k = 0; k < A.m; ++k)//这里不能交换 j, k 的枚举嵌套顺序
{
res.v[i][j] = res.v[i][j] + A.v[i][k] * B.v[k][j];
}
}
}
return res;
}
```
***
2019.9.10
在写主席树时，需注意即使当前结点在主席树上存在，我们大部分情况下仍需新建该节点，以保存旧结点的值。
```cpp
void modify(int s, int e, int pre, int &root, int pos)
{
/*if (!root)*/ root = ++tot;
ch[root][0] = ch[pre][0], ch[root][1] = ch[pre][1];
v[root] = v[pre] + 1;
if (s == e) return;
int mid = (s + e) >> 1;
if (pos <= mid) modify(s, mid, ch[pre][0], ch[root][0], pos);
else modify(mid + 1, e, ch[pre][1], ch[root][1], pos);//注意一定要加 else !
}
```
***
2019.9.16
注意浮点数计算时一定要检查是否有变量开成了整形！~~awsl~~
***
2019.9.18
注意启发式合并是将元素较小集合合并到元素较大的集合中，因为这样可以使每个元素取出的次数尽可能少（大约为 $O(\log n)$），才能达到启发式合并 $O(n \log^2 n)$ 的时间复杂度。
***
2019.10.31
~~时间跨度好大~~
在写模拟退火时，设 $ans$ 为目前的最优解，$res$ 为当前随机到的解，设 $diff = res - ans$，且我们希望答案为最小值，则当 $diff < 0$ 时我们取最优解，否则我们要以 $e^{\frac {-diff} {kT}}$ 的概率接受这个解，故应写为：
```cpp
int diff = res - ans;
if (diff < 0) ans = res;
else if (exp(-diff / T) * RAND_MAX > rand()) //ramain res...
```
***
2019.11.1
注意写题时估计答案的范围！~~调了一下午QAQ，不过还学会了对拍w~~
**对拍时小数据没问题，大数据出锅 $\rightarrow$ 是否爆精度**
***
2019.11.6
在写 splay 时出现了错误，先检查宏定义的 $chk(x)$ 是否出错QAQ !
```cpp
#define chk(x) (ch[fa[x]][1] == x)//不要写成其他奇怪的东西!
```