P4501:[ZJOI2018]胖 – 题解

主要思路

可以比较显然的看出来是个区间扩展问题,单调的向两边进行扩展。

正常暴力可以考虑 \(n^2\) 进行扩展,然而这题显然有单调性,所以我们可以试着进行二分优化掉一个 \(n\)。二分出一个范围,然后再用 ST 表或者是线段树之类的东西去查一下区域内的最远距离然后就可以进行判断了。

代码有点长而且还有点复杂。

继续阅读P4501:[ZJOI2018]胖 – 题解

[Fortuna OJ]Aug 5th – Group A 解题报告

A – 矩阵游戏

这道题看了题解之后发现就是一道 sb 题。

考虑将每一列看成一个数,发现如果忽略掉列的操作,这些数仍然满足等差的条件,所以我们只要暴力算完第一列就可以进行等差了。如果考虑列的操作,那么我们就大力暴力就行了,时间复杂度是\(O(n + m)\)。

继续阅读[Fortuna OJ]Aug 5th – Group A 解题报告