# 1. 反哈希攻击（故意构造碰撞）在竞赛中的防御策略 A 随机化基数并配合大素数模数使攻击者无法预先构造碰撞对 ✓ 正确答案 B 使用固定的大素数模数即可完全杜绝碰撞 C 自然溢出在任何情况下都比大素数模更安全 D 双哈希后碰撞概率与单哈希完全相同
# 2. 树状数组上二分（find by prefix sum）的实现中利用二进制提升从高位到低位累加，O(log n) 找前缀和首次 ≥ k 的位置 A 必须对树状数组做普通二分查找才能得到 O(log n) B 从高位到低位逐位尝试累加，复杂度 O(log n) ✓ 正确答案 C 该操作复杂度为 O(n log n) D 只能查找最大值，不能查找前缀和
# 3. 树状数组查询前缀和复杂度为 O(log n) 的位运算来源 A 每执行一次 i -= lowbit(i) 消去二进制中一个 1，最多 O(log n) 次 ✓ 正确答案 B 每次查询要遍历所有节点 C 树状数组使用二分查找 D 查询与 lowbit 无关
# 7. 快速选择（QuickSelect）期望 O(n) 与最坏 O(n²) 的来源 A 每次 pivot 都让两侧均衡 B 使用了递归 C 需要排序整个数组 D 每次 pivot 都选到极端元素导致每层只缩小 1 ✓ 正确答案
# 8. 线段树 Beats（区间历史最值/区间取 min）的复杂度证明中势能函数 Φ 在 chmin 操作下的递减性，总复杂度 O(n log² n) A 递推关系 T(n)=T(n/2)+O(1) B 势能函数 Φ 在 chmin 下递减，总势能下降有界 ✓ 正确答案 C 二分查找 D 随机化选点
# 12. 如何用大素数模 + 自然溢出做哈希及二者的风险差异 A 两者风险完全相同 B 大素数模一定不会碰撞 C 自然溢出一定不会碰撞 D 自然溢出在对抗性输入下可能被构造碰撞，风险更高 ✓ 正确答案
# 14. 随机化快排/快速选择为何随机选 pivot 能避免最坏退化 A 让算法变慢 B 减少比较次数到 O(n) C 让排序结果随机 D 消除针对固定 pivot 的对抗输入，使期望复杂度有保证 ✓ 正确答案
# 17. 双哈希（double hashing）为何大幅降低碰撞到可忽略 A 双哈希只用一个模数 B 双哈希一定不碰撞 C 双哈希速度更快 D 两个独立哈希同时碰撞的概率是各自概率的乘积 ✓ 正确答案
# 20. 如何向面试官说明某问题"只能近似且已知近似界" A 该问题在 P≠NP 假设下无多项式精确算法，且已知近似比上下界 ✓ 正确答案 B 该问题涉及大数据 C 该问题代码复杂 D 该问题无人研究
# 29. 近似算法中"近似比"的严格定义（≤ / ≥ OPT 的方向） A 近似解成本与 OPT 无关 B 近似解成本 C 满足 C ≥ α·OPT C 近似解成本 C 满足 C ≤ α·OPT ✓ 正确答案 D α 必须大于 n
# 38. PTAS 与 FPTAS 的区别及其对输入规模的依赖 A 两者相同 B FPTAS 不保证近似 C PTAS 比 FPTAS 更近似 D FPTAS 的复杂度是 n 与 1/ε 的多项式，PTAS 中 ε 可进入指数 ✓ 正确答案
# 61. 线段树懒标记（lazy propagation）在范围更新的必要性 A 让查询更快 B 把整段更新合并为 O(1) 标记，下推时再更新，使区间更新 O(log n) ✓ 正确答案 C 不需要下推 D 减少构建时间
# 64. ODT 用 set 存储连续同值区间及合并/分裂的实现 A 直接二分 B 先 split(l) 与 split(r+1)，删除区间后插入新区间 ✓ 正确答案 C 遍历所有区间 D 重建整棵树
