拼多多9月6日机考笔试面经

《面试题目》

1. 彩门按不同绶带阈值排列、只能在两端换向时，至少需要换向多少次才能全部揭开？哪些情况无论如何都无法完成？
2. 如何统计重量和为装载模数倍数的无序货物对？
3. 图中存在步行边和零耗时罐笼边，且罐笼最多乘坐 c 次、两次乘坐之间必须步行时，如何求最短耗时？
4. 如何统计括号匹配区间内部长度满足模数条件的区间数量？
5. 如何在周期数组上计算所有区间的周期相位贡献？

《参考解析》

1. 按当前方向走到端点，遇到阈值不超过当前绶带数的门就立即揭开；整趟没有新增门时说明剩余阈值都不可达，应返回 -1。每次有进展再换向，提前掉头不会减少换向次数。
2. 只统计每个重量对模数的余数。余数 r 与 t-r 配对，余数 0 以及偶数模数下的 t/2 只能在本类内部组合，使用组合数并保证每类只计算一次。
3. 将状态扩展为“当前位置、已乘罐笼次数、上一条边是否为罐笼”，步行边转移时清除连续乘坐标记，罐笼边只有在次数未达上限且上一条不是罐笼时才能转移，再用 Dijkstra 求状态图最短路。
4. 用栈保存尚未匹配的左括号。遇到右括号弹出栈顶，内部长度为右端下标减左端下标再减一，检查该长度对模数取余是否为零。
5. 先按周期对位置分类并计算后缀计数，再按相位差合并贡献；枚举每个周期长度时只处理互补相位，避免重复计算，整体可用调和级数控制复杂度。