UOJ Logo WrongAnswer的博客

博客

无比玄学的事情

2016-04-21 19:45:35 By WrongAnswer

今天为了学斜率优化,去做了下APIO2014的Split the Sequence。

写的时候发现凸包里面的点,x是int级别的,y是long long级别的,叉积似乎会爆long long?

于是手写了大整数乘法,然后交上去TLE了。

(一开始T是因为用了二分复杂度差,改成不二分以后还是TLE)

强行用一些黑科技卡常数卡过去了。

由于跑得太慢垫底了,于是想了解如何优化程序效率。

看到有人直接整数除法下取整,过了。

然而斜率不一定是整数,到底对不对?我构不出数据卡这个做法- -(那么这个做法是不是对的?)感觉略玄学。

还有人直接long long叉积也过了,我试了下

100000 200

10000 10000 10000 10000 10000 ...

的数据,确实A了。

依旧比较好奇为什么不会爆- -理论上叉积是10^27级别的啊?有些玄学。

然而我把程序改完以后跑的时间仍然是rank1的5倍,百思不得其解。

用了个计数器counter计数,都是3×10^7~4×10^7,然而为何我的程序慢那么多?

各种调试……

最后脑洞大开,原本我的DP数组是

f[100010][210], g[100010][210]

改成:

f[210][100010], g[210][100010]

跑的时间就是原来的1/4了!进第一页了!UPD:现在又不是第一页了

这是为什么呢?

真是无比玄学!

(Slow)http://uoj.ac/submission/63721

(Fast)http://uoj.ac/submission/63762

求各位大神解释一下以上问题(为什么叉积不会爆、为什么反一下会快那么多)

评论

Recursion
多维数组你把连续访问的放在后一维肯定会更快,因为他们在内存中的地址也是连续的。
matthew99
你去研究一下多维数组是怎么存储的吧= =b
liuyunhui123
2014年论文集《精细地实现程序》的2.3.5提到了~
riteme
所以为什么直接叉积可以过?是没人能卡吗......

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。