买教训
Ruchiose高高兴兴地来到了NOI赛场上,在赛场上他久违看到了买老师。
买老师:“一切皆可买!Ruchiose你要不要看看我的货。”
Ruchiose:“都有些什么呀?”
买老师:“有许多教训。”
Ruchiose:“给我来两斤……”
买老师:“先给你这个豪华精装版的教训。你Day2的T2的memory是多少?”
Ruchiose:“225M左右。”
买老师:“你压位了吧。”
Ruchiose(唱):“呀喂……”
买老师:“你用什么压的。”
Ruchiose:“STL bitset。”
买老师:“STL bitset用用人生还有希望的?在不开O2的情况下STL bitset比手写int压位慢几十倍。考虑2.5e+7次访问和2.5e+7次修改,这个差距大概是一点几秒。你看看你T2的成绩。”
Ruchiose看了看成绩单,发现T2的标算被卡成了60分,而且最慢的点跑了5.7s,一股浓浓的常数写渣的味道。Ruchiose感到非常沮丧。
Ruchiose:“这个教训太昂贵了,有没有什么物美价廉的教训?”
买老师:“有啊有啊。你T1是怎么做的?”
Ruchiose:“哪一天的?”
买老师:“Day2的。”
Ruchiose:“我做过CF,这题我一眼秒。这题就是CF 432D,都是建出next数组的树后搞,只不过432D中有用的是一条由N出发的链,这题是整棵树都要用到罢了。”
买老师:“然后你就O(nlogn)地倍增了?”
Ruchiose:“yeah。”
买老师:“多想想。”
Ruchiose想了一想,发现如果从ExKMP入手的话是可以做到O(n)的。自己毕竟还是too young,买老师是身经百战了,见得多啦,一看到数据规模里有80%和100%两档就知道标算不是O(nlogn)。 Ruchiose一看成绩单,果然只有80分。Ruchiose感到非常沮丧。
Ruchiose:“老板结账。”
买老师:“zoo 20分,random 40分,总价60分。”
Ruchiose发现自己预估的是570分,付了60分以后可能不够买金牌了。这让Ruchiose感到绝望,买老师。
买老师:“我们正在暑期大促销,省队A类选手凭证件买金牌有优惠价,不要543,只要508,只要508,金牌带回家!”
Ruchiose感到人生大起大落,感觉考前SRM的250分题莫名其妙FST攒下的rp终于爆发了。虽然教训和金牌都入手了,但是后来他发现一些大爷如Fancycoder等分数比自己高却没有优惠价,只能带银牌回家,也感到自己的金牌受之有愧。但不管怎么样最后还是混进了集训队,多想想,以后还有的是机会打翻身仗啊。