第六届山东省ACM省赛酱油记

(今天是2016年6月5号,第七届山东省ACM省赛,看着他们满载归来,我又想起了去年省赛的时候,翻出了这篇文章。这篇文章写于2015年5月,始发于QQ空间,后来又删掉了,现在重新发到这里:D)

 

热身赛xlc没来,就我跟zzk打得。开始我先过了求和的一道题。
B
1 1Y
公式题,注意溢出的问题。
发现竟然不是FB,zh他们队竟然在0分钟就过了。
随后zzk和我说了一下E,是个去注释的题,感觉不太好做,就放了放。
我随后看了C,感觉像以前做过的一个题,似乎所有情况都应该是1。但我还是写了一个平方的做法,大约是10的八次方,就当测测机器,结果竟然A了。

我又交了一下全输出1,也过了。

C 15 1Y
给n个正整数问能否找到一些数字使得它们的和恰好被n整除。这个题的答案是一定能整除,可以用鸽巢定理证明。
然后zzk和我说了一下D题,我发现只要判断是不是1即可,这样需要判断一个方程能否成立就行了。本来代码写的是对的,但我看走眼了又浪费了几分钟。
D 25 1Y
找规律。根据规律建一个方程判断能否成立。
由于一元二次方程是众所周知的坑题我就决定先做E。E题是个去掉注释的题,我没仔细读题,担心有注释嵌套等一些比较奇怪的数据,问zzk他也不知道有没有。于是我就提问了一下,结果返回no response,还叫我认真读题。我看了一下题面发现上面说保证数据是可以编译的代码,我就放心了。一开始我想读一行输出一行这样处理。但zzk提示说可以合并在一起做,我感觉是个好办法,于是就写了代码,又调了调,过了样例,正想交,我忽然想起那句保证数据是可以通过编译的代码那句话,可能存在位于字符串里面的注释!真是坑啊。我跟zzk商量了一下,加了个特判。有个数据间换行的地方,我非常傻逼的写在了前面,zzk可能是没注意到或者也许是觉得我是学长也没说出来,交上去就WA了。随后他指出换行那里写错了。改了以后交上去,竟然真的AC了。
E
73 2Y FB
从一份代码中去掉注释。坑点是注释符号可能存在于字符串中,这样的情况不应去掉。具体代码不难写。
由于一元二次方程我也没写过,剩下的时间里就把机器交给了zzk,我在一旁打辅助。他最后写好了代码,我们又一起改了一些bug,但最终也没过。最后就4个题了。
揭榜以后发现没有队AK,这样我们四个题加上罚时优势位居第一。发现山大最多的才3个题,似乎没有了往年的强势,有点奇怪。

正式赛。
一开始,他们读题,我写头文件,登录pc2。一开始zzk说J是水题,跟我了下,我说直接判相等和模11就行,xlc说他也看了确实是这么做,于是我就敲了,感觉可以FB,交上去竟然WA了!我刷了一下榜,ACF都有人出了!于是zzk看A,xlc看C,我看F。F我大体看了一遍,竟然没看懂,又猜测了一下题意,竟然没什么思路。这时候zzk写了A,但他可能比较紧张,交了两次都WA了。连续3个WA,对我们的开局造成了非常不利的影响。这个沉默直到xlc过了C才被打破。
C 23 1Y
一道博弈入门题。很多人应该都见过,xlc大概是现场重推的。

随后zzk意识到自己代码中的错误,原来是有个地方写反了,我们这次谨慎地测了一下觉得没问题就交了。终于AC了。
A 27 3Y
A题是个签到题,WA两次确实比较可惜。
我又琢磨了一下J,感觉题意也没问题,但竟然没有人过这道题。裁判端提示J题数据有问题,原来是大数。xlc说上java吧,我说不用直接做就行。
J 43 2Y
大数模11。这本是可以抢FB的一道题但是开场的WA对我造成了很不好的影响,但所幸我们只提交了1次。

