2023年威海市中小学生编程挑战赛中学组解题思路

T1

本题是一个模拟题，没有其他，按题目描述仔细实现即可，注重细节，多多调试。

T2

题目大意：

数各不相同长度为 $n$ 的序列 $A$，求：$\min\limits_{1 \le j < i} |A_i-A_j|$ ，以及令上式取到最小值的 $j$。若最小值点不唯一，则选择使 $A_j$ 较小的那个。$n <= 10^5,|A_i| \le 10^9$

思路

朴素做法： i 从 2 开始枚举到 n，每个 i 再枚举 j 从1 到 i - 1，寻找最小的 $|A_i-A_j|$， 如果有相等的，则找 $A_j$ 较小的那个，两层 for 循环。时间复杂度 $O(n^2)$，部分测试点超时。

优化： 考虑到第二层 for 循环每次都从1开始到i，如果我们能在$O(log_2n)$时间实现查找 $A_j$的话，这题就完美解决了。这样时间复杂度的算法我们可能最先想到二分，但是二分的前提是数组有序，这里不适合；我们考虑维护一个二叉搜索树（BST），$O(log_2n)$插入，$O(log_2n)$查找。另一种数据结构是STL中的set也可以实现。总体时间复杂度 $O(nlog_2n)$。

另在数据范围中提到一个特殊性质，数列A单调不降，因数各不相同，也就是单调递增。通过链表等也能实现解决本题，我这里只提个思路，就不展开了，有兴趣的同学可以去尝试。

T3

题目大意

n 道 OI 比赛试题，总时间 t，以及 n 行 $W_{1i}、T_{1i}​、W_{2i}、T_{2i}$， 分别表示第 i 题：完全正确做出来的得分，完全正确做出来所花费的时间，“骗”来的分数，“骗”分所花费的时间，求在 t 时间内所能得到的最高分。$3 ≤N ≤40，2 ≤T ≤ 1080000，1 ≤ W_{1i} 、W_{2i} ≤ 30000，1 ≤ T_{1i} 、T_{2i} ≤ T$。

思路:

考虑每一题，我们可以选择不做，完全做和骗分做这三种情况，我们可以写一个dfs来进行搜索，大体上长这个样子

void dfs(int step, int leftTime, int scoreSum)
{
      if(step > n) {找到最大的得分；return;}
      dfs(step + 1, leftTime, scoreSum);//不做step此题
      dfs(step + 1, leftTime - t1[step], scoreSum + w1[step]); // 安全正确做
      dfs(step + 1, leftTime - t2[step], scoreSum + w2[step]); // 骗分做
}

其中step看作是第i题，leftTime表示还有多少时间剩余，scoreSum表示处理完了 step - 1 道题后总共得了多少分。dfs中间还有一些小细节要处理一下。这样做的话能得40%的部分分。

考虑其他超时部分怎么优化，可以简单将此dfs修改成记忆化搜索，大体上长这个样子 int dfs(int step, int leftTime),表示在处理第 step 道题，剩余 leftTime 时间能得到的分数。当然也可以直接把此记忆化搜索改成递推的形式，这就是一个变形的背包问题了。当然搜索的形式也可以直接使用背包的状态定义来进行，就是可能刚开始学的时候不太好理解。