本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-15 20:49:02

模拟赛

25.07-SDSC

• D1T1 corner case 变量写错挂五分。
• D1T4 时间分配失误，导致忘了判不带修的情况。
• D2T1 想麻烦了，写后缀数组 + 笛卡尔树上去，浪费了不少时间。
• D2T3 没有思考算法正确性，在区间不变时被卡掉。
• D3T2 数组开太多 MLE，同时细节写错挂分。
• D4T3 忘判无解挂分。
• D5T2 删调试把输出删了，爆零。
• D7T1 贪心结论显然假了，挂分。
• D7T3 暴力写挂挂分。

校内模拟

• 25.08.20 T2 注意到结论后没有多加思考，导致写法复杂且容易出错。
• 25.09.01 multiset 用成 set，挂分。

25.09-LCA

• 09.25 T1 忘判前导零，挂分。
• 10.02 T3 点双挂了调试时间过长，T4 没时间暴力。
• 10.09 T4 忘看空间限制导致爆掉，挂分。
• 10.20 T1.T3 corner 漏了，挂分。
• 10.23 T3 Dijkstra 堆开错了，挂分。

语法问题

• 不声明 vector 头文件不会报错，但会 CE（CF632D）
• lower_bound 返回值是指针，直接减数组下标得到的值不能直接取 $\min$，可能会 CE（LCA-1108T3）
• 关闭流同步的 cin/cout 不能与快读同时使用（ABC354G），不能与 scanf 同时使用（P10534）
• scanf 读入字符比较鬼畜，最好别（LCA-1113T2）
• __int128 注意强转类型，防止溢出（P10389）
• 不开 #define int long long 后注意区分两个 inf（P2371）
• pow 和 sqrt 均是浮点数运算，有精度问题（ABC361F）
• 赋值 $inf=10^{18}+10$ 的话会因为浮点数精度变成 $10^{18}$，导致边界问题（T386386）
• 直接交换两个数组复杂度为 $O(数组大小)$，用 vector 可 $O(1)$ 交换（CF1983C）
• vector 常数大，存 $10^6$ 级别的元素要谨慎（QBXT24.11-R11T4）
• 线下评测时会记录静态空间使用，程序使用空间应尽可能不超过一半（SDSC-2024-D3T1,2025-D3T2）
• 排序的比较函数必须保证单向合法，不能出现两个元素相等（U468784）
• 元素可重时用 multiset 而不是 set，删除单个元素需要使用 find（ABC170E,P12664）
• 使用 set 的指针时，若 set 有变化指针就会失效，若继续使用是 UB，会运行错误（P11933）
• 函数调用常数较大，取模可以改成 define（MX24.12.08T1）
• vector 进行 resize 后不会清空为 $0$，需要手动清空（CF1439B）
• 嵌套 pair 时无法比较，不能直接放到优先队列或 set 里（P9370）
• int 右移超过 $31$ 位时可能出现问题（CF2118C）
• 二维数组要按照访问顺序尽量让寻址连续，可以减小不少常数（P5046）

细节错误

• 函数返回值类型写错（P7706）
• 变量写错（P7831,CF1167E, T386391），数组和数组大小混用（P7913.CF1184E3），映射和原数混用（P2704）
• 忘记特判 $0$，尤其是除以 $0$（P10730,P10469）
• $i\ge0$ 和 $!i$ 用错（P5829）
• 所有数据均要取模，包括初始值大于模数的数（P10511,24-ZR-D7T3）
• 注意 $l<r$ 等判断要在取模之前（Gym104053F）
• 数组开小（ABC306F,ABC364B.C, P3648），尤其是图论的边数可能是 $n+m$ 或 $2m$（P7624），手写栈 / 队列时要注意极限情况，尤其是队列要开到入队次数（T701837）
• 多测清空（P3952,CF1983E），多测在中途返回值后清空（P3385），多测换行（24.09.27T2）
• 多测要读入完再特判（ABC433E）
• 忘开或没开全 long long（SDSC D2T4,P8392）
• 输入后再预处理（CF482C）
• 赋初值或清空时要注意清完，尤其注意更换下标后的最大值（CF2118D1）
• 最值的初值要赋为无穷，$0$ 会导致漏情况（SGU482）
• inf 赋值要略大于 $10^9$，否则可能会出边界问题（ABC393F）
• 初始化变量时注意不同的初值，避免将所有值错误地赋成相同（P11046）
• 极限数据特判（24.10.19T1,P11747）
• $2^{63}$ 会爆 long long，需要 unsigned long long（P11747）
• 求前若干大时整体后移要倒序枚举（ABC394F）
• 二分时若 $r$ 初值是 $2\times 10^9$ 级别，在 $\frac{l+r}2$ 时可能爆 int（ABC395F）

