第4章 四道题

林景摆烂了好一会，大抵是看刘希和颜安都还没有放弃，搞得他也有点不好意思，重新振作起来后将题目阅览了一遍。

刚才刘希与颜安的对话他都听到了，知道这次考试的难点在后五题上，于是率先看起了倒数第五题。

有n个人，m个课。每个人有一个擅长的科目的集合，范围是零到二的m次方，需要选择一个两个人的队伍，使得这两个人每个人都至少有一门科目是他会但对方不会的，求选择的方案数。

其中n的范围是二到十的五次方，m的范围是二到二十一。

经过一阵思考后，林景初步确定了解题思路，具体实现还得要上手敲代码把他没注意到的细节部分处理好才行。

看了一眼正在努力敲代码的颜安，才发现他那双手就没停下来过，仿佛正在敲的不是代码，而是小说一样。

可就算是小说，那也该偶尔停下来思索一番才对。

这种一刻不停地状态，林景只有在写基础题的时候才会进入，稍微有点难度的算法题就需要谨慎考虑慢慢写了。

颜安那架势看着就不像是在写最后五题的样子。

他不会是想用穷举法破解吧？

林景脑袋里没由来的冒出这么个念头，毕竟有的时候碰上实在不会的题目，他们也会用穷举法试试，说不定能因此获得些解题思路。

只是现在不比平时训练，他们是在考试在竞争，哪有那么多时间浪费，有这写穷举法的时间还不如多写两道题。

一想到这，林景就知道该自己出手了。

“要不让我来吧？我已经有思路了。”拍了拍颜安的肩膀，林景压低声音说道。

队伍的攻坚手是他，让一个大一新生来做这几道最难的题目，实在是有些为难人家了。

林景对自己之前的摆烂行为感到非常羞愧，连颜安都没有放弃，他作为队长怎么能好意思做出这种事来。

哪知颜安头也没回，两眼盯着屏幕，上面的代码一行接一行飞快的冒出，“学长等下，我就快写完了。”

随着最后一个关键字被敲出，颜安的双手终于停了下来，机房内陷入了短暂的沉寂中。

“学长直接开始写下一题吧，前面的我都写了，这道题我思路有点不太对，正愁不知道怎么写呢。”

颜安指着纸张上的最后一题说道，让林景听得一愣一愣。

这才过去多久？就已经写完了四题？

林景下意识的看了眼时间，确认了现在距离题目发到他们手上才只过了二十分钟而已。

又看一眼身侧刘希学姐的进度，也是四题，乍一看好像两人进度一样，可这才是不对劲的地方。

刘希写的那是试题的前四道，堪称最简单的四题，只是开胃菜而已。而颜安写的那可是倒数五题，是硬得啃不动的大菜。

他两的速度居然一样？

林景感觉这场竞争忽然变的玄幻起来。

且不说颜安写的那几题可能连他都无从下手吧，就算是用穷举法，那也不可能写这么快。

除非他那四道题都是乱写的。

不是没有这种可能，就像他在这种重要时刻还在摆烂一样。

林景怀疑的看了眼颜安，“我只是有了倒数第五题的解题思路而已，最后一题暂时还没看。”

他顶替了颜安所坐的位置，将注意力放在了颜安的代码上。

是不是乱写的他一看就知道，也不用顺着代码的逻辑去捋，将倒数第五题的代码找出来并拉到最底下，发现只有二十五行。

这种简单粗暴的方式印证了他的猜想，颜安果然是在乱写的，因为即便是他来写这道题，也很难将代码量压缩到这种地步。

虽然他还没开始写，但初步预估就得要四十行代码，完全不是颜安这种二十五行代码能解决的题。

如果颜安写的其他题目也是像这样只有二十几行的话，那二十分钟搞定四题完全不成问题。

可这有用吗？代码追求的是短小没错，但还有个最重要最基本的前提是得能运行出结果。

没有结果的代码，还不如穷举法。

如果靠短就能拿分的话，一句“Hello，world”岂不就是全场最高分。

林景默默叹了口气，内心早已麻木。

他还以为学弟是不放弃精神，结果等他振作起来一看，哪里是不放弃，这分明是摆烂加自暴自弃加自欺欺人。

痛苦的揉了揉太阳穴，删了重来吧，连看都不想看直接就选中全部按下了退格键。

正在一边等另一台电脑启动软件的颜安注意到他的动作，“学长你删我代码干嘛？”

这未免也太过分了。

就算是以前他发现了学长的错误也没有这么干过啊，他还好心好意的加上备注指出错误并提出自己的观点，然后发回给学长。

他这么好心，结果换来的却是这样的对待。

一把从学长手中抢过键盘，还好能撤销删除操作，颜安将代码恢复后立即点击运行。

没等多久，控制台上出现了代码的运行结果，“你看，这代码是没问题的，可以运行。”

关注到这边动静的老师也走了过来，低头看了一眼屏幕，满意的点了点头。

“结果确实正确，没想到你这两天技术提升蛮快嘛，是不是掉到哪个悬崖下面捡了武功秘籍啊？说出来让老师也去撞撞大运。”

对于他两天没有参加训练的事，老师已经不计较了，至少这技术水平提升了。

放在两天前，颜安就算能写出这道题来，也很难想到用高位前缀来解题，这得需要颜安对所运用的方法非常熟悉才行。

出乎林景预计的结果让他傻了眼，呆滞的看了一眼老师，又看了一眼颜安，发现自己才是那个无知又摆烂的家伙。

连忙给颜安道歉，好在被发现的及时，不然的话林景都不知道自己该怎么取得颜安的原谅。

在这之后，已经知道倒数第五题被颜安完美解决的他并没有立即开始对下一题动手，而是认认真真的开始阅读起颜安的代码。

毕竟如果让他来写，怎么着也得四十行起步，而且要比颜安的代码更复杂，所以就很好奇颜安用的是什么方法，和他比优点在哪。

这一看，就沉迷进去了。

代码精简其中的思想不容易领会，他想了好一会，才明白这是运用了高位前缀和来解题。

由于正面枚举并不好做，颜安就考虑反面情况即题目中两人会的领域，其中一个人是另一个人的子集。

……

那么对于某一个状态S，直接就能得到有多少个状态T，满足T包含于S。

得出答案为 n*(n-1)/2再减掉非法方案。

理解代码后的林景徐徐吐出一口气，不得不对颜安刮目相看，高位前缀难吗？

难也不难，反正他没想到用这个方法解题，那对他来说，就是一个需要补足的点。

看完一题的他立即进入到下一题，这一次没有删除颜安的代码，而是在确定能够运行后再度全身心投入到阅读代码中去了。