为什么这题不会爆longlong

P3195 [HNOI2008] 玩具装箱

数据太水(
by _wkjzyc @ 2021-02-21 21:51:28


数据问题?
by Eason_AC @ 2021-02-21 21:54:05


因为2008年出题人还不知道卡高精度
by 听取MLE声一片 @ 2021-02-21 21:55:28


这个题要卡爆$longlong$也不简单的.....
by MuYC @ 2021-02-21 21:59:32


@[sfmmdm](/user/82124) 题目性质吧,首先分段的数量肯定不会太少。 可以这么感性理解: $a^2 +b ^2 \leq (a+b)^2$ 而且这东西还要减一个 $L$ ,所以即使可以构造数据也很难卡满。
by Diaоsi @ 2021-02-21 22:06:12


@[Diaоsi](/user/137242) 谢谢,实际上答案是不会爆 `long long` 的,但是如果写斜率优化的话,会直接用到 `sumc[i]` 的平方,可能作为中间变量爆 `long long`,这个我测试过,但貌似不影响答案。
by sfmmdm @ 2021-02-22 08:15:25


|