360 笔试编程题思路：一笔画无向图与打车最小花费

《面试题目》

1. 一笔画无向图：求可能的落点以及落点个数（数据规模 1e5）。
2. 打车问题：cost = x > b ? base + k * (x - b) : base，给定 n 条边花费时间和 n 个点花费时间，可以在点上下车然后打车到另一个点，求最小花费时间（数据规模 1e6）。

《参考解析》

一笔画问题的本质是欧拉路径。「一笔画」能否完成，等价于图里是否存在一条经过每条边恰好一次的路径（欧拉通路）或回路（欧拉回路）。判定条件只有两条：一是忽略孤立点后图必须连通；二是奇度顶点的个数只能是 0 或 2。奇度点为 0 时存在欧拉回路，路径的起点可以选任意一个度大于 0 的点，终点回到起点；奇度点为 2 时存在欧拉通路，起点和终点必须是那两个奇度点，顺序可以互换。「求可能的落点以及落点个数」这句话正对应这两种情形：如果 n 个点里奇度点的个数是 0，落点范围就是所有有边的点（回路起点任选），个数按度大于 0 的点统计；如果是 2，落点集合就是这两个奇度点，个数为 2；其他情况（奇度点个数为奇数、或图不连通、或没有任何边）则不存在一笔画，答案为 0 或按题面约定返回。数据规模到 1e5，实现上有几个必须注意的点：邻接表建图而不是邻接矩阵；判连通用 BFS 或迭代 DFS，别用递归（1e5 的链状图会直接爆栈）；点和边的编号范围要先读清，孤立点是否计入答案要按题面确认；如果同时要求输出路径，用 Hierholzer 算法配显式栈，复杂度 O(V + E)。

打车题的状态与转移。题意是：一段路程由若干条边（每条边有通行耗时）和若干点（每个点有耗时）组成，可以在某个点下车、另打一辆车到另一个点，打车费用按分段函数计：距离（或时间）x 不超过阈值 b 时收固定 base，超过部分按每单位 k 计，要最小化总时间或总花费。这类题的标准解法是 DP：设 dp[i] 表示到达第 i 个点时的最优值，转移枚举「上一次换乘的点 j」，代价由「从 j 到 i 的路径代价 + 一次打车的费用」构成，也就是 dp[i] = min(dp[j] + cost(j, i))。朴素转移是 O(n^2)，而分段计费函数恰好可以拆成「固定项 + 与距离线性相关的项」，路径代价又可以用前缀和预处理成 O(1) 查询，于是转移中对 j 的枚举里与 i 无关的部分可以提取出来，只维护一个随 i 变化的最小值（也就是维护「前面所有 j 的最优值减去它们的前缀代价」这个量），就能把整体压到 O(n)。帖主说的「要么不下要么下，求 max，可以前缀和优化」正是这个结构，只是最优化方向要按题面确认是最小化时间还是最小化花费。

1e6 的数据量下还要注意：用快读（或语言自带的高效输入）避免 IO 超时，结果用 64 位整数（费用累加可能超出 int），滚动数组或就地更新把空间控制在 O(n) 以内。

分段函数本身的处理细节。cost = x > b ? base + k * (x - b) : base 是一个在 x = b 处连续但斜率突变的函数（左段斜率为 0、右段斜率为 k），这类函数在 DP 里的好处是能用一次函数分解：拆成「base - k * b」（当 x > b，为一个常数）加「k * x」，于是转移式子对 j 的依赖只剩常数项与 x_j 的线性项，前缀和与单调队列都能用上。要注意的两个坑：x 可能恰好等于 b，判断用 > 还是 >= 结果一样但别写反；以及如果题目里的「距离」是边权之和而不是时间，前缀和要建在边权上，点数与边数差 1，下标容易错位。

这类笔试的心态与策略。帖主自述「白天上班已经给大脑燃尽，就写个思路不想写题了」，这其实是多数在职或实习候选人参加秋招笔试的真实状态。现实一点的做法是：笔试前把这类高频模板（欧拉路径判定、区间 DP、前缀和优化的一维 DP、贪心与二分的组合）各自手写一遍留档，考场上直接改模板而不是从零推导；遇到思路已经清楚但代码量大的题，先把核心转移写出来跑样例，再补边界；如果当天状态确实差，也要保证提交一版能通过部分用例的代码，部分分在总分里往往决定能不能进面。复盘时把「思路对、代码没写完」和「思路就错了」分开记录，前者靠模板熟练度解决，后者才需要补知识点。