WZOIMonthly 模拟试题：好感统计与慢跑问题

"Problem Day2.pdf 是一份模拟试题，包含了两道题目，主要涉及的算法知识点有二分查找、单源最短路以及有向无环图（DAG）上的动态规划。第一题‘好感统计’是一个组合优化问题，要求根据女生间的好感度计算可以组成参赛队伍的数量。第二题‘慢跑’的背景信息不完整，可能是关于路径规划或时间计算的问题。" 在第一题“好感统计”中，我们需要解决的是一个基于条件的组合计数问题。给定N个女生，每个女生有一个好感度Ai，并且只有当两个女生的好感度之和大于S时，她们才能组成一组参加比赛。目标是找出所有可能的合法组队方式数量。 为了解决这个问题，我们可以采用二分查找的方法。首先，我们对所有女生的好感度进行排序。然后，对于每个可能的值x（x从S到2 * max(Ai)），我们查找数组中是否存在一个女生，其好感度与x之和大于S。如果存在这样的女生，我们可以递减地在数组中寻找另一个女生，使得两者的好感度之和等于x。这个过程可以通过单源最短路算法实现，例如Floyd-Warshall或者Dijkstra算法，但在这种情况下，由于数据规模较小且数组有序，简单使用二分查找和线性扫描可能更为高效。 具体步骤如下： 1. 对好感度数组进行排序。 2. 使用二分查找找到所有可能的组合之和x，使得存在两个女生的好感度之和等于x。 3. 对于每个找到的x，从最高好感度的女生开始，检查是否能找到一个好感度为x - Ai的女生，使得Ai + (x - Ai) > S。 4. 计算满足条件的组队数量并累加。 在给定的数据规模范围内，需要确保算法能够在规定的时间限制内完成，即对于100%的数据，在1秒内完成计算。对于较大的数据集，可能需要考虑更高效的算法优化，如位运算或前缀和等技术来减少计算量。 第二题“慢跑”的具体问题描述不全，但从背景描述中可以推测，这可能是一个关于路径选择或时间规划的问题，可能涉及到在给定限制下找到最佳的跑步路线。可能需要利用动态规划在DAG上进行状态转移，找到最优解。但由于信息不足，无法提供更详细的解答。如果需要详细解答第二题，需要完整的题目描述。