随后我和xlc说了一下F,其实我也没怎么看懂,他就又看了看。这时候过B的渐渐多了起来,我就去看B。当时榜上过题的很多,我们名次比较靠后,节奏比较乱,我心里也比较乱。想B题的时候一直都不能静下心来,期间xlc就在想F。后来zzk和我说了一个B的思路,我感觉很靠谱,他看着我写,最后交上去AC了。
B 62 1Y
简单的STL题,用set可以轻易解决。想偏的话很容易联系到一些高级数据结构。
这时候我才发现榜上只有一个队过了F,xlc也认为F并不好做。我和他说了一下有个平方数的题似乎可以搞,给他翻了翻竟然找出一个立方数的题来,我们才发现原来有俩题一个叫平方数一个叫立方数。他想了会跟我说了个思路,就决定试一试。期间我读了D,当时并没有人做D,但我感觉很好做就等上机写代码了。
H 81 2Y
平方数,一个数学题。
xlc犯了个小错误,最后还是过了。
随后我上机写D题,写好以后在一个小细节上卡了一下,最后还是及时发现了,交上去顺利AC。这也是我们队整场唯一的一个FB。
D 101 1Y FB
D题是要找能够覆盖至少K个点的最小矩形面积。我用的是枚举前缀和+尺取法的做法,400的数据量,n^3的复杂度。
省赛前几天我特意复习了一下尺取法,这次竟然用到了,感觉有些神奇。

随后xlc觉得G题跟H基本一样,但是榜上却没有人过,就在想有没有什么坑,但想了又想也没觉得有坑。他随后改了H的代码交上去却超时了,后来加了一个优化,竟然RE了。后来我们发现有个地方爆int了,这样正数变负数,作为数组下标就RE了。改掉之后终于AC。
G 134 3Y
立方数,xlc说做法与H类似。
当时我们队名次比较靠前,但罚时很多。榜上有很多队过了L,我们就去看L。题是xlc读的,强联通分量还是最短路他也拿不准,最后敲定是最短路。我看了下这得用优化的最短路啊,于是就敲了个堆优化的dijkstra,交上去WA了,后来发现了几个可能的bug又交了两遍还是WA。xlc又重读了一遍题,发现应该是强联通分量,于是就翻了模板。我一边敲,他一边研究代码。最后我们在最短路的基础上加了个强联通缩点,写好了正想交,发现pc2竟然没响应了。于是叫来工作人员,又重启了pc2客户端。最后交上去就A了。
L 183 4Y
图论,强联通分量缩点+最短路。
这场比赛几乎可以说从头到尾全是失误,打的非常不顺。L题读错题,白白贡献了3个WA更是非常的不应该。
之后我曾经试图猜测一下F题的答案,也许是某个公式之类的,但交了两次都是WA。
剩下的时间里xlc推了一个F的题方程,觉得可以解就给zzk了,而他自己在研究E。我读了读K,感觉应该是个思路或者dp,数据量不大应该不难搞,但也没什么明显的思路,就看了看I。I题名为路由表,样例都是关于ip地址的,我对计算机网络还是比较熟的,看这些感觉应该是字符串匹配一类的题,ip地址更是经常跟trie一起出题。于是就去找zzk问了一下题意,可能是他没学过网络,对题意也是一知半解。我大致地看了一样数据量确定了不能暴力,只能用trie树,又大概看了一下输入输出要求,明白了样例。期间xlc在写E,我就在想I,觉得有个差不多的做法了就上去写。写好以后竟然不能出样例,于是就印了代码退下来让xlc继续写。我后来发现了几个小错误,上机改好过了样例就交了,但是竟然WA了。之后就封榜了。此时我在做I,xlc在写E,zzk在解F,如果三题全出名次一定非常靠前甚至夺冠,但这可能性实在太低了。之后我自己感觉代码没啥问题,又看了一下题面,发现输出要求先匹配最长的再找最小端口号,前一点完全被我忽略了。但做法也不难,只要再开一个数组记录一下长度信息即可。我按照自己的思路写了代码但竟然连样例都不过了,于是我就印了代码,把机器给了xlc。xlc此时也发现自己的算法是有问题的,一直不能过样例。这时我就有些慌张了,一直不能静下心来思考I题。我心里很清楚这是个非常简单的问题,如果在平时只要理清思路肯定能够AC。当时已经是封榜过了20分钟了,我又控制住心态,重新理了理头绪,虽然想的很慢,但是感觉并没有差错。最后终于发现是之前写的有句代码忘记去掉了。这样终于过了样例,我提交了我们在这次比赛的最后一发,终于返回了一个YES。

