UOJ Logo WrongAnswer的博客

博客

FJOI2017滚粗记

2017-04-23 18:25:41 By WrongAnswer

这场省选毁掉了我对好成绩的梦想。

8:00开场看题,T1貌似是可持久化Treap裸题,T2字符串DP似乎挺可做,T3居然是去年原题扩大数据范围,做过。

感觉这场很容易拿高分的样子,想想能A两题再写一题高分就稳了。

于是开场先做T2,求两个长度 $n\le 500$ 的字符串的最长公共回文子序列。一开始以为直接写就行了,结果发现复杂度 $O(n^4)$,还10组数据,没救。

想了想直接上序列自动机似乎复杂度很不满的样子,虽然是 $O(n^5)$ 不过好像能有很多分。

于是花了半个多小时码完过了样例,自己出了几组数据没问题。

再做T3,写了十几分钟过了样例测了几组大数据就不管了。

这时候自信T2拿到高分T3 AC了,觉得只要再AC T1就rank 1稳了。这时候9:00,然而FJOI是4h所以还剩3h= =

最后决定放弃后两题的对拍开始搞T1。T1的意思是这样的,维护一个序列,支持插入、区间翻转、区间第 $\lceil\frac{m}{2}\rceil$ 个最大值下标查询、区间满足 $a_i>a_{i+1}$ 的 $i$ 之和查询、区间满足 $a_i< a_{i+1}$ 的 $i$ 之和查询。这种和两侧有关的信息似乎很难维护。

不过还是硬着头皮开始写了,先码个可持久化Treap……嗯,要维护哪些信息呢?结点的值,子树的最大值以及最大值个数,前驱的值,后继的值,子树中满足 $a_i>a_{i+1}$ 的下标之和,子树中满足 $a_i< a_{i+1}$ 的下标之和,以及翻转标记。

然后写 pushup,写写写……写完了。

然后写 mergesplit,写写写……写完了。这时候代码已经100行了。

然后在前面加了个翻转 revpushdown,每次操作 pushdown。接着开始写修改,写着觉得常数好大,不过 $n$ 范围是 $50000$ 可能不虚。

……

终于写完修改、翻转、查询了~已经11:00了,然而FJOI是4h所以只剩1h了= =

嗯我测一下样例,果然……没过……

把树打出来看,发现几个地方写炸了,改改改,改了好久,终于调过了样例。

11:30。不知道会不会出事情。

于是赶紧写了T1的暴力拍,一拍就错。

手算了下发现暴力写挂了,还好。

改完暴力继续拍,又拍出错了,而且错在十几行。

这回真的是正解写挂了。

11:45。宣布离比赛结束还有15min了。

不知所措。

把树打出来,结果等到WA的时候树已经巨大了,看不出错误原因。

最后纠结了很久要怎么办,决定把我花了2h+的可持久化Treap扔了,交暴力。感觉失去了希望。

又一次死于数据结构。

出考场,听说T1有人写正解有人写暴力,T2大家都写我这个做法,T3大家都能A。完了这么一来我真的要被翻了。

等成绩。

……

成绩出来了。

赶紧看看我的成绩。看到时我就傻眼了——

110。

第1题10分……暴力分……

第2题居然爆0了?虽然我写的暴力但怎么小点都WA???至今不知哪里写错。

第3题大家都A了。

于是10+0+100=110滚了个大粗。

整场花很多时间写的代码都没分,所有分加起来只用了大概半小时。

出榜发现我果然被翻了,zhshr 180实力当队长,ditoly T1 90分,总共180,果然是数据结构大神啊。女队aufeas 200分最高分!!!!!!!!!!太强了!!!!!!!!!然而我只有女队的一半左右,这场rank 10,掉队既视感。

chentong 130分翻盘进队,runzhe2000 100分有点惨不过压线进队了。dick32165401和wzt惨啊……被线卡……(UPD:dick32165401卡线进队了

后来和其他人交流了一下发现他们T2写我的那个 $O(n^5)$ 做法有90分,那肯定是我太SB了哪里写挂了,手抖一下90分没了,rank 1就这么送人了……话说我参加的两年省选二试T2都是这种子序列题,去年我没时间写,爆0,今年我写了结果挂了,爆0。讲大话很简单,我完全有能力得到200分。问题是做到了吗?

好在总成绩还有rank 2……想想我一试高分其实也是因为运气……运气好T1水过去多拿了60分,再加上一试后两题都是水题,区分度很迷。然而到了二试,题目难度科学了,我的辣鸡水平马上暴露了——前两题加起来才拿到10分。不能怪题目,只能怪自己弱。我的实力大概就省队的后几名吧,本来还指望今年CTSC滚粗以后再去NOI冲集训队,冲候选队,再冲国家队的,现在看来真是荒唐,我能进集训队都算运气好了。没有强的实力却每次都想RP爆发考好真是一个笑话,如果我再像之前那样天天颓,真的就要退役了,嗯,多刷Codeforces、Codechef、TopCoder,才能提高思维能力和代码能力,争取做题都能有思路,代码题都能快速写对。


UPD:

人生中最后一次省选被我糟蹋成这样实在是太不爽了。

每年都是一试的优势被二试浪翻,坑在一道代码题上近3h,导致没时间写或检查T2。去年滚粗后希望今年二试能考好,没想到今年又是同样的结局,真是可笑。

省选二试前rank 1,省选二试看到题自信满满,1h内写完后两题觉得剩下3h写T1稳了。然而梦想是美好的,现实是残酷的。为了省出时间我放弃对拍后两题,只手出了几组小数据,导致本来能90分的T2写挂爆0。更何况,由于我糟糕的代码能力,T1我并没有调出来,如果调出来的话能得到60~90的分数,就不会这么惨。最后,花费大量时间的前两题几乎没分,保持排名的梦想彻底毁灭。

教练cy在看到题目时,说T2和去年题类似,大家做过去年的题,应该属于强项。没想到,我们学校出了我这样一个害群之马,在大家都拿到70~90的分数的情况下居然爆0。真是对不起immortalCO,对不起教练,对不起学校。

总是高估自己的实力,有着我能AK的错觉,却忘记自己名字就是WrongAnswer,各种题写不对。在我前面,确有不少实力很强的选手:队长zhshr、女队aufeas、T1 90的ditoly,初三选手fjzzq2002,以及这次省选同样没考好的fateice、pyz5715、victbr……弱者不配拥有梦想,明知我只写过一次Treap却要花近3h在T1上,真是愚昧无知。如果及时想到放弃T1,或许就是另外一种结果。

下一个目标是APIO2017。但愿APIO2017不要这样滚粗了。UPD:APIO再次滚粗,惨啊

评论

immortalCO
“区间第 ⌈m/2⌉ 个最大值查询”是啥?区间K大?
waz
orz
waz
您考挂了还是比我高到不知道哪里去了
1273011572
orz
chentong
orz 钟知AK、钟知AKAK、钟知AKAKAK、钟知AKAKAKAK。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。