首页 > 代码库 > 51Nod 算法马拉松23 开黑记

51Nod 算法马拉松23 开黑记

技术分享

惨啊……虽然开了半天黑,但是还是被dalao们踩了……

第二次开黑,还是被卡在rank20了,我好菜啊……= =

 

写一写比赛经过吧……

 

看到题之后习惯性都打开,A~D看上去似乎并没有什么思路,F应该是道数论题,看了E感觉有点意思,一看数据范围,咦怎么只有$50000$,再仔细看一看式子,手动分情况讨论之后得到一个结论——

这题是水的线段树维护莫队啊= =

然后就开始码码码,由于一些脑残错误调了一会儿,然后就得到了这样的结果:

技术分享

我坚信自己莫队的复杂度没错,然后就开始各种王逸松卡常,使用的卡常技巧包括:

开O3和always_inline

加快读快写

加离散化(这不是基本素养嘛喂

把线段树的四个数组写到一个结构体里

函数手动展开(效果还是很不错的

用变量来存储频繁访问的数组元素(就是把询问的端点用变量存起来

以上卡常全加上之后仍然TLE,想起卡常时ztc跟我说的可以用树状数组,就改成了树状数组,这次终于过了(跑得还挺快……)。

(后来想起来,只要把线段树的两次求和改成一次求和再用总的减一下就能把线段树的时间省掉一半,也能卡过去……)

在我调莫队的时候ztc搞出了B的通项($\frac{n(n-1)}{2m}$),然后他对着小伙伴们喊了一嗓子,这题瞬间就被大家踩爆了……

然后机房的小伙伴们一直在cheat A题,在我第一次交E题之前旁边的lrz就把A题cheat掉了,然后他就把代码给了我一份……(论51Nod为什么要求数据不少于15组

与此同时lrd一直在写D题的DP,第二天来的时候搞过去了(虽然他说理论复杂度有$5$亿……),然后又给了我一份,这样就切掉了四道题,但是似乎并没有进前十……

在8:00之前lyc又搞出了C,但是F题并没有太多思路,然后就考试了……

考试之前榜上还有三个没AK的,但是考完试肯定就没机会了,真是心塞……

(我才不想说我推F的式子推了一上午……)

后来考完试再搞F的时候,推出了跟题解一样的式子,但是有一个东西是算素数的$k$次幂之和,感觉没法算,就暂时弃疗了。

 

(我写不完了……To Be Continued)

51Nod 算法马拉松23 开黑记