I 283 2Y

一道很明显的trie树,如果没有网络知识基础很有可能纠结于题面而读不明白题意,实际上还是非常容易,但是最后的输出要求比较繁琐,需要想清楚。

trie树我在省赛前也有复习过,竟然也神奇的出现了。过了I之后,我也松了一口气,感觉9题金牌可以稳了,就吃了点东西。当时还剩下不到20分钟,我问了一下zzk,他说F是一个一元三次方程,非常难解,我说可以不可以二分或者三分之类的,他说似乎是不行。而xlc研究的E也一直没有结果,也许是太紧张了他也比较混乱,很难理清思路了。
我数了数山大的气球,有10个。
最后的几分钟里,我们一起看了看榜,已经确定山大是10题,而sx他们队一直是9题榜首,我想以他们队的实力肯定能过D,这样咱们学校不会是夺冠了吧?由于我们队罚时比较多,封榜时是8题靠后,前面山大和山理工封榜后都交了好几个题但是罚时也不少。我预测了一下运气好的话我们或许可以进前五。

省赛题这么水,而我们这次打的这么烂,几乎可以说是我们三个组队以来打的最不顺利的一场。开场水题连续3个WA,直接就是要崩盘的节奏,中间L题读错题也浪费了很多时间,据xlc说GH也有很多失误。总之真的是非常的不顺。但毕竟我和xlc都很久没认真做题了,而zzk又是第一次打。
我心里还是觉得打成这样非常可惜,赛后K神打来电话说要我们队三个都去蓝光报告厅参加闭幕式。我吃了一惊,整个队都去闭幕式这可是前三名的待遇啊,难道我们是第三名吗!?
最后揭榜的时候发现原来当时排名位于我们前面的两只8题的队伍在封榜以后都没有过题,这样我们队就成为了第一个9题的队。这个事实有些不可思议,要知道我们并不能解出第10个题,我们的对于这套题的极限也就是第三名,而我们打得这么烂竟然也可以得第三,实在是不可思议。最后是揭晓冠军的时刻。当山大的K题变绿,变成第一名的时候,欢呼声响起。这时主持人说,不要着急,还有一个队没有揭晓。那一刻,所有人都在期待山科大的D题。当最后的D题变绿,山科登顶,全场的欢呼声更重。那时我觉得这应该是个历史性的时刻,从第一届省赛到第五届冠军都被山大独占,而今年的此时此刻,冠军终于易主,而正是我科大。自08级起,学校历年的ACMer不懈努力,取得各种成绩,激励我辈,而此优秀传统得已传承,历史被改写,从此我们可以说山科大ACMer绝不逊色于山大。这种感觉真是热血的很。
赛后我开玩笑的和zzk说,你就山科大第一个大一的金牌爷了。他就说他老是帮倒忙。老实说,我觉得zzk的代码和思路都还算不错,但是读题能力比较弱,问他题意常常说不清楚,读懂的题也常常说不出重点,跟我们交流也有些问题,可能是觉得我们是学长,不太好意思开口吧。总之,希望新一代的队员们好好努力吧。

大学这几年的ACM酱油生涯…

(本文写于2015年6月)

从上海滚回来以后,今年的ACM生涯也就结束了,来写写这两年的ACM经历吧。

