Err0r

KSCD_ · 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）
• __builtin_clz(0) 是 UB，要特判（LCA0101T1）

  细节错误

• 函数返回值类型写错（P7706）
• 变量写错（P7831,CF1167E, T386391），数组和数组大小混用（P7913.CF1184E3），映射和原数混用（P2704）
• 忘记特判 0，尤其是除以 0（P10730,P10469）
• 所有数据均要取模，包括初始值大于模数的数（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）
• 求前若干大时整体后移要倒序枚举（ABC394F）
• 二分时若 r 初值是 2\times 10^9 级别，在 \frac{l+r}2 时可能爆 int（ABC395F）
• 要注意寻址常数，比如倍增在 DFS 内预处理会比较慢（LCA-251218）

  算法实现

  数据结构

• 线段树开两四倍空间（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）
• 线段树离散化后区间修改时，对于修改区间 [l,r] 要加入 l-1,l,r,r+1 四个点，因为它们都可能是连续段端点（P14447）
• 可持久化线段树修改一定要开新点（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）
• 多测后缀数组要记得清空 tk，否则可能出神秘问题（P1117）
• PAM 需要先求出 v 的父亲，再连上 u,v 间的边（P5496）

  数学

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

  其他算法

• 二分的上下边界分析（CF1976C,P10730）
• set 常数较大，可以使用可删堆代替「STL 性能陷阱」(25.02-MX-D3T1)
• 整体二分时若可差分，可在询问上修改，而不把 [l,mid] 内的操作反复执行，常数会减小（P1527）
• 整体二分时若询问有序，比如要双指针之类时，需要在递归进右区间前翻转以保证相对顺序不变（LCA251113E）
• FWT 每轮都会除以二，最后再除的值为 2^n（CF662C）