算法实现

数据结构

• 线段树开两四倍空间（P3919P5787），写 pushdown（P1712,T392687），不要在线段树的叶子节点 pushup（P8334,P7712）
• 吉司机线段树 pushdown 时，判断是否存在最大不能以目前父亲节点最大值判断，而要用左右儿子最大值，因为父亲节点可能已被更新过（P6242）
• 线段树维护历史和时，历史和标记同样需要使用一次函数，尤其是吉司机线段树进行最值操作时的标记（LCA-09.25-T5）
• Splay 的删除操作删根节点时进行了 Splay 操作，根节点会改变，需要在 Splay 前记录原来的根（P6136）
• Splay 写文艺平衡树时要注意找到目前树上的第 $l,r+2$ 个节点操作，且需要将两个点到根的路径均 pushdown 一遍，可以在 kth 中实现（P3391）
• 平衡树求第 $k$ 小时要注意根节点上有一个值，递归进右子树时要减去（P3369,P3391）
• 动态开点线段树空间常数小，时间常数大（P1712）
• 动态开点线段树节点个数初始化为 $1$（CF1741F,CF2030D）
• 可持久化线段树修改一定要开新点（HT-S25.09.12）
• 前缀后缀询问可以使用树状数组，常数远小于线段树（CSP2024T3）
• 开桶注意数据规模，可能要开两倍（ABC282D）
• 01Trie 中所有数组都要开 $n\log n$ 大小（P10853）
• Trie 在插入时要注意维护根节点信息，如子树大小等（24-ZR-D7T3）
• 并查集的路径压缩需要保证整条路径上全部压完，而不是只修改当前点的 $fa$（U471568）
• 序列并查集注意预处理边界（P2391）
• 可撤销并查集撤销时要用栈维护，顺序不能错（P5443）
• ST 表等倍增在预处理时需要升序依次处理（ABC370F），树上倍增需要从根到叶子依次处理（Gym103446H）
• LCT 中 rotate 时要注意各语句先后顺序，如 $y$ 是否为根的判断要在最前，$c_{x,!fx}$ 的使用在更新之前（P3690）
• LCT 中 split,access 修改前，findroot 前后，单点值修改前均需 splay 至根（P3690）
• LCT 中 rotate,access,cut 后均需 pushup，splay,findroot 前均需 pushdown（P3690）
• set 取出某区间内元素时，取到 $x>r$ 要记得放回去（HT-P5707）
• 线性基求第 $k$ 小值时要注意顺序，从高位到低位做（LCA-1113T3）

DP

• 询问值较小而实际值较大时，把大于最大询问值的实际值压到询问值，再加入状态（P8548）
• 分组背包先处理容量为 $0$ 的物品，防止计重（P1782）
• 多重背包二进制优化是先保证最低的连续位全有，最后剩余的放在一个物品，保证所有数均能构成（P1782）
• 换根 DP 时注意维护全部 DP 值，包括父节点和子节点，以及所有 DP 数组（CF627D）
• 换根 DP 等 DFS 时注意全局变量不要重复使用，可能会替换掉有用信息，需要先用完再向下递归（HT-NOI077T2）
• 斜率优化弹队尾时是直接弹出队尾，而不是删掉倒数第二个元素（P3648）

图论