大一上学期的时候ACM集训队来宣传,什么也不懂的我就直接报名选拔赛了。可是当时实在太弱了,C语言课都没听过,连个字符串逆置都不会写,所以前两次比赛都没敢去。寒假回去照着刘汝佳的入门经典写了几道课后题,写了一道UVa超时了直接就放弃了。于是整个假期都在打鬼泣5。

过年回来队里又办了第三次选拔赛,我就厚着脸皮去了。比赛时间大概是一个下午,我乱搞一顿水了2个题。当时川神大概是过了4个,连BFS啥的都会写了。而我还在用暴力求中位数,连qsort都不会。由于一直没加什么关于ACM的群,所以消息一直很封闭,对于最后结果我也不知道。再后来教主组织人开了个会,大概就是问问寒假都刷了多少题。我作为一个UVa还不到10道题的人果断就没敢去丢人- -。但也可能就是这次没去就错过了后来的省赛等一系列比赛吧。大一下的时候感觉对学校的各种玩的也没太多兴趣了,干脆就刷刷题了。但是才水了三五天就遇到不会的了:是一道字符串匹配的题,当时看来真的是超级麻烦。然后我就觉得ACM这东西真的不是我辈能企及,就放弃了。

但是,大概我与ACM的缘分注定是不会这样结束的吧。

在过了大约一周的时间后,班里搞了一个啥学长经验交流会,特地邀请了当时ACM集训队里的DC和CC。当时看两位爷在上面谈笑风生,真是好叼。尤其是超爷说他当时都跑到网吧里去交题,我表示汗颜。但是,真正让我印象深刻地,不是他们取得多么了不起的成绩,而是,他们练ACM刷题的过程中,也会像我一样遇到各种的艰难、麻烦。

然后,在后来的时间里,我在UVa上那条代表题数的直线又开始变得倾斜起来。

暑假来临之前,我刷到了大概130道题,幸运地赶上了暑假集训的末班车。我那时候才混进和ACM有关的第一个Q群。
我还记得很清楚那时候教主叫我们几个人开了个会,问我们暑假留校的目的是什么。当时他在黑板上写了几项,有出去打比赛拿奖、留下来试试看自己适不适合这个比赛、提高自己的编程能力。我很实在的选了最后一个,当时还很担心没选到让教练满意的选项会不会被赶出去。。

第一年留学校还是很有新鲜感的,但是生活却不太舒服。2013年的夏天超级热,连青岛都到了35度。我们一帮人住在B4,晚上睡觉要被热醒好几次。更惨的是那时候我舌头上面长了两个疮,别提吃饭,连说话都疼得厉害。但是肉体上的折磨还能忍受,最摧残的是心理的煎熬。话说大一下那时候我一直都有认真听教主讲课,最后考试也都AK满分,对自己还是很有信心,所以才抱着进一步提高的心态参加了暑假集训。但是一打比赛我就傻眼了,身边人都啪啪啪敲键盘了,我表示连题意都还没看明白。别人总是轻易过题,自己就一点思路都没有,于是挫败感暴增。

一个暑假下来川神过了二十多道题,其他好多人也过了十几道,我才九道。作为一个连BFS都要比着书敲的人还能说什么?我也认了,毕竟我起步比较晚。

我还记得当时教主给我们看3xian的退役文(好吧,现在看来确实有点装逼),但是当时却是影响我非常的深:在ACM圈子里,总有这么一些人,身处并不舒坦的环境里,凭借自己努力,改变弱者身份,证明自己。

一个暑假下来,我没有如期待那样得到多么巨大的提高,反而深深地感受到了自己的渺小。同时,暑假前教主留下的问题,在我心里的选项,已经由最后一个悄悄地变成了第一个。

真正入门就是大二上开始的。深受3xian影响的我也开始不看题解,自己硬啃题做。困惑了一个暑假的动规,终于开始有点眉目,我一天都能过掉好几道(神牛们不要鄙视我。。),于是曾经的折磨都变成了AC时刻的享受。那个学期刷掉了不少入门经典上的题。难得等到一次个人赛,去打了打,结果还是被虐了。

