P9762 [ROIR 2021 Day 1] 分割数表 题解

· · 题解

原题链接：传送门

思路：

观察 a_{i,j}，其实就是 123456……一直往下排。

那么计算总和的式子就是：sum=mn \times (mn+1)\div 2。

然后题目要求我们切一刀分成和不同的两块。对于竖着切，设切了 k 列，左边那块的和为：

\sum_{i = 1}^{n}\sum_{j = 1}^{k}(i-1)\times m+j=\sum_{i = 1}^{n}km(i-1)+k(k+1)\div 2=kmn(n-1)\div 2+nk(k+1)\div 2=\frac{nk(mn-m+k+1)}{2}

对于横着切，一样的，设切了 k 行，上面的那块和是等差数列，末项为 ，那么和为：\frac{mk(mk+1)}{2}。

然后我们可以 O(1) 求和，那么枚举行列就可以得出 O(n+m) 的算法。

考虑优化，希望最小化 \max(\sum x,\sum y)，那肯定越接近 \frac {sum}{2} 越好，这个时候有两个办法：

完结撒花！

原文链接：传送门