吐槽一下,怎么必须要 AC 了才能发题解,害的我还得先登审核号把自己赛时代码拷过来。
我们需要充分发挥人类智慧,仔细观察样例 1 后可以发现当我们对每一行删去最小值后每一行都是一样的。
不妨大胆猜测,如果每一行不一样那么一定不行,如果每一行一样则一定为最优方案。
很显然,当每一行相同时,只需要一直做竖向操作即可,操作唯一。
然后就有以下代码:
竟然 WA 了!
也是非常神奇。
然后我们动用观察力可以发现有如下 hack。
正常应该输出 1,直接竖着做一遍即可。
于是可以找到漏洞,不一样要先把每一行的最小值减去,先减每一列也行。于是我们把行列交换再做一次,两次取最小值。
有如下代码:
然后就过了(?)
声明:
> 本题解为恶搞做法,不保证思路正确,欢迎大家尝试 hack 本题解,或证明本题解正确性。
彩蛋:
> 比赛结束三分钟后 cjdst 在 Q 群问 T3 正解是啥,ta 给出了自己一个解方程的做法(显然太吃操作了,对于我这种不会有理数加减法的蒟蒻来讲),我也分享了我的恶搞做法,于是有了本题解。(甚至 cjdst 说以后自己也要乱搞打巅峰赛。