dwjshift's Blog

NOI2014网上赛 暴力记

| Comments

原文发表时间:2014-07-30
今年的题目真是水的不忍直视……真·暴力Au……不过我连暴力都没写好- -

day1

从8:30拖到9:50才开始,然后一开始题目根本不是能看的!表格显示不全图片全部没有T3连输入文件都没有,过了若干年才把这些东西放了上来……
看到T1感觉萌萌哒。直接拆位暴力讨论一下,没了。拍了一会就滚去看T2了。
T2我一开始的想法就是先离线按照a排序把一条条边加进图里,然后就只用维护b最大值最小的路径了。但是怎么维护呢?想了想大概是MST吧……但是不会LCT真是各种哀伤……于是只好去想最短路搞一下部分分了。看到图挺稀疏的……spfa大法好!而且写spfa的话不用从头跑一边最短路,加入一条边后把这条边的端点加进队列里,在原来的基础上继续跑spfa就好了。这样不刻意卡的话效率是跟一次spfa差不多的(虽然我不指望数据能不卡spfa……试了一下大样例秒A了,然后就挺开心的滚去坑T3了
我实在不怎么会做提答- -然后花了半个小时手玩第一个点,后面的直接随便弄个能有分的答案,然后差不多就交了……
考完之后q群上的信息挺多的。听说T3 windows下\r\n会爆0,我整个人都斯巴达了。
接着是现场的人说T2数据是随机的,据说有人暴搜剪枝都过了。(现在在bzoj我复杂度不靠谱的spfa都能跑到#2……你们感受一下
最后总分60+100+14(T3一开始是爆0的,不过day2的时候重测了)
又检查了一下T1发现是xor的情况脑抽了……我就郁闷了,拍了那么多次怎么还有错……这时有个神犇提醒了我:大数据随机的话一堆的and 0or 1答案都已经确定了……唉

day2

T1依旧没什么好说吧其实我是误打误撞弄出来的(捂脸
做一遍kmp然后扫一遍就没了,复杂度
T2是我这次noi做的最失败的一题。我写的是分治,对于一个区间,求字典序最小的路径的话,必然会经过区间中最小的一个元素,假设这个元素是吧,然后就继续分治。这样子就需要求区间min……于是我sb地敲了一个二维树状数组。然后我发现,我不会用树状数组求区间min,于是又去写了一个分块……然后写着写着又发现空间太小,边角的地方只好暴力解决了,复杂度有10Y+……最后还调了1h……
然后T3就没时间写暴力了……
出来才知道T2就是一个TG组难度sb题啊!
成绩出来100+60+0,Cu滚粗了。比Ag线低11分T_T
就像clj说的,考场上5h梦游,出考场分分钟AK(虽然我出来也不能AK……不过还是能分分钟Ag的……


另外讲一件有趣的事
clj:“现在NOI的题目太水了,不能忍,明年联合室友出点大难题,让大家感动一下。”
我已经做好准备明年爆0了0.0

NOI

Comments

comments powered by Disqus