广告最多的网站,响应式自助建站平台,餐饮网站开发,自己做的表白网站第 1 题 【 问答题 】 • 最短路径问题 平面上有n个点(n100)#xff0c;每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。 若有连线#xff0c;则表示可从一个点到达另一个点#xff0c;即两点间有通路#xff0c;通路的距离为两点间的直线距离。现在的任务…第 1 题 【 问答题 】 • 最短路径问题 平面上有n个点(n100)每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。 若有连线则表示可从一个点到达另一个点即两点间有通路通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。 时间限制1000 内存限制131072 输入 共nm3行其中: 第一行为整数n。 第2行到第n1行(共n行) 每行两个整数x和y描述了一个点的坐标。 第n2行为一个整数m表示图中连线的个数。 此后的m 行每行描述一条连线由两个整数i和j组成表示第i个点和第j个点之间有连线。 最后一行两个整数s和t分别表示源点和目标点。 输出 仅一行一个实数(保留两位小数)表示从s到t的最短路径长度。
样例输入 5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5 样例输出 3.41 第 2 题 【 问答题 】 • Freda的越野跑(2023.3) Freda报名参加了学校的越野跑。越野跑共有N人参加在一条笔直的道路上进行。这N个人在起点处站成一列相邻两个人之间保持一定的间距。比赛开始后这N个人同时沿着道路向相同的方向跑去。换句话说这N个人可以看作x轴上的N个点在比赛开始后它们同时向x轴正方向移动。 假设越野跑的距离足够远这N个人的速度各不相同且保持匀速运动那么会有多少对参赛者之间发生“赶超”的事件呢? 时间限制1000 内存限制262144 输入 第一行1个整数N。 第二行为N 个非负整数按从前到后的顺序给出每个人的跑步速度。 对于50%的数据2N1000。 对于100%的数据2N100000。 输出 一个整数表示有多少对参赛者之间发生赶超事件。
样例输入 5 1 3 10 8 5 样例输出 7 提示 我们把这5个人依次编号为A,B,C,D,E速度分别为1,3,10,8,5。 在跑步过程中 B,C,D,E均会超过A因为他们的速度都比A快; C,D,E都会超过B因为他们的速度都比B快; C,D,E之间不会发生赶超因为速度快的起跑时就在前边。 第 3 题 【 问答题 】 • 社交网络 随着社交平台的兴起人们之间的沟通变得越来越密切。通过Facebook的分享功能只要你是对方的好友你就可以转发对方的状态并且你的名字将出现在“转发链”上。经过若干次转发以后很可能A分享了一条好友C的状态而C的这条状态实际上是分享B的但A与B可能并不是好友即A通过C间接分享了B的状态。 给定你N个人之间的好友关系好友关系一定是双向的。只要两个人是好友他们就可以互相转发对方的状态无论这条状态是他自己的还是他转发了其他人的。现在请你统计对于每两个人他们是否有可能间接转发对方的状态。 时间限制1000 内存限制262144 输入 第一行1个整数N(1N300)。 接下来N行每行N个整数表示一个NN的01矩阵若矩阵的第i行第j列是1表示这两个人是好友0则表示不是好友。 保证矩阵的主对角线上都是1并且矩阵关于主对角线对称。 输出 一个NN的01矩阵若矩阵的第i行第j列是1表示这两个人可能间接转发对方的状态0则表示不可能。
样例输入 5 11000 11100 01100 00011 00011 样例输出 11100 11100 11100 00011 00011 提示 在输入数据中1与2是好友2与3是好友4与5是好友。 因此1、2、3有可能互相转发状态;4、5有可能互相转发状态。这两组人之间则不可能。 第 4 题 【 问答题 】 • 旅行 转眼毕业了曾经朝夕相处的同学们不得不都各奔东西大家都去了不同的城市开始新的生活。在各自城市居住了一段时间后他们都感到了一些厌倦想去看看其他人的生活究竟如何于是他们都选择到另一个同学所在城市去旅游并且希望旅游的城市各不相同他们想知道有多少种不同的方案可是数量实在太多了他们无法计算出来你能帮助他们吗。 时间限制10000 内存限制131072 输入 一个正整数n(n200)表示人数。 输出 一个数表示有多少不同的方案。
样例输入 3 样例输出 2 提示 有如下两种方案 同学1去同学2的城市同学2去同学3的城市同学3去同学1的城市; 同学1去同学3的城市同学3去同学2的城市同学2去同学1的城市。
