UOJ Logo WrongAnswer的博客

博客

FJOI2016爆炸记

2016-04-10 17:28:54 By WrongAnswer

今天福建省选二试。果然,还是我太弱了,完美爆炸。

[以下是废话部分]

早上起床迟了,7点才起来,然后由于自己作死把手机掉床缝里面去了找了好久才找到(还好找到了)。

@Paladin100100 进宿舍催感觉很急于是匆忙吃了个早饭检查了下证就出发了,车上一直看考生须知,感觉就怕哪里看错了- -

来的时候和 @immortalCO 大神交流了一些算法(呸只是聊一聊啥都没交流)接着就入场了。

各种紧张。

[以下是正题]

“估计今天的题会很丧。”我想。

7点55分,电脑右下角时间居然是7:50,卧槽居然不能调?(接着监考老师叫我们把手表摘了于是考试的时候只能把时间加5来推算了2333)

发卷。

一看到题,本人立马傻掉了。

第一题“树的平均路长问题”,题目一开始就是个带sigma的公式,感觉相当不可做,再看后面,靠,居然是红黑树,一堆定义看得好晕。

总之第一题看完就先跳过了- -

第二题“所有最长公共上升子序列问题”,是求两个序列有多少个最长公共上升子序列,这不是和一试的题类似吗?再看数据范围,卧槽,序列长度n,m<=5200,元素范围20000,似乎套不了一试的那种做法,先放弃- -

第三题“n点游戏问题”,等等这是大爆搜的节奏吗?跑了下n<=6都跑不出于是直接弃疗。

第四题“密码破解问题”,树的路径计数,这……点分治应该能过吧。

感觉第一题输入一个数输出两个数而且输入的n<=5000似乎可以打表。试试?

噫……总算看明白了题意,求的是n个节点的红黑树所有点的深度之和的最小值和最大值,推了个O(n^3)的式子,写了一发试了下样例过了!那就打表吧,要求最大值和最小值,那就先打最大值吧,开打……

接着……该写哪题呢?

……第二题感觉相当玄学,不如先写下第四题。

第四题是树上每个点都有'('和')',求有多少条有向路径是匹配的括号序列。老规矩,点分治,找重心分解,然后怎么统计有多少条过重心的路径是匹配括号序列?

如果是左括号个数=右括号个数,那么很好办,但是像())(这种的比较麻烦。- -,再记个“前缀'('个数-前缀')'个数”的最小值如何?比如

( ) ) (

1 0 -1 0

于是最小值就是-1。这样似乎就解决了,开写。[一边写,一边第一题正在打表中]

写了一半,发现统计部分排序的话带log,这样总复杂度变成O(n log^2 n)了,n=100000会不会TLE?[不管先写完再说]

然而我真是太弱了,写了2h多才写完,测一发样例,WA!!整个人都不好了。[这时候看第一题打表打了挺多的,于是就掐掉去打最小值了(后来听说最小值可以贪心构造总之我考场上是SB)]

打了一堆调试语句手画样例总算找出了问题[2333还不都是建了十几个数组然后数组名手抽打错]接着开始对拍,又WA了(此时我的内心简直是崩溃的),再调,终于过了。写个O(n^2)的对拍,过了,幸好幸好。

此时考试已经过去了3个多小时。感觉一阵虚。

那就赶紧补下第二题?

(但我竟然来不及写完了)

敲了半个小时,连样例都过不了。这是爆0的节奏啊!

放弃了。

放弃了。

快结束了,看第一题打表打到了n=4200+,感觉如果没WA应该能挺多分。整理了一下第一题发现打表打了25KB多(打的是差分,所以不是太长),有点虚。

带着第2、3题没写完爆0的遗憾结束了二试。

出考场,问了下 @immortalCO 大神,他写了2和4,目测200+分。

问了下 @lightning 大神,他写了1、2、4,不过1和2都是暴力,目测比我高。

第二题和一试的类似应该很多人都A了吧……第四题裸的点分治应该大家都会吧……感觉200分的人会很多。

然而我2没写!3没写!1、4加起来也超不过200分T T

……

紧张了一个中午,成绩出来了。

我190分。

第1题打表过了90分,第4题100。还好没TLE。

@immortalCO 210分,怒A了2和4。

@lightning 200分,A了4,1和2加起来正好100了。

再看其他人,妈呀怎么这么多200分?(经过后面的分数整理,二试前几名是260,230,220,210,200,200,200,200,200,200我就这么悲催地爆炸掉到rank11了)

rank11。有种上次UOJ Round 12的感觉。

[虽然似乎10分对总rank并没有太大影响?]

还好上一场考不错,于是这场少10分还是有机会进NOI,不过我还是得提高水平啦一定要提高做题速度不然NOI如果没Au照样并没有什么卵用……

评论

chentong
orz zzx大神,我二试数组开炸了是真的爆0了QAQ
FakeAccout
orzorzorz

发表评论

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