AtCoder Beginner Contest 058(ABCD)
A - ι⊥l
思路：特判
B - ∵∴∵
思路：模拟
C - Dubious Document
思路：暴力统计下每个字母出现的最小次数，然后排序。
D -
求和优化。
我的公式：考虑包含某个 y i y_i yi 出现的所有对的贡献分类求和。
s y = ∑ i = 2 m − ( m − i + 1 ) × y i − 1 s_y=sum_{i=2}^m-(m-i+1)times y_{i-1} sy=∑i=2m−(m−i+1)×yi−1
s x s_x sx同理。
最后答案即： s x × s y s_xtimes s_y sx×sy
更优的方法：考虑成对出现的次数。
如 x 1 , x n x_1,x_n x1,xn都出现 n − 1 n-1 n−1次，所以 ( x n − x 1 ) (x_n-x_1) (xn−x1)贡献是： ( n − 1 ) × ( x n − x 1 ) (n-1)times(x_n-x_1) (n−1)×(xn−x1)
x 2 , x n − 1 x_2,x_{n-1} x2,xn−1都出现 n − 2 n-2 n−2次，所以 ( x n − 1 − x 2 ) (x_{n-1}-x_2) (xn−1−x2)贡献是： ( n − 2 ) × ( x n − 1 − x 2 ) (n-2)times(x_{n-1}-x_2) (n−2)×(xn−1−x2)
依次类推求和即可。
最后
以上就是稳重钢笔最近收集整理的关于AtCoder Beginner Contest 058(ABCD)的全部内容，更多相关AtCoder内容请搜索靠谱客的其他文章。
发表评论 取消回复