Codeforces Round #373 (Div. 2)

4/4

好久没写题解了，写个CF的题解练一下手！！

题A A. Vitya in the Countryside

题意：给你一个序列，问你是上升的还是下降的，还是不确定。

题解：水题，略

题B B. Anatoly and Cockroaches

题意：给你一个字符串，有两种操作，第一种：将b变成r或者将r变成b，第二种：b和r交换，问你最后变成交替的字符串的最小代价，每种操作代价一样都是1.

题解：本来以为dp，恶心贪心什么的，但毕竟是第二题没有那么麻烦。做法是写出目标序列，然后看一下有多少错位，优先交换，然后交换还不够就补上，一共有两种目标序列。

题C C. Efim and Strange Grade

题意：给你一个浮点数，然后你可以采用四舍五入进行进位，不超过t次，然后最后得到最大的数是什么。

题解：表示真的不会做贪心题。这道题的显然结论没找到：优先弄第一位大于等于5的，然后一直往前弄即可，这样一定是最优的。

题D 因为出题人自己都不会做，所以就删了。。。。。

题E E. Sasha and Array

题意：给你一个序列，有两种操作，第一种：1 l r x表示将这个序列的[l,r]加上x，第二种：2 l r求出

，其中f是斐波那契序列。

题解：用线段树维护两个值s1，s2。其中s1表示，s2表示，然后每个节点还要多维护的lazy值是一个矩阵，表示这个区间要乘上的矩阵，最后要注意的一点就是update的时候，最多有log个区间要乘以那个矩阵，要预先算出来，然后直接加到那个子区间去，不然会超时。

代码