寒假的时候才开始全面的做训练指南,也开始学各种算法。然后打了一个假期的CF都没紫起来,中间还绿了两回。川神第一次就紫了。

大二下的时候被身边人黑的厉害,我也有点松懈了。电脑上都装上LOL了。开学没多久以后XLC的CF也紫了。我继续艰难地打着。到了5月份,滚去威海打省赛。老实说这次省赛相当水,但是因为我当时太浮躁了,很多算法基础都不牢固,连个线段树都要写半天,最后拿了个银牌。这也是学校这几年第一次没拿金牌了,惭愧。

省赛回来以后又认真刷了刷题,CF终于紫了。对于我这么弱的来说,紫色也算是不容易了。

14年选人的门槛降低了不少,导致暑假留校的成员大增,也为集训队注入了新的活力。由于12级各位大神都比较懒,于是就由我负责给新成员们出题,玩的也算是愉快。

受影响13年暑假留校影响我本来还是有点担心这年的网络赛能不能打出线。但是在12级各位大神和13级各位新队员的通力合作下,总算把几个赛区的名额都拿到了。在教主的建议下,我们两只12级的队都选择去了牡丹江赛区。事实证明这个决策相当明智。

在牡丹江,我们两支队取得了一银一铜的成绩,差强人意。后面那些赛区就是大二和大四的去了。

后来我跟XLC还有11级的WGJ组队又去了上海。上海赛区是一个特别赛区,由谷歌命题,我们也有点心理准备,但是没想到最后直接打秃了。

再后来就打算不再参与ACM竞赛,专心准备找工作,但是在寒假却奇迹般地拿到了阿里的暑期实习offer,于是我决定再参加这一年省赛。

在组队方面教主安排我和XLC、还有大一的ZZK组队。我已经有比较长时间没做题了,但是每次组队赛我们却都能神奇地排到前列。身为手速狗的我常常是迅速敲掉水题,但是最后有区分度的题往往是XLC写的。不得不佩服银牌爷XLC的厉害。

今年的省赛在自己学校举办,学院里也非常重视,很多人都为这个比赛的成功举办默默付出了很多汗水。我们队这次比赛打的并不顺利,但是神奇地拿到了季军,有些不可思议。值得祝贺的是这年省赛学校拿到了三块金牌,其中包括冠军和季军,实在是一个大突破。

作为一个还在队里水的大三狗也说点什么吧。。
我还记得早的时候薛神说我们这些学校的人也不一定就是智商比那些强校差,其实还是有很多经验之类的东西值得总结和传承下去。

我们这代人实在是幸运地多,有了自己的机房,比赛也开始受到点重视。想想昔日的队员,在那么糟糕的环境下,取得今日SDUSTACM的成绩。我们又怎能不珍惜现在?

最近这段时间看大一的时不时就要把梦想、Final之类的挂在口上,却又常常在水Q群。我就有种把Q群直接解散了的冲动。

从最早接触ACM至今也有快要两年的时间了,如若不是当时的一念之差现在的人生可能又是另一个样子。至于以后还会不会打,好吧,我肯定还会水题的。至于要不要比赛,那得看学弟们愿不愿意给我比赛名额了。。

常用的文本处理命令总结

统计某个文件内某个字符(串)‘,’出现的次数:

grep -o选项表示只匹配给定内容;wc -l选项表示统计行数。

输出某个文件的第3列:

输出指定某列的内容:

查询当前目录所有文件中某个单词出现的位置:

 

 

欧拉路径与欧拉回路相关

简单来说,欧拉路径就是一笔画形成的路线,欧拉回路是一笔画形成的路线并且回到起点。

判断条件:必须是联通图(可以使用并查集判断是否联通)。

欧拉回路:
无向图:每个顶点的度数都是偶数,则存在欧拉回路。
有向图:每个顶点的入度都等于出度,则存在欧拉回路。
欧拉路径:
无向图:当且仅当该图所有顶点的度数为偶数 或者 除了两个度数为奇数外其余的全是偶数。
有向图:当且仅当该图所有顶点 出度=入度 或者 一个顶点 出度=入度+1,另一个顶点 入度=出度+1,其他顶点 出度=入度。

 

