AtCoder Beginner Contest 405

A，B

H₂O题，秒。
C

发现如果枚举两个数会超时，但如果枚举它们的值却不会超时。
于是我们可以先记录每个值有几个数，再枚举 \(1\sim 10^4\) 的第一个数 \(a\)。
先特判掉两个数相同的情况，贡献数量为 \(\frac{cnt_a*(cnt_a-1)}{2}\)，贡献数为 \(\frac{cnt_a*(cnt_a-1)}{2}a^2\)。
接下去再枚举 \(a+1\sim 10^4\) 的第二个数 \(b\)，贡献数量为 \(cnt_a\times cnt_b\)。
这样循环次数为 \(5\times10^7\) 左右，可以通过本题

赛后看别人题解才知道这道题可以将原始变为： $$\sum_{i=2}^{n} a_i\times(\sum_{j=1}^{i-1}a_j)$$
之后在用前缀和求解即可

D

首先，可以想到如果从每个点出发搜索到安全出口，其时间复杂度是远远不如从安全出口搜索到每个点的，并且两者的结果等价，不过是要将输出的方向反以下而已。
接下去我们可以发现这道题属于多源搜索，一般使用 BFS。接下去我们就可以发现只要在 BFS 过程中记录下到安全出口的距离，每次判断当前距离是否小于记录的距离，如果小于则更新距离和方向即可。
后面的题作者没有写，请尽情谅解

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！