2026年谷歌全球编程挑战赛Google-Code-Jam试题详解

2026年谷歌全球编程挑战赛GoogleCodeJam试题详解第一部分：算法设计（共3题，每题15分）题目1（15分）：多路径最短路径问题背景：在城市交通网络中，某些路口可能存在多条路径可达同一目的地。交通管理部门需要计算从起点到终点的最短路径，且要求路径上的交通拥堵程度最低。拥堵程度由路径上经过的路口数量决定。问题描述：给定一个无向图，节点表示路口，边表示道路，每条边有权重（表示拥堵程度，权重越小表示拥堵越轻）。请设计算法，在所有从起点`S`到终点`T`的路径中，选择一条经过路口数量最少且总拥堵程度最低的路径。如果存在多条满足条件的路径，选择经过路口数量最少的路径。输入：-第一行：`N`（路口数量，1≤N≤1000），`M`（道路数量，1≤M≤5000），`S`（起点），`T`（终点）。-接下来`M`行，每行三个整数`u`、`v`、`w`（表示节点`u`和`v`之间有一条权重为`w`的边）。输出：-一行，输出满足条件的路径经过的路口数量。如果没有满足条件的路径，输出`-1`。示例：输入：4514121231341133242输出：3解析：-可能的路径有：`1-2-3-4`（经过路口数量3，总拥堵程度1+1+1=3）、`1-3-4`（经过路口数量3，总拥堵程度3+1=4）、`1-2-4`（经过路口数量3，总拥堵程度1+2=3）。-最优路径为`1-2-3-4`，拥堵程度最低且经过路口数量最少。题目2（15分）：动态任务分配问题背景：某公司需要分配任务给多个员工，每个任务有不同的完成时间和优先级。员工可以同时处理多个任务，但每个任务只能由一个员工完成。目标是最大化所有任务的总优先级之和。问题描述：给定`N`个任务和`M`个员工，任务`i`的完成时间为`t_i`，优先级为`p_i`；员工`j`的处理能力为`c_j`（表示最多能同时处理的任务数量）。请设计算法，为每个任务分配一个员工，使得在不超过每个员工处理能力的条件下，任务的总优先级之和最大。输入：-第一行：`N`（任务数量，1≤N≤200），`M`（员工数量，1≤M≤100）。-第二行：`t1t2...tN`（任务完成时间）。-第三行：`p1p2...pN`（任务优先级）。-第四行：`c1c2...cM`（员工处理能力）。输出：-一行，输出最大化的总优先级之和。如果没有满足条件的分配方案，输出`0`。示例：输入：3223110203022输出：50解析：-员工1和员工2都能同时处理最多2个任务。-最优分配：员工1处理任务1（时间2，优先级10）和任务3（时间1，优先级30），员工2处理任务2（时间3，优先级20）。-总优先级：10+30+20=60。题目3（15分）：区间覆盖问题背景：某城市需要为市民提供公共医疗服务，服务点覆盖一定的时间区间。目标是覆盖最多市民，且覆盖时间尽可能紧凑。问题描述：给定`K`个服务点，每个服务点有一个覆盖区间`[s_i,e_i]`。请设计算法，选择一个服务点的子集，使得所有被覆盖的时间区间不重叠，且覆盖的总时间最长。输入：-第一行：`K`（服务点数量，1≤K≤300）。-接下来`K`行，每行两个整数`s_i`、`e_i`（表示服务点的覆盖区间）。输出：-一行，输出最大的覆盖时间。如果没有满足条件的覆盖方案，输出`0`。示例：输入：4142536710输出：4解析：-最优选择区间`[1,4]`和`[7,10]`，总覆盖时间4+3=7。-其他组合如`[2,5]`和`[7,10]`覆盖时间5+3=8，但题目要求不重叠，因此选择`[1,4]`和`[7,10]`。第二部分：数据结构（共2题，每题20分）题目4（20分）：动态树形结构问题背景：某公司组织架构为树形结构，节点表示员工，边表示上下级关系。需要动态维护树形结构，支持插入、删除和查询操作。问题描述：设计一个数据结构，支持以下操作：1.`INSERT(u,v)`：在节点`u`和`v`之间添加一条边（`u`为`v`的父节点）。2.`DELETE(v)`：删除节点`v`及其所有子节点。3.`QUERY(u)`：查询节点`u`的深度（根节点深度为0）。输入：-第一行：`Q`（操作数量，1≤Q≤10000）。-接下来`Q`行，每行一个操作，格式为：-`1uv`：插入操作。-`2v`：删除操作。-`3u`：查询操作。输出：-对于每个查询操作，输出节点`u`的深度。示例：输入：5112312212333输出：010解析：-初始树：`1`为根节点。-操作1：插入`2`为`1`的子节点。-操作2：查询`1`的深度，输出`0`。-操作3：删除`2`及其子节点，树为空。-操作4：插入`3`为`2`的子节点（此时`2`已删除，操作无效）。-操作5：查询`3`的深度，输出`0`。题目5（20分）：滑动窗口最大值问题背景：某公司需要实时监控股票价格，每次价格更新后，需要查询最近`K`个价格中的最大值。问题描述：设计一个数据结构，支持以下操作：1.`ADD(x)`：添加一个新价格`x`。2.`MAX(K)`：查询最近`K`个价格中的最大值。输入：-第一行：`N`（价格数量，1≤N≤100000），`K`（窗口大小，1≤K≤N）。-接下来`N`行，每行一个整数`x`（价格）。输出：-对于每个`MAX(K)`查询，输出最近`K`个价格中的最大值。示例：输入：8313-1-35367输出：335367解析：-价格序列：`[1,3,-1,-3,5,3,6,7]`。-查询1：最近3个价格`[1,3,-1]`，最大值`3`。-查询2：`[3,-1,-3]`，最大值`3`。-查询3：`[-1,-3,5]`，最大值`5`。-查询4：`[-3,5,3]`，最大值`5`。-查询5：`[5,3,6]`，最大值`6`。-查询6：`[3,6,7]`，最大值`7`。第三部分：数学与逻辑（共1题，25分）题目6（25分）：组合数动态规划问题背景：某公司需要从`N`个候选人中选择`K`人组成一个团队，每个候选人有不同的能力值。需要选择一个团队，使得团队的总能力值为`S`，且团队成员的能力值尽可能分散（即相邻成员的能力值之差最小）。问题描述：给定`N`个候选人的能力值`a1,a2,...,aN`，以及`K`和`S`，请设计算法：1.选择`K`个人，使总能力值为`S`。2.在所有满足条件的团队中，选择能力值之差最小的团队。输入：-第一行：`N`（候选人数量，1≤N≤50），`K`（团队人数，1≤K≤N），`S`（总能力值，1≤S≤2500）。-第二行：`a1a2...aN`（能力值）。输出：-一行，输出满足条件的团队中能力值之差的最小值。如果没有满足条件的团队，输出`-1`。示例：输入：531012345输出：1解析：-可能的团队：-`[1,2,7]`：能力值之差最大为6。-`[1,3,6]`：能力值之差最大为5。-`[1,4,5]`：能力值之差最大为3。-`[2,3,5]`：能力值之差最大为2。-最优团队为`[2,3,5]`，能力值之差最小为2。答案与解析第一部分：算法设计题目1-输入：`4514`边：`1-2-1`，`2-3-1`，`3-4-1`，`1-3-3`，`2-4-2`。-过程：-使用Dijkstra算法计算从`S`到`T`的最短路径，优先队列按拥堵程度排序。-可能路径：`1-2-3-4`（拥堵3），`1-3-4`（拥堵4），`1-2-4`（拥堵3）。-最优路径为`1-2-3-4`，经过路口数量3。-输出：`3`。题目2-输入：`32`，`231`，`102030`，`22`。-过程：-员工1和员工2处理能力均为2。-最优分配：员工1处理任务1（10）和任务3（30），员工2处理任务2（20）。-总优先级：10+30+20=60。-输出：`60`。题目3-输入：`4`，`[1,4]`，`[2,5]`，`[3,6]`，`[7,10]`。-过程：-最优选择区间`[1,4]`和`[7,10]`，总覆盖时间4+3=7。-输出：`7`。第二部分：数据结构题目4-操作序列：`112`，`31`，`22`，`123`，`33`。-过程：-树结构动态变化，查询深度时按当前树结构计算。-输出：`0`，`1`，`0`。题目5-输入：`83`，`[1,3,-