考试注意

惨痛教训

Posted by ethan-zhou on April 13, 2022

重要公式

gyh 总结

矩阵树

无向图

矩阵形式:

$A(i,i)=\deg(i)$,$A(i,j)=-\operatorname {cnt}(i,j)\text{(i 到 j 的边权/重边数量)}$

有向图

矩阵形式:

  • 内向树:$A_{out}(i,i)=\deg_{out}(i)$,$A(i,j)=-\operatorname {cnt}(i,j)\text{(i 到 j 的边权/重边数量)}$
  • 外向树:$A_{in}(i,i)=\deg_{in}(i)$,$A(i,j)=-\operatorname {cnt}(i,j)\text{(i 到 j 的边权/重边数量)}$

以 $i$ 为根的生成树数量为 $A$ 删去第 i 行以及第 i 列,之后求行列式。

行列式

定义式: \(\operatorname{det}(A)=\sum_{排列 P} (-1)^\text{P 中逆序对数}\prod_{i=1}^{n} a_{i, P(i)}\)

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

trick

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

我的常犯错误

做题策略(惨痛教训)

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

重大错误

2021省选

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

2020NOIP

  • 求 lcm 注意要 先除后乘

NOI 笔试易错

  • RAM=Random Access MemoryROM=Read-Only Memory 分不清
  • Lazarus 是 Pascal IDE,GUIDE 和 Anjuta(AG)是 C++ IDE (然而我用 vim)

STL

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

细节

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

数据结构

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

fhqTreap 专栏

  • pushdown 时要 判空节点
  • rank 分裂时应该判断 sz[ls]+1>=rank
  • push_upsz[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 为割点,弹栈直到 nxnx 要保留,因为割点可能在多个点双中)
  • 边双:dfn[p]==low[p],弹到 p,当前边为桥。

总是忘记的

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

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


阅读量:


icon