构造方法:fleury算法,O(E)。

 

两个例题:

http://hihocoder.com/problemset/problem/1176

http://hihocoder.com/problemset/problem/1181

 

 

Dynamic Programming Optimizations 动态规划优化

本文主要是针对http://codeforces.com/blog/entry/8219提及的一些算法和题目的解释。

 

Kalila and Dimna in the Logging Industry

考虑一条正确的dp顺序非常重要,以dp[i]表示砍掉的最大id是i时的最优解。注意到砍完最后位置的那棵树之后的花费将为0,因此只需要在花费尽可能少的情况下,砍到最后位置的那棵树即可而无需考虑砍完所有树,这步贪心优化非常关键。可列出方程dp[i]=min{dp[j]+a[i]*b[j]}直接套convex-hull-trick即可。

 

Cats Transport

首先考虑一条正确的dp顺序。以猫的出现时间-饲养员到该座山的时间,可得该猫的最少等待时间,假设为数组a。将数组a从小到大排序,这样根据等待时间会比较容易发现dp规律。当一个饲养员想要收获该路上的一些猫时,取决于这些猫的等待时间最大的那个,有了这个同时可以计算出其他猫需要等待的时间。dp[i][j]=min{dp[i-1][k]+a[j]*(j-k)-(sum[j]-sum[k])},其中dp[i][j]表示前i个饲养员搞定前i个猫时的最优解,sum是数组a的前缀和。变形之后使用convex-hull-trick。和前面不同的是这个是多维的,因此需要用一个数组临时保存结果,避免影响当前的计算。

 

NKLEAVES – Leaves

这个题比较容易构造出dp方程。但是在求最小值的时候,要求斜率m是递减,x是递增,这样才可以使用单调队列,因此需要对原题进行调整,翻转weight数组,改向左移动变为向右移动。这样得到方程dp[i][j]=min{dp[i-1][k]+sum2[k+1]-sum2[j]-(n-j+1)*(sum1[k+1]-sum1[j])},其中sum1是数组weight的后缀和,sum2是weight*(n-i+1)的后缀和。此时得到直线方程中mx部分是sum[k+1]*j,其中sum[k+1]减小,j增大,符合convex-hull-trick的要求。另外一个注意的地方是初始化的部分。

 

Ciel and Gondolas

dp方程是dp[i][j]=min{dp[i-1][k-1]+c[k][j]},其中dp[i][j]表示前i条船装前j个人时的最优解,c[k][j]表示第k个人到j个人在同船时的值。设opt[i][j]表示dp[i][j]=min{dp[i-1][k-1]+c[k][j]}在取得最优解时的k的值。比较容易发现dp[i][j]<=dp[i][j+1],可以推出opt[i][j]<=opt[i][j+1]。基于这个特征可以进行优化,假设当前先计算得到dp[i][m],同时可以得到opt[i][m]=k,那么计算dp[i][1…m-1]时只需要从1…k进行转移,计算dp[i][m+1]只需要从k+1…n进行转移,这个过程可以递归进行,即是一个分治的算法。

 

Guardians of the Lunatics

这个题还是分治优化的dp,与上一个类似。题解

 

[APIO2010 特别行动队] (动态规划+斜率优化/convex-hull-trick)

一道很经典的题。

