Codeforces Round #427 (Div. 2)

啊,大号终于上紫名了,撒花😆😆😆😆😆😆
2017-08-01 10-15-44 的屏幕截图

2017-08-01 10-17-26 的屏幕截图
 

A. Key races

按照题意模拟,开始读错题写了半天。。。英语是真的读不过外国人啊。

 

B. The number on the board

贪心,从小的数字开始修改可以使次数最少。所以我们可以先统计 0 - 9 每个数字出现的次数,然后一次修改,直到条件满足。

 

C. Star sky

首先知道在 t 时刻看星星的亮度为 (t + s_i) \% (c + 1), 即初始亮度相同,在同一时刻亮度相同。因为 c 很小,所以不同亮度的个数很小。所以我们可以将相同的星星统计在一起计算贡献。即穷举星星的亮度,通过计算查询区域内有多少个这类星星,从而计算出这类星星的贡献。查询利用二维的前缀和优化。

 

D. Palindromic characteristics

首先,一个 O(n^2) 的 DP, f_{i,j} 表示子串 s_i s_{i+1} ... s_j 是否为回文串。接着再一个 O(n^2) 的 DP, g_{i, j} 表示子串 s_i s_{i+1} ... s_j 最高为几级回文串,显然 g_{i, j}g_{i, \lfloor \frac{i + j}{2} \rfloor -1} + 1. 注意 DP 的边界。做出来后统计一下,前缀和处理一下即可得到答案。

 

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注