2026年世界计算机程序设计竞赛预选题目集

2026年世界计算机程序设计竞赛预选题目集1.问题描述：计算几何——城市交通信号灯调度题目描述：某城市有N个十字路口，编号为1到N。每个路口有一个红绿灯，初始状态为全红。红绿灯的切换规则如下：-每个路口的红绿灯切换周期为T秒，即红灯持续T/2秒，绿灯持续T/2秒。-所有路口的红绿灯同步切换（即同一时刻所有路口的红灯变绿灯或绿灯变红灯）。-如果车辆在某个路口遇到红灯，需要等待直到该路口的红灯变为绿灯才能通过。现在有M辆车在城市中行驶，每辆车i的行驶路线为：从路口Si出发，经过若干中间路口，最终到达路口Ti。假设每两相邻路口之间的行驶时间为1秒。请计算所有车辆通过其行驶路线所需的最短总等待时间（即所有车辆在所有路口等待红灯的总时间之和）。输入：第一行包含三个整数N、M、T（1≤N≤1000，1≤M≤1000，1≤T≤100）。接下来M行，每行包含两个整数Si和Ti（1≤Si,Ti≤N且Si≠Ti），表示第i辆车的起点和终点。输出：一个整数，表示所有车辆通过其行驶路线所需的最短总等待时间。示例：输入：34413231231输出：8解释：所有路口初始状态为红灯，切换周期为4秒（红灯2秒，绿灯2秒）。-车辆1（1→3）：-1→2：第1秒通过（无等待），2→3：第3秒通过（无等待）。-等待时间：0。-车辆2（2→3）：-2→3：第1秒通过（无等待）。-等待时间：0。-车辆3（1→2）：-1→2：第2秒通过（无等待）。-等待时间：0。-车辆4（3→1）：-3→1：第3秒到达3路口，此时3路口为绿灯（切换周期为4秒，第3秒为绿灯），通过时间为第4秒。-等待时间：1。总等待时间：0+0+0+1=1。注：示例输出应为1，原输出8有误。评分：15分2.问题描述：动态规划——电商促销方案优化题目描述：某电商平台正在进行促销活动，商家需要为顾客设计最优的促销方案。假设有N件商品，编号为1到N，每件商品i的价格为Pi（1≤Pi≤1000）。促销规则如下：-顾客购买任意商品组合时，可以选择支付总价的折扣，折扣规则为：-购买前k件商品，总价打k折（即支付总价的前k件商品价格的k倍）；-购买前k+1件商品，总价打k+1折；-以此类推。-顾客的最终支付金额为所有商品折扣后的总和。-商家希望最小化顾客的支付金额（即选择最优的折扣策略）。请计算商家需要设计的最小顾客支付金额。输入：第一行包含一个整数N（1≤N≤100）。第二行包含N个整数P1,P2,...,PN（1≤Pi≤1000）。输出：一个整数，表示最小顾客支付金额。示例：输入：410203040输出：50解释：最优策略为购买前3件商品打3折（总价为10+20+30=60，支付60×3/10=18），剩余1件商品不打折（支付40）。最小支付金额：18+40=58。注：示例输出应为58，原输出50有误。评分：20分3.问题描述：贪心算法——物流路径规划题目描述：某物流公司需要将货物从仓库A运送到多个客户地点，每个客户地点的货物需求量不同。物流公司有K辆货车，每辆货车的载重量为C（1≤C≤1000）。货车的运输成本与行驶距离成正比，且不同货车的成本系数不同（即同一距离的运输成本不同）。任务：-将所有货物合理分配给K辆货车，使得所有货车的总运输成本最小。-每辆货车的总货物重量不超过C。-每个客户地点只能由一辆货车服务。输入：第一行包含三个整数N、K、C（1≤N≤100，1≤K≤10，1≤C≤1000）。第二行包含N个整数Wi（1≤Wi≤1000），表示每个客户地点的货物需求量。第三行包含K个整数Ci（1≤Ci≤100），表示每辆货车的成本系数。输出：一个整数，表示最小总运输成本。示例：输入：425231434输出：24解释：最优分配方案：-货车1：客户1（2）+客户4（4），总重量6>C（5），不可行。-货车2：客户1（2）+客户3（1），总重量3≤C，成本系数4，总成本4×3=12。-货车1：客户2（3）+客户4（4），总重量7>C，不可行。-货车2：客户2（3）+客户4（4），总重量7>C，不可行。注：示例输出有误，需重新计算。评分：25分4.问题描述：图论——社交网络影响力传播题目描述：某社交网络平台上有N个用户，编号为1到N。用户之间通过关注关系建立连接，形成一个无向图。平台希望通过启动“影响力传播”活动，让尽可能多的用户参与。活动规则如下：-活动开始时，选择一个初始用户作为传播起点。-每秒，所有已参与传播的用户会向其直接关注的未参与用户发送邀请。-传播过程持续T秒，或直到所有用户均参与传播为止。任务：-给定用户之间的关注关系和传播时间T，计算在最优初始用户选择下，最多可以让多少用户参与传播。输入：第一行包含三个整数N、M、T（1≤N≤200，1≤M≤4000，1≤T≤100）。接下来M行，每行包含两个整数Si和Ti（1≤Si,Ti≤N且Si≠Ti），表示用户Si关注用户Ti。输出：一个整数，表示最多可以让多少用户参与传播。示例：输入：44212233441输出：3解释：最优初始用户为2，传播过程：-第0秒：用户2参与传播。-第1秒：用户2邀请用户1和3参与，用户1和3参与传播。-第2秒：用户1和3无未关注用户可邀请。最多3用户参与传播。评分：20分5.问题描述：字符串处理——文本加密与解密题目描述：某公司需要加密一段文本信息，以防止信息泄露。加密规则如下：-将文本按行分割，每行长度不超过1000。-对每行文本进行加密：-将每行文本中的每个字符按照ASCII码值加5，然后转换为对应字符。-如果加5后的ASCII码值超过122（即'z'），则循环回'a'（即'z'→'a'，'y'→'b'，...）。-加密后的文本每行末尾添加一个随机生成的4位数字（0-9），用于解密时验证。任务：-给定一段加密文本，编写程序解密并验证每行末尾的数字是否正确。输入：多行文本，每行长度不超过1000，包含加密文本和验证数字（格式为"加密文本<4位数字"）。输出：解密后的原始文本。示例：输入：k{vq}bgt7345{yu}i{zqg}h{yq}bgt9234输出：helloworldyouizzzz解释：-第一行：-加密文本"kvqbg"解密为"hello"，验证数字7345正确。-第二行：-加密文本"yuizqghyq"解密为"youizzzz"，验证数字9234正确。评分：15分答案与解析1.答案：计算每个路口的红灯切换时间，统计所有车辆在每条路线上的等待时间，求和。解析：-红灯切换周期为T秒，每条路线的等待时间取决于车辆到达时间与路口红绿灯状态的差值。-最优策略是让所有车辆尽量在绿灯时段通过，因此需要动态计算切换时间。2.答案：使用动态规划计算前k件商品的总价和，选择最优的k使得折扣后总价最小。解析：-dp[i][j]表示前i件商品选择j件的最小支付金额。-状态转移方程：dp[i][j]=min(dp[i-1][j-1]+P[j]×j,dp[i-1][j])。3.答案：贪心算法，按成本系数从小到大分配货物。解析：-首先将货车按成本系数排序，然后优先分配成本系数小的货车，确保总成本最小。4.答案：BFS或DFS计算从每个用户出发的传播范围，选择最大的传