GESP 8级编程题 求做法
2025-12-28 09:00:35
发布于:广东
T1
个点, 条边的带权无向图。
其中,猫窝在 点,老鼠洞在 点。
定义一个节点 是安全的,当且仅当:
- 可以找到一条从 到 的路径,为了方便描述,定义这条路径为 其路径长度为 。使得从对于每个 到 的 最短路 严格大于 沿着这条路径走到第 个节点的路径总长度。
第 个节点有 个积分,求所有安全节点的积分总和。
第一行 。
第二行
接下来 行,每行三个正整数 描述一条 长度为 的边。
输出安全节点积分和。
输入
5 5 1 2
1 2 4 8 16
1 2 4
3 1 8
2 5 2
2 3 3
3 4 3
输出
22
。
T2
给定一个长度为 的 环形数组 。
有一个给定的数 ,满足 。
要求分割这个数组,使得分出来的每一段都包含 。
求最多分割几段。
输出答案。
输入1
6 2
1 2 1 2 1 2
输出1
3
输入2
7 3
3 1 3 1 2 1 2
输出2
2
sjfw
保证 都至少在 中出现过一次。
全部评论 3
T1跑dijkstra求猫的最短路cat[],再跑dijkstra求所有安全点,边权按照cat[u]-mouse[u]排序
T2先用map跑一遍,每个段放到vector<map<int,int>>里,然后尝试把最前面的扔到结尾1周前 来自 北京
01周前 来自 北京
0在看,但是T1Q群里有人出了trick
1周前 来自 广东
0T1 条件转化为 dis_{a,b}>dis_{u,b} 则 u 是安全节点
1周前 来自 广东
0
看QQ
1周前 来自 浙江
0其实并不严谨,少了a,b的范围
1周前 来自 浙江
0还有w的范围,这个非常重要,决定能不能用dij
1周前 来自 浙江
0w写了
1周前 来自 广东
0显然不可能小于 把
1周前 来自 广东
0



















有帮助,赞一个