lzw视角: http://www.cnblogs.com/vb4896/p/7754224.html

 

Day -1

 

一大早和sfiction/zya一起从玉泉出发去机场,前一天上毛概的时候因为台阶太高体重太大,崴了一下脚,走路下楼痛苦异常。星期三和学长们整理模板的时候,发现每个人都要带一大坨模板,lzw甚至还要带一堆数学类书籍,书包感觉要爆炸。

路上sf一直和我们两个讲述实习做些什么以及一些奇奇怪怪的算法题,感觉很diao,没怎么听懂。

到达西安之后,坐了三个多小时的车,终于到了西北工业大学长安校区,感觉横跨了整个西安,及其偏僻,就在秦岭脚下,是个大农村。坐了总共58站公交车,而且这个公交车异常破烂而且开的十分勇猛,一路上尘土飞扬,到达西工大之后感觉卵子都要被颠出来了。

在西工大报道的时候,发现每支队伍都要拍一张羞耻照片,滚榜的时候用。在我们后面拍照的是南京大学的三支队伍,三支队伍中竟然有4个妹子,而且还都很可爱,想到浙大集训队已经好久没有女队员了,感觉心情有些复杂。

西工大食堂提供给我们的饭菜卖相异常糟糕,味道也很一般,但还是坚强的吃完了…之后就到达了著名的秦龙温泉酒店,水里面意料之中的有奇怪的水锈,床单上竟然真的有奇怪的血迹,马上叫阿姨来换了一个。房间意外的没有像知乎中说的一样,到处都是用过的避孕套,感觉还是有一丝开心。房间窗户对面就是个KTV,有几个中年老男人唱歌唱了一晚上,心情烦躁。johann过来帮助lzw调红黑树,我则在床上睡觉,因为一些奇怪的原因,lzw的红黑树没有调出来(

lzw放弃红黑树之后,三队四队一起出去吃夜宵,发现方圆几公里内好像只有一个饭店,jyw学长在上菜前感觉好像察觉了什么,找了个借口溜了,但是我感觉这个饭店好像还行啊?

 

Day 0

 

三个人刚到热身赛的现场,johann在试键盘的时候突然发现这个键盘的tab键掉了,感觉要报警。让志愿者去换了个键盘,结果是个游戏键盘,退格键异常的小,感觉更爆炸了。想让志愿者从其他地方扣个tab下来再把我们之前的键盘换回来,可是志愿者说已经没有键盘了,还在不停的道歉,不知道我们的态度是不是过于凶狠…

热身赛赛前五分钟竟然就发了题目,lzw发现A是一个快速幂猜数题,lzw马上打了个快速幂,然后我上来就猜了个2017,比赛开始后10s就交了,发现run id已经是18,似乎已经没有一血了。结果我们竟然拿到了猜数题的一血,一群人过来拍照,瑟瑟发抖,感觉人品已经败光了。

B题是个大模拟,非常的烦,johann写的十分不顺,我和lzw讨论C,发现和七月集训的一道题差不多,用线段树维护一个转换环,所以决定等johann写完上去看看转换环的长度是多少,结果发现并不是一个环,要先转换6次左右才能进入这个转换环,还要魔改一下,记录当前节点进入了状态机的哪个状态。这个时候突然发现UESTC五分钟就过了这个题目,感觉很震撼,似乎是个暴力就能过得题。但是因为是热身赛,所以还是让lzw上机写正解,然而一直在WA。lzw debug的时候,我上去打了个暴力,johann提出了一个小优化,竟然真的AC了,感觉这个数据好垃圾…

之后又测了测栈深度,java什么的,感觉还算合理,lzw的C题正解到最后也没有debug出来。

晚上回到宾馆,先是和lzw一起debug C题,终于发现了一个很隐秘的错误,对拍了一下感觉是对的。然后在lzw的督促下边看《非诚勿扰》边用java的bigDecimal写去年china final的E,冒泡排序的傻吊方法很快就过了,然而结构体排序研究了半天,感觉排序已经对了,不知道为什么就是过不了,后来终于发现原来是ArrayList没有清空…感觉很傻。经过了一个充实的晚上,11点就上床睡觉了,因为晚上过于充实,直接导致了lzw的概统小测获得了1分的高分。

 

Day 1

 

有剧透,之后要训这场学长们请谨慎观看

到了正式赛现场发现键盘竟然换了回去,感觉很开心,昨天凶狠的态度似乎获得了回报。

比赛开始后,题目里面有个标题叫Lover,还有个标题叫Lover 2,johann就唱起了《Hop》,吸引我也跟着唱,感觉有毒。马上johann发现B是个傻吊贪心,然而用set贪了半天,一交就WA掉了。三个人看了一会,感觉也没看出什么错误,后来才发现需要用multiset,B2y16。之后我和johann看F,发现好像不会啊,不知道他们是怎么过的,叫来lzw看他也觉得不会…此时感觉我的心态已经有些爆炸了,但是因为平时训练也经常前期爆炸,所以感觉还是比较正常。lzw转去开了G,发现是个很傻的按位处理,就上机去写了。我和johann继续讨论F,johann发现F是一个马尔科夫链的随机游走,然而就我掌握的知识而言,这种题我只会高斯消元,可是数据范围太大了。lzw因为忘记取余,G又WA了一发,改了之后G2y41。这个时候F已经过了一堆人,榜上已经看不见我们了。

lzw发现我们还在卡F,就又去开了H,发现是个傻吊线段树贪心,就接着上去写。我和johann走投无路,只能猜了个公式,lzw的H写的很顺,一下就过了H1y63,然后我上机打了F这个猜的公式,竟然也过了F1y65,感觉莫名其妙。这个时候我们在榜上冲到了第六名,获得了本场比赛的巅峰。三个人的心态有所好转。

然后lzw发现A只要线段树维护一下线性基合并就好了,也没有仔细算时间复杂度,上来就开始写,赛后sf说我们的时间复杂度其实不太合理的…然后lzw写好之后,我去看了一眼,发现在算线性基之前有个小地方需要按位处理一下,就让lzw改了改。交了就过了A1y92。在lzw写A的时候,我和Johann很快想到了枚举然后bitset优化容斥的做法,我上机开始写,很快写完了。发现样例及其难输入,是一个长度为500的随机01串,非常的烦。我敲了半天样例发现不知道哪里多敲了一位,心态瞬间爆炸,想不测样例了直接交题吧,被Johann摁住,然后Johann开始输入样例,发现果然没过样例,找了几个奇怪的错误,终于通过了样例,交了就过了J1y143。这个时候我们是全场第9名。

看了看后面的题目,EIK都有人过,但是都不超过五个人,但是感觉要想拿到金牌,可能还是要再过一题。虽然后来发现,就算我们之后没过题也是有金的。

很快我们讨论起了K,lzw很快表示这个题肯定要用到Hall定理,但是怎么用不是很清楚。然后我们很快发现只要看看每个子集的最大值对应的lover个数就好了。然后lzw和Johann分别提出了一个转化,我们都觉得Johann那个转化好像比较妙,但是想了半天都不会,就回到了lzw的转化,然后我很快发现lzw的转化可以用莫队+线段树来维护(怎么tm又是线段树),但是感觉复杂度爆炸。就先让lzw上去莽,我掏出了莫队的板子想让lzw抄,结果lzw说“莫队很简单的,我闭着眼睛也不会写错”。写完之后喜获TLE。

然后我们陷入僵局,lzw和johann看起了I,我接着想K,他俩很快发现这个I好像也是个莫队啊,因为维护的数字不超过10个,所以随便搞搞就行了。然后把K写好的莫队复制了上去,写完一交,又是TLE。看了半天,感觉没什么bug,如果是个卡常数题目,那就很绝望了。我们在本地gen了一个大数据,发现奇慢无比。然后看了一下,发现莫队忘排序了…排了序一交,又是WA。

然后我掏出了莫队板子来对代码,发现lzw的莫队顺序写错了…改完一交I3y269

最后30分钟给我乱搞K,交了一万遍,还是没过。赛后发现标准算法是把我们的莫队优化掉了,其实只要two pointer一下就好了,感觉非常傻,不知道为什么四队没想到我们也没想到。

赛后sf一直说要迟到啦,让我们鸽掉滚榜和颁奖典礼,导致我们没有领到奖牌也看不到终榜。结果提前四个小时到达咸阳机场,gtmsf。

最后结果是我们第17名,四队第21名,七队第58名,总共357支队伍。我们和四队是金牌,七队是银牌,都还算比较满意的成绩。我打了两年ACM,也拿到了第一个金牌…可惜队友和去年已经不一样,我永远弥补不了去年北京写错上下界网络流的遗憾了..

 

经验教训

 

  • 这场比赛题目质量似乎比较一般,不知道为什么有这么多线段树,所以lzw写的题目太多了,感觉lzw被掏空
  • reku这个傻吊连个ST表都要抄板子,怕不是个残疾人?
  • 不要过于自信,必要时要多看模板
  • 最后比较大的失误是K题一直沉浸在莫队中无法自拔,其实K比I要简单多了,我们应该有能力8题的
  • 明年去西安的学长们千万不要住秦龙
  • 告诉带队教练,从西工大打车去咸阳机场,很稳的,只要教练付钱就好了

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注