• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Codeforces Round #725 (Div. 3) 题解(A-G)

开发技术 开发技术 2天前 5次浏览

A. Stone Game

注意(a_i)是互不相同的,所以可以直接得到两个极值的位置。

然后最优的方案必定是一下三种中的一种:

  • 仅从左侧删除,直到删掉两个极值
  • 仅从右侧删除,直到删掉两个极值
  • 两边都删除,每边一删掉一个极值就停

都计算一下取最小值即为答案。

B. Friends and Candies

当且仅当(n nmid sum_{i = 1}^n a_i)时无解。

假设(n)人的平均为(t),那么只把(a_i > t)的元素选出来平均即为最优方案。

C. Number of Pairs

智商不够,DS来凑。

注意到要求(i < j),所以逆着处理。用一个平衡树保存已经处理过的值,然后当前元素对答案的贡献就是平衡树中([l – a_i, r – a_i])内值的个数。

D. Another Problem About Dividing Numbers

(k = 1)时直接特判,注意(a = b)时的情况。

其余情况,由于只限制了(c > 1),所以不妨把目标定为把(a, b)都变成1。

(x)的质因数分解为(x = sum_i p_i^{e_i}),那么(x)至多只能操作(sum_i e_i)次,记这个操作次数为(f(x))

现在,当且仅当(f(a) + f(b) ge k)时有解。

E. Funny Substrings

第一种操作可以直接模拟。

第二种操作,(x)的次数等于(a)的次数加(b)的次数,再加上(a)的后缀与(b)的前缀拼凑出来的次数。

注意到目标串的长度只有(4),所以对于每一个变量,维护其次数,长度小于等于(3)的前缀以及后缀。再维护一下变量间的加法即可。

然后就是个大模拟了。

F. Interesting Function

按十进制拆分成每一位去算贡献然后累加就可以了。

每一位的贡献就是把低位去掉之后(r – l)的值。

G. Gift Set

记第一种礼物搞(x_1)个,第二种礼物搞(x_2)个。

可以将题目转化为整数线性规划问题

[max. z = x_1 + x_2 \
s.t.
left{
begin{array}{ll}
ax_1 + b x_2 le B\
bx_1 + a x_2 le R\
x_1, x_2 in mathbb{N}
end{array}
right.
]

然后用单纯形求出(x_1, x_2)可以不为整数时的解,猜测正解在当前解的附近,模糊搜索一下。FST警告


程序员灯塔
转载请注明原文链接:Codeforces Round #725 (Div. 3) 题解(A-G)
喜欢 (0)