AtCoder Beginner Contest 405 A-D题解

-> 链接 <-

A - Is it rated?

模拟

Code

B - Not All

用一个数组记录每个数出现的次数，然后遍历数组，如果某个数出现的次数大于1，则输出该数。

Code

C - Sum of Product

题目分析

给长度 $N$ 的数组 $A$ ，求 $\displaystyle \sum_{1\leq i< j\leq N}A_iA_j$ 。

解题思路

先从样例一入手

3
4 2 3

表示为

$$\displaystyle \sum_{1\leq i< j\leq N} A_iA_j=A_1A_2+A_1A_3+A_2A_3$$

根据乘法结合律

$$\displaystyle \sum_{1\leq i< j\leq N} A_iA_j=A_1A_2+A_1A_3+A_2A_3= A_1(A_2+A_3)+A_2A_3$$

发现

$$\displaystyle \sum_{1\leq i< j\leq N} A_iA_j=\sum_{1\leq i\leq N}(A_i(\sum_{i+1\leq j\leq N}A_j))$$

用 前缀和 可以计算出 ${\displaystyle \sum_{i+1\leq j\leq N}}A_j$

代码实现

Code

D - Escape Route

比C简单，bfs即可，注意反方向打箭头。

Code