【cf360X】Codeforces Round #210 (Div. 1)

2015年6月23日1,9581

A. Levko and Array Recovery

求出每个位置初始值的最大值,然后check一下

B. Levko and Array

二分答案,f(i)表示前i个的最小修改次数,且i不修改,枚举上一个不修改的位置转移

C. Levko and Strings

f(i,j)表示前i个字母,beauty值为j的合法方案,\(t_k=s_k\)(k>j)

1.在第i位放一个比s[i]大的字母,枚举上一个位置i-k-1满足\(s_{i-k-1}!=t_{i-k-1}\)

产生的新的beauty子串(k+1)*(n-i+1)

2.在第i位放一个比s[i]小的字母,不产生新的beauty子串

D. Levko and Sets

我数学很差QAQ 看英文题解吧。。。

似乎就是裴蜀定理+gcd乱搞一下

E. Levko and Game

先把所有边长定为r

如果s1->x的距离<s2->x的距离,则从x出发的边长定为l,即让两人都走这条边会使第一个人更合算

先判断能不能赢,再判断能不能平局