旁听了一波给舒老师和学弟的pkuwc面试讲座...
这里有一段隐身的吐槽, 想看的请本身想步伐不雅观看. 不想看的跳过这一段看似空白的对象就好了...
刚开始ATP学姐给我们讲了本身面试的时候的工作..描绘了一下其时面试的局面和其时问的问题..(ATP学姐太可爱了ＯvO)可能筹备的也不是很充沛 用了好多的"然后" "就是"之类的, 本身也在吐槽, 老师后来也槽来着, (不过还是超可爱n(≧▽≦)n)旁边老师在记录, 尤其记下了一个什么"你认为学习信息男生和女生有什么区别?"的问题..(可是这种问题怎么可能问男生啊讲原理), 然后学姐讲完之后就是shallwe大爷来讲, shallwe大爷还筹备了稿子, 然后就讲了一些面基技巧.. 但是也是对照老生常谈的对象, 之前参与各类百般的风貌大赛回答问题的时候也就是那一套之类的 小时候还能做到, 此刻反而越来越不行了.. 然后讲了各类百般的问题, 说是问的问题都在blog里面.. 老师还说要blog的地点来给学弟学妹什么的(那也就是包孕我们咯), 但是听完回来一看这blog里的对象能给老师看?! 各类吐槽甚至还有吐槽面试培训的.. 然后他们就回去学习了= =
老师就开始种讲评, 还让两小我私家分袂回答了上面说的男女区别问题 然后两个都做出了对照"单方面"的回答, 老师就说要往什么三个方面想之类的说了一堆, 横竖就是不怼人的同时优雅地装逼的技巧, (什么在北大不说清华比北大强之类的, 说了确定不是石乐志么= =)然后再就是"你有什么错误谬误", 风闻年年问...(大家筹备好的答案都能倒着背了好么)就说要找个"不是错误谬误的错误谬误", 然后两小我私家都说本身对照执着啊... 就不能找点有创意的么←←, 觉得全世界都有执着得有点傻这个错误谬误... 要我的话可能会说本身好奇心过强? 横竖就这么着吧. 然后还有什么进门关门鞠躬瞅瞅有没有废纸倒拖把什么的... 横竖就是一些鸡汤文里描写的面试的细节问题, 还有着装问题, 我感受只要不是明显违和的穿女装应该都不是什么大问题吧←←(对没错哪怕是可爱的男孩纸穿女装其实也是可以哒~(≧▽≦)/~)两小我私家又练了一波关门鞠躬之类的 终于煎熬地熬过去了.. 然后连忙去了个茅厕 终究半下午+半晚上没有去了.. 回来之后就调这个题 不过很快就调A了这还对照和善..(嗯 主要原因是此次的luogu没有出锅...)
===我===是===一===条===分===割===线===我===也===是===一===扇===传===送===门===
继续吐槽, 不过此次跟标题问题有关了.. 听完回来就继续写这道题啊...
这道题显然撑持\(O(n)\)的做法, (觉得1e6的话套个log就不是很靠谱了)
那就是要优化, 就是要化式子嘛..然后刚开始以为这个题是
\[\sum_{i=1}^n(ax_i^2+bx_i+c)=a\sum_{i=1}^nx_i^2+bs_n+n*c\]
然后最大化\(\sum_{i=1}^nx_i^2\)之后直接输出\(a*f[n]+b*s[n]+n*c\)的洪流题,
但是发明仿佛样例差了好多好多...功效发明本身快读没读负数...
然后改完之后输出负数了... 手玩了一下发明仿佛这个\(n*c\)的\(n\)仿佛不必然是标题问题里给的\(n\)...
那就不能这么化式子了, 就开始从头化.. 还是得从状态转移方程入手...
\[f[i]=max\{f[j]+a(s[i]-s[j])^2+b(s[i]-s[j])+c\}(j\in[1,i))\]
然后去括号
\[f[i]=f[j]+as[i]^2-2as[i]s[j]+as[j]^2+bs[i]-bs[j]+c\]
移项能得到
\(f[j]+as[j]^2-bs[j]\)=\(2as[i]\)\(s[j]\)+\(f[i]-(as[i]^2+bs[i]+c)\)
由于标题问题中已经给了\(-5<a<-1\), 所以斜率必然是<0的, 而\(f[j]+as[j]^2-bs[j]\)直不雅观上很明显是递减的. 我们考虑凸性对功效的影响.
我们考虑中间的点在位于两个斜率中间(大于大斜率小于小斜率显然不优就不考虑了)的情况.
发明如果是位于下凸壳的点是不优的, 而位于上凸壳的点是优的, 我们就要维护一个上凸壳.
而这里的斜率\(2as[i]\)显然是递减的(绝对值递增), 所以
如果一个斜率一旦已经小于(绝对值大)于队首的边, 那么队首的点在以后也不会优了 我们让队首出队即可.
依然是维护一个单调行列队伍.
然后就没有了. 代码: 1A了哈哈哈哈 (疯狂地笑ing...)