8冬假伊始（2 / 2）

“要么AC，要么重来！”

“算法是一种思维方式。”

讲台的整面白板上写满了各种算法公式、推导过程和伪代码，右半边还残留着模糊的状态转移方程和图论问题的手绘示意图。进门的桌子上摆着好几本厚厚的参考书：《算法导论》、《计算机程序设计艺术》、《挑战程序设计竞赛》，也不知道是谁的，忘记带回去了，在这儿放久了，也就随之成了公用的了，供大家随时翻阅。

顾梓聿和姜明?常常是一起到的，但张铎总是悄无声息地就已经坐在那里了，谁都不知道他究竟是什么时候到的??难怪他管钥匙呢。然后机房陆陆续续就有人来，大家都很自觉地，来了之后就安安静静地坐在那里开始刷题。傅尧肯定不是最早一批来的，但他也不是最后一个，迟到一哥总是方灵烨。

大家的风格各不相同，有人算得飞快，像是在与时间赛跑；有人停顿许久，陷入沉思，然后突然猛然敲下一行代码。

除了方灵烨。

这小子是真的聒噪，机房里除了键盘敲击声，就是他喃喃自语的声音：“这个fn到底能不能拆成fn-1+fn-2这种形式？如果可以，那就是DP，否则可能要用数论技巧……”

他完全沉浸在自己的世界里，幸好周围大家都很nice，没人想把一直发出背景音的他扔出去。

张铎算是冷静型的，他总是戴着森海塞尔的降噪耳机，已经提交了十几次的题，每一次失败都会在代码旁边留下注释：“TLE可能是log的优化不到位？”、“WA，可能是边界没考虑？”他像个机器一样有条不紊地调试代码，直到那行绿色的“Accepted”终于出现在屏幕上，他才轻轻舒了一口气，揉了揉眼睛，开始看下一道题。

姜明?的风格算是暴力流，用他的话来说就是“先写个能跑的”。看到一道题如果没有思路，他通常都是“能写暴力就写暴力”，不管算法最优解是什么，先写一段跑起来再说。

“过了吗？”顾梓聿冷不丁甩来一句。

“WA了。”姜明?摸摸脑门，叹了口气。

“优化了吗？”

“在优化呢，把三重循环改二重，直接在外层循环计算和，避免On?，时间复杂度会好点。”

改完，他再次提交。结果还是WA，他叹了口气，抓了抓头发，朝屏幕翻了个白眼：“我的生命又浪费了五分钟，梓聿，你帮我看一眼呗，就求个最大连续子数组和，这个要怎么做啊？”

“这么经典的算法问题求MaximumSubarraySum，你是不是上课没听？暴力枚举肯定不行，可以用分治法、前缀和或者动态规划，时间复杂度逐个递减，你选一个吧。”

顾梓聿看着腆着脸凑上来想直接看答案的好兄弟，十分冷酷地转过头：“算法导论里有很详细的解释，自己看书去。”

姜明?看着顾梓聿的屏幕，直接念出声来：“…某城市有N个工厂（编号1~N），M个商店（编号N+1~N+M），需要运输货物。每个工厂最多可以生产一定数量的货物，每个商店需要一定数量的货物。运输货物的费用由路径的单位运费决定，求如何安排运输，使得在满足所有商店需求的情况下，总运输费用最小。”

“这是个网络流问题，啊，我最讨厌网络流了…你模要怎么建？”

“这是典型的最小费用最大流，需要在最大流的基础上，增加边的费用，找到总费用最小的最大流方案。首先需要添加超级源S，向所有工厂连边（容量=产量），然后添加超级汇T，所有商店向T连接（容量=需求），用差分约束系统SPFA或者Dijkstra计算最短费用路径，用EK或Dinic增广路径求最大流。”

“好的好的，明白了。”姜明?连忙点头表示自己听懂了??其实他并没有听懂，但为了不让旁边这个疯狂算法怪继续在自己耳边?嗦下去，他只能装作理解并完全赞同顾梓聿的解题思路，好让他老人家心满意足地回到自己的草稿纸中去。

该说不说，人比人气死人，今天的训练题一共就5题，他俩一起到的，他还在第2题，顾梓聿已经做到最后一题了。虽然目标是尽量在规定时间内完成尽可能多的题目，大家都在埋头苦干。但毕竟规定时间是5个小时呀，顾梓聿你能不能做个人！

傅尧专注地盯着自己的代码，他用的是Dijkstra，但某个测试点始终报错，磨了很久还过不去，他忍不住低声自问自答：“难道有负权边？可题目说不会有啊？”

顾梓聿在一旁听到了，随口说了一句：“不会是0作为权值吧？如果有0，你Dij可能会出问题。”

傅尧愣了一下，迅速修改代码，提交??Accepted！

他不禁心悦诚服地长出一口气：顾梓聿果然还是强。

旁边的黄颖听到顾梓聿的提示，看着自己始终没有思路的题目，还是忍不住发问：“顾梓聿，你动态区间最值查询用的是线段树还是树状数组？”

顾梓聿一边看着自己的伪代码脑子飞速转个不停，一边答道：“看你怎么考虑了，树状数组应该更快，但如果是动态区间修改的话，树状数组可能不太好扩展。你可以两种都试试，看看哪个更适合。”

“对了黄颖，”姜明?插了句嘴，“待会儿做出来之后记得分享一下啊，我还没做到那儿呢。”

黄颖点点头，站起来伸了个懒腰，又重新回到座位上认真钻研。

“诶，彭昱呢？怎么没看见他？”姜明?磨了会儿洋工，突然意识到好像冬假都没看见彭昱的影子。

“他请假回家过年了，可能开学前会回来的早点儿。”张铎的声音闷闷地响起，“顾梓聿，你做到第几题了？”

整间机房里的耳朵都竖了起来。

顾梓聿不好意思地笑了笑：“我今天只待一个上午，所以比较赶哈，你们慢慢来。