算法思想·多选训练5

第 1 题（多选）

关于 Tarjan 求 SCC，正确的有（）。

{{ multiselect(1) }}

• 当 low[u]==dfn[u] 时，u 是一个 SCC 的根并弹栈直到 u
• dfn[u] 是 DFS 访问时间戳
• 每个点会属于多个 SCC
• low[u] 反映从 u 可追溯到的最小 dfn

第 2 题（多选）

关于网络流，正确的有（）。

{{ multiselect(2) }}

• 残量网络表示仍可调整的容量
• 增广路只能在树上寻找
• 最大流值等于最小割容量
• 反向边用于撤销或调整已有流量

第 3 题（多选）

关于有限无环无偏正常规则组合游戏中的 SG 函数，正确的有（）。

{{ multiselect(3) }}

• SG 定理可直接处理任意带概率转移的游戏
• SG(x)=mex{SG(y)}，y 为后继局面
• 多个独立子游戏的 SG 值异或为总局面 SG
• SG=0 表示先手必败

第 4 题（多选）

关于容斥与莫比乌斯反演，正确的有（）。

{{ multiselect(4) }}

• 莫比乌斯反演常用于约数偏序上的反演
• 三集合容斥中三重交集为正号
• 容斥通过加减交集修正重复计数
• 容斥不需要明确事件是否重叠

第 5 题（多选）

关于树链剖分，正确的有（）。

{{ multiselect(5) }}

• 常配合线段树处理路径修改/查询
• 依赖重儿子和 DFS 序编号
• 只能处理链，不能处理树
• 可把一条树上路径拆成 O(log n) 个链段