• 建超级源点之后点数为 $n+1$（P5960）
• 链式前向星建边时反向边异或值为 $1$ 需要从 $0$ 或 $2$ 开始标号（P4043）
• Dinic 算法要加当前弧优化以保证复杂度（LCA-XIAN11）
• Dinic 算法中 dfs 时若到汇点返回值为 $flow$（P2764）
• Dinic 算法中若 $r=f$ 时要退出循环，且要写在循环内，否则当前弧优化会假（QOJ143）
• Dinic 求费用流时 dfs 要打标记，否则会由于零环产生死循环（P4014,P4016）
• 求 LCA 跳祖先时 $k$ 从大到小枚举，且要枚举到 $0$（P3398,CF1184E3）
• Dijkstra 开小根堆（LCA10.23T3）
• Kruskal 生成树有两倍点数，若 ST 表快速求 LCA 也需要两倍大小，上界不能错（LOJ137）
• Tarjan 求割边时判定条件是 ${low_v>{dfn}_u}$，而非 $low_u$（ABC375G）
• Tarjan 求割点时注意特判根节点，特判条件是搜索树中的度数大于 $1$，而不是原图度数（QOJ996）
• Tarjan 求割点只能用未遍历过的 $v$ 点判断，即其搜索树上的子节点（P3388）
• Tarjan 求点双时弹栈直到弹出 $v$，而非弹出 $u$（LCA-25.10.02T4）
• 缩点之后求度数之类要判 $u,v$ 是否在同一个连通分量内（MX-S10-B）
• 基环树上拓扑排序求环后只有与环距离为 $1$ 的点 $r=1$，其他不在环上的点 $r=0$，不能直接用作标记（P2607）
• 树链剖分时先 dfs 重儿子（T392687）
• 树链剖分 + 多测时注意清空 $son$ 数组（CF2063E）
• 树上把边权放到子节点上取路径信息时，注意 LCA 上的信息不能取（P4180）
• 点分治搜索时注意判断 $vis$ 标记是否访问，否则复杂度会假（P3806）
• 分层图求最短路时注意若层间的边有负贡献，需要以层数为第一关键字排序，否则会由于负边使得 Dijkstra 答案错误（P9370）
• 01 bfs 的 vis 标记必须在出队的时候打。如果在入队的时候打，就可能有某个位置，本应该在之后某个时刻放入队首，却被放入队尾，导致比答案多 1（P3645）
• 2-SAT 建图时必须建逆否命题，否则是错的（CF2147C）
• 差分约束的限制和跑的最短 / 长路要对应（P5960）

字符串

• 多测处理 char 数组时如果把 $0$ 下标暴力改成 $1$ 下标，会导致终止符丢失并接上前面数据的后面部分，导致出错（LOJ10043）
• Z 函数中要初始化 $z_1=m$ 并从 $i=2$ 开始处理，还要记得更新 $l,r$，否则复杂度错误（CF1598G,P5410,P7114,QOJ786）
• manachar 向原串中插入特殊字符时开头结尾都要加，可以方便讨论（QOJ787）
• manachar 时单个字符为 $0$ 和为 $1$ 不要混用（P3805）
• manachar 时 $f_i\leftarrow f_{l+r-i}$ 时要对 $r-i+1$ 取 $\min$，不然是假的（P3805）
• AC 自动机建立时要将深度为 $1$ 的 $x$ 的 $fail_x$ 初始化为根节点（HT-P5637）

数学

• 写 BSGS 等数论算法时可能有多个模数，变量不要用混（25.06-三轮省集 D6T2）
• 拉格朗日插值求系数时若有 $x_i=0$ 且顺着求除法，需要特判掉分母为 $0$ 的除法（LCA-09.29-H）

其他算法

• 二分的上下边界分析（CF1976C,P10730）
• set 常数较大，可以使用可删堆代替「STL 性能陷阱」(25.02-MX-D3T1)
• 整体二分时若可差分，可在询问上修改，而不把 $[l,mid]$ 内的操作反复执行，常数会减小（P1527）