状态转移方程是dp[i]=max{dp[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c},变形后得dp[i]=max{-2*a*sum[j]*sum[i]+a*sum[j]^2-b*sum[j]+dp[j] +a*sum[i]+b*sum[i]+c},可以看作两部分,右部分a*sum[i]+b*sum[i]+c在确定i之后变成常数,左部分-2*a*sum[j]*sum[i]+a*sum[j]^2-b*sum[j]+dp[j]可以视作线性函数y=m*x+b,其中m=-2*a*sum[j],b=a*sum[j]^2-b*sum[j]+dp[j],x为sum[i],求max{y=m*x+b}转化成convex-hull-trick问题。

另外本题可以不用二分。在直线组y=m*x+b中,斜率m是一直增大的(m=-2*a*sum[j],a<0,sum[j]>0,sum[j]递增),画图可以发现整个图形是递增的,而且x(x=sum[i],sum[i]递增)也是递增的,所以值一定也是递增的。因此不需要用二分,使用双端队列即可,在队首维护当前的最优值。

 

关于convex-hull-trick更多的资料:

http://codeforces.com/blog/entry/8219

Codeforces Round #344 (Div. 2) Report

写代码也可以看作是一门艺术。一份简洁清晰的代码也极具观赏性。在ACM竞赛中,代码是否简洁明了在一定程度上反映作者的思路是否清晰。

这几天写的一道CF题,同样的思路,我用了80行,而标程才40行。对比之下,我发现在实现同样的目的的时候,我的做法看上去的很好懂写了两个分类但是不够简洁,而标程则十分直接没有一句废话。

贴上代码。

 

Convex hull trick

本文参考自http://wcipeg.com/wiki/Convex_hull_trick,内容包括我对wiki的一些简单翻译和个人的一些理解。

Convex hull trick是一种算法或者说数据结构,用于在一组线性函数(形如y=mi*x+bi)中,每次查询给以具体的x,可以快速求出最大/最小的y。

举个例子。

现在有y=4, y=4/3+2/3x, y=12-3x和 y=3-1/2x这四条直线,问当x取值为1时,这些线性函数的y里面的最小值。

convex_hull_trick

四条直线如上图,可以发现当x=2时,直线y=4/3+2/3x有最小值,为2。

朴素的算法很容易就能想到,假设查询Q次,共有M条直线,那么时间复杂度就是O(QM)。

现在讲一下用Convex hull trick求最小值。

对于上面的几条直线,y=4始终不可能是最优解因此剔除,余下的只取它们为最小值的那段区间(上图绿色部分),它们的斜率是依次减小的,形成了一个凸包,它只有一个峰值。

因此,在去掉无关紧要的直线后,将余下的直线按照斜率降序排序,这样形成了N个区间,其中每段都是每条直线取最小值的那部分。如果我们可以确定每个区间的端点,那么这就变成了一个简单的问题:使用二分查询每个答案。

在前面已经发现,如果相关的线段已经确定和排序,那很明显它可以在O(lgN)内使用二分求解。因此,如果我们一次添加一条直线在我们数据结构中,然后再维护这个结构,将得到一个可行的算法:开始没有线(也可能一条或两条,取决于具体实现细节),每次添加一条直线直到整个的数据结构完成。

假设在回答任何查询前我们能够处理所有直线。我们按照斜率降序排序,每次仅添加一条直线。当添加一条新的直线时,之前存在的一些直线可能被移除,因为它们不再有用。如果我们想象所有直线位于栈(stack)上,最先被添加的直线位于在栈顶上。当我们添加一个新的直线时,考虑栈顶的直线是否还有用。如果是,我们加入新的直线并继续;如果不是,则弹出栈顶并重复这个过程直到栈顶的直线不应被丢弃或只有一条直线(底部的这个可能永远不会被删除)。
那么,我们如何才能确定是否应该从堆栈中弹出?假设l_1,l_2,和l_3分别是栈顶方向的第二条直线、栈顶的直线和待添加的直线。然后,当且仅当l_1和l_3交点位于l_1和l_2交点的左侧时,l_2无用可以被删除。(这是因为它意味着l_3已经包含l_2以前的部分。)

Convex hull trick空间复杂度为O(M),算法过程包括排序O(MlgM),Q次查询,每次是O(lgM),故时间复杂度是O((M+Q)lgM)。

最后贴一个模版。跟前面的例子不一样,这里是用来求最大值的,外部使用的时候直线要按斜率升序添加。要改成求最小值也很容易:二分改成求最小值,另外外部使用的时候直线要按降序依次添加。