• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

快乐的一天从AC开始 | 20210808 | CF1554B

admin

11月 28, 2021

题目链接

每日吐槽

心路历程

我怎么连Div2. B都做不出来了呀

思路

(f(i, j) = i * j – k (a_i | a_j), i < j)

对于所有可能的(a_i)取值,(f(n – 1, n) in [n^2 – n – 2kn, n^2 – n])(f(i, n) in [ni – 2kn, ni]),则(f(i, n) > f(n – 1, n) Leftrightarrow i > n – 2k – 1)

然后就可以枚举右端点,对于每个右端点,可能的左端点最多只有(O(k))个。

然后直接暴力枚举,时间复杂度(O(kn))

发表评论

您的电子邮箱地址不会被公开。