Codeforces Round 645 (Div. 2)
感觉这场的题出的很不错,所以记录一下。
这题分奇偶讨论一下就行了。其实可以合并成一个公式:
⌊nm+12⌋\lfloor\frac{nm+1}{2} \rfloor ⌊2nm+1⌋
仔细读一下题,发现可以一次性叫所有人一起来。所以排个序就行了。
这题很有意思。
首先比较容易发现,所有走法得到的最大值和最小值之间的所有值都是可以被走出来的。
但是如果去求最大值和最小值,需要推几个式子,还是很麻烦。
继续观察,可以发现,每次提前往下拐一格,可以使最后结果 +1。
那么所有走的方案就是 (n−1)(m−1)+1(n-1)(m-1)+1(n−1)(m−1)+1。
显然答案应该是一段连续的月份+前一个月的月末+后一个月的月初。
然后列个式子,可以发现取月初的是比较亏的,应该整体往前推一下。
所以答案应该是一个月末加上后面的若干个完整的月份。
那么双指针一下就完事了。