一定要跑三遍

· · 生活·游记

声明:Floyd ijk 写法要跑三遍,ikj 要跑两遍,kij 是正确的。

ijk 写法指的是 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);,即不妨设后面的语句是 f[i][j]=min(f[i][j],f[i][k]+f[k][j]);。

上课时学长讲"易错点",大家昏昏欲睡。为了醒瞌睡,学长使出看家本领,讲了一个故事。

一个在 CSP 的考生,T2 写 Floyd 以获得分数。CCF 的评测机有一个不成文的评分标准,即 for ijk 写法必须用循环跑上三遍。运行的时间是按次数计算的,这位考生计上心头,循环时少跑两遍。果然,代码常数大大减小,运行效率便大大提高。旁边的考生向他请教技巧。他毫不避讳,说:"你看,跑了三遍的 Floyd 和跑了一遍的有什么区别吗?少跑两次嘛。"旁边的考生诺诺,却与他渐渐疏远了。

CCF 主席偶尔抽查一下 Floyd 的正确性。一次抽查中,主席用特殊构造的数据测出 Floyd 正确性不够并责问我们这位考生时,他振振有词:"跑一遍和跑三遍不是一样保证了代码正确性吗?"主席只是淡淡地说:"你是一个不诚实的人,请你离开。"

为了成绩,他又参加另一场比赛。这位主考官打量了他半天,才说:"你就是那位只跑一遍 Floyd 的考生吧。对不起,我们不通过你的审核!"第二场、第三场……他屡屡碰壁。不仅如此,他的教练不久也要求他退竞,原因是他的"名声"对其他同学的成绩产生了不良影响。他就读的学校也专门找他谈话,希望他能转到其他学校去,因为他影响了学校的生源……万般无奈,他只好收拾行李搬到了另一所学校,一切重新开始。他痛心疾首地告诫准备参加 CSP 的考生:"在 CSP 写 Floyd,一定要写三遍呀!"

"这就是易错点!"学长厉声棒喝。我们不禁悚然动容,睡意全无。