考试注意

Blog E

gyh 总结

矩阵形式：

A(i,i)=deg⁡(i)A(i,i)=\deg(i)A(i,i)=deg(i)，A(i,j)=−cnt⁡(i,j)（i 到 j 的边权/重边数量）A(i,j)=-\operatorname {cnt}(i,j)\text{（i 到 j 的边权/重边数量）}A(i,j)=−cnt(i,j)（i 到 j 的边权/重边数量）

矩阵形式：

• 内向树：Aout(i,i)=deg⁡out(i)A_{out}(i,i)=\deg_{out}(i)Aout​(i,i)=degout​(i)，A(i,j)=−cnt⁡(i,j)（i 到 j 的边权/重边数量）A(i,j)=-\operatorname {cnt}(i,j)\text{（i 到 j 的边权/重边数量）}A(i,j)=−cnt(i,j)（i 到 j 的边权/重边数量）
• 外向树：Ain(i,i)=deg⁡in(i)A_{in}(i,i)=\deg_{in}(i)Ain​(i,i)=degin​(i)，A(i,j)=−cnt⁡(i,j)（i 到 j 的边权/重边数量）A(i,j)=-\operatorname {cnt}(i,j)\text{（i 到 j 的边权/重边数量）}A(i,j)=−cnt(i,j)（i 到 j 的边权/重边数量）

以 iii 为根的生成树数量为 AAA 删去第 i 行以及第 i 列，之后求行列式。

定义式： det⁡(A)=∑排列P(−1)P 中逆序对数∏i=1nai,P(i)\operatorname{det}(A)=\sum_{排列 P} (-1)^\text{P 中逆序对数}\prod_{i=1}^{n} a_{i, P(i)}det(A)=∑排列P​(−1)P 中逆序对数∏i=1n​ai,P(i)​

• 交换两行，结果取反
• 某行乘 k，结果乘 k
• 某行减去另一行乘一个系数，结果不变，直观理解：

trick

• dp 提前算贡献
• 时光倒流（常用于从环、序列上删数，且过程与所删数当前的前驱、后继相关的时候，或者贪心的候选集合递减（蔬菜））
• 模拟最大流转模拟最小割
• 找不变量（交换差分，逆序对个数奇偶性….）
• xzh 总结的常见套路
• gyh 总结的常见套路
• 分阶段 dp（寿司晚宴&皮配）
• prim 最小生成树
• 按余数分类（定长区间异或 1）
• 消消乐 dp
• n 选 k 使得和最大，n 很大，k 很小，考虑排除没有可能的方案（CF1572D）
• 子树合并 dp 复杂度
• 取关键点（字符串循环节/答案对应的长度不超过 BBB，并支持 n2n^2n2 计算，则可取若干关键区间计算 [1,2B],[B,3B],[2B,4B]⋯[1,2B],[B,3B],[2B,4B]\cdots[1,2B],[B,3B],[2B,4B]⋯）
• dp 变为 dag 路径计数（然后可以搞一些操作，比如在反图上跑）
• 二进制分组斜率优化（当斜率不递增时，可以分别开若干个大小为 20,21,22⋯2^0,2^1,2^2\cdots20,21,22⋯ 的单调栈，加的时候先在最小的里面加，一旦大小撑爆了就跟下一个单调栈合并）
• i 行 j 列转化为 i 行向 j 列连边。
• 在生成树上构造。
• 点减边容斥。求连通块个数转化为求包含每个点连通块个数-包含每个边连通块个数

我的常犯错误

做题策略（惨痛教训）

1. 开始把题全看一遍（15 min 左右）
2. 开始想题前手玩样例（5 min 以内可以玩的话）
3. 除非分数有保障，想题超过 30 min 考虑换换，不要有心理负担，暴力也能搞好多分
4. 思路较复杂，且不好调的题，重新回忆下算法，不一定是写错了，可能是假了。不要一心认为某nb做法是对的，其他做法是假的。

2021省选

我 tm RE 了！\large{\text{我 tm {\color{purple}RE} 了！}}我 tm RE 了！

• 爆搜不要瞎加剪枝，引起不必要的 RE，导致 60+分 -> 0分
• 暴力拼起来的题全打挂
• 想出算法开始打，打完发现算法假，灵机一动新想法，又写了个假算法。
• 诸如两个数的和，这类边界特判要特别注意，最大值是原来两倍

2020NOIP

• 求 lcm 注意要 先除后乘

NOI 笔试易错

• RAM=Random Access Memory，ROM=Read-Only Memory 分不清
• Lazarus 是 Pascal IDE，GUIDE 和 Anjuta（AG）是 C++ IDE （然而我用 vim）

• multimap 的 erase(x) 会把所有值等于 x 的删掉

• 建图把无向图建成有向图
• 组合数计算函数忘记特判 x>y，x,y<0，开 O2 后 UB 爆零了。。
• 预处理阶乘/扫描线分开存储修改查询时，数组忘 开两倍

• 线段树着急写错左右儿子
• 值域线段树 pushdown 忘记把空节点新建出来

fhqTreap 专栏

• pushdown 时要 判空节点
• 按 rank 分裂时应该判断 sz[ls]+1>=rank
• push_up 时 sz[p]=sz[ls]+sz[rs]+1 忘记写 +1
• 把 split 复制粘贴改成 splitrk 忘记改递归的函数名
• split(rt,b,c) 之后应该 split(b,a,b)，写成 split(rt,a,b)

• 求树的直径时忘记把父亲的跟儿子取 max
• 线段树合并忘记 判断叶子节点
• 点分治忘记考虑 分治中心的贡献
• 扫描线先改后查
• 莫队排序写挂
• AC 自动机，在把 fail 树上子树加起来的时候，必须显式建图，倒着遍历所有节点，并加到自己的 father 上不对
• dinic 中 bfs 的 queue 忘记清零
• 写线性基形式的高斯消元时，消元这一步：

inline void eli(double *x,double *y,int ind){
    if(is0(x[ind]))return;
    double rate=x[ind]/y[ind];
    for(int i=0;i<=ind;i++)//第四行
        x[i]-=y[i]*rate;
}

第 4 行不可以循环到 n，否则会被卡精度。

• 函数内开大数组 RE 了
• 对拍时要把 std 中的小数据暴力注释掉
• 编译不会开 O2 的命令 g++ -O2 -Wall *.cpp -o *

Tarjan 专栏

• 有向图建成无向图
• 缩完点后建图把原来的点和缩成的点搞混。。。
• instack 数组应该在弹栈时置零

• 强连通：dfn[p]==low[p]，弹到 p。
• 点双：low[nx]==dfn[p]，则如果 p 不是搜索树的根，或者 p 在搜索树上有多个儿子，p 为割点，弹栈直到 nx（nx 要保留，因为割点可能在多个点双中）
• 边双：dfn[p]==low[p]，弹到 p，当前边为桥。

总是忘记的

• sa 中求 h 数组时：h[rk[i]]>=h[rk[i-1]]-1
• 2-SAT 中最终应该选择编号大的强连通分量

作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接

• Previous
  【题解】P5979 [PA2014]Druzyny