去年我都做了些什么?

买教训

Ruchiose posted @ Aug 01, 2014 08:54:47 AM in 未分类 with tags NOI , 1100 阅读

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等分数比自己高却没有优惠价,只能带银牌回家,也感到自己的金牌受之有愧。但不管怎么样最后还是混进了集训队,多想想,以后还有的是机会打翻身仗啊。

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter