NOI2014酱油行

刚刚从深圳回来,在NOI2014打完酱油后有感,撰。

风景

这次到深圳来的主要目的是观光(sad),所以先放点风景。 领导发言一直强调深圳是个海滨城市,但把我们所在这个山里面是几个意思。。

1 2 3 4 5 6 7 8 9 10 11 12

酱油记

day1

Day1真是给酱油行开了个好头。开赛前老大一直表示比赛会很简单,我却丝毫没有领会他的良苦用心。写完100+70+??就自信满满的弃疗了。考完发现有203开始还挺高兴,然后愉快的看到所有人都200+。。自信过头,T2老老实实写了70分暴力,一分都没想多拿,听说好多人各种骗分卡时就过了当时就想问候出题人全家TAT。题答33分还算可以,听完题解彻底崩溃了,原因是后5个点找回文我一个点都没写,完全没有观察数据直接骗1分,sad。

统计完成绩发现离金线还差20多分,想着反正也是D类也签不了保送就接着酱油好了,于是晚上欢乐掼蛋到1:30

又发现学校去年拿Au的day1全都170-真是喜闻乐见。

day1.5

社会实践本来有雷柏和华为可以参观,到了前一天晚上发现只能参观雷柏,大家都想着造鼠标的有什么好参观的就都不去了,改在电子阅览室浪。下午的演讲还是没人去,不过听说挺有意思的倒有点后悔了,阅览室里没网能做的事情实在有限,下午几乎都在玩手机。。

day2

抱着酱油的心态去了。前一天晚上也没好好睡反正各种睁不开眼。 day1题目比较水所以想当然的以为day2会很难(貌似讲题解的时候某老师也是这么说的)。结果看了T1发现只要写个KMP都不敢写,虽然最终还是写了但一直到成绩出来前都很虚。。觉得T2开始写了个$O((NM+N+M)*(N+M))$的暴力,差不多就是维护取过的点的序列然后每次在序列里面扫一遍看是不是合法,插入就直接用类似于冒泡的方法,一共插N+M-1次所以不会T。后来发现判断的时候可以直接在序列里面二分,但感觉会T,然后犯了个大错:我当时以为会T的地方只是插入排序,于是构造了个排序满的数据发现完全不T,非常自信。成绩出来发现还是T了而且T如狗才想起来我构造的数据取完前N+M-1个数后就结束了,因为他们都合法。于是看着60的分数就呵呵了。

T3更是奇葩,大家都看出来是凸包就我看出来是半平面,原因是我对式子做了个变形。。原来是

$$ f(i)=\min_j{{f(j)+dist(i,j)*p_i+q_i}} $$

dist(i,j)写作dist(root,i)-dist(root,j),记d(i)dist(root,i),然后化成

$$ f(i)=\min_j{{f(j)-d(j)*p_i}}+d(i)*p_i+q_i $$

于是每个点维护直线$y=-d(j)*x+f(j)$,每次取i号点父亲到根的路径上所有点的直线下方的半平面的交,用树链剖分套线段树套平衡树来写,复杂度是$O(N{\log^3N})$,当时觉得自己不可能写得出来,看了下数据范围又觉得会T,本来是不想写的,但拍完前两题还有2h+觉得反正也没什么事做就写了,最后写写停停写写停停写到还剩一个query的时候比赛结束了。。

赛后看成绩100+60+30果然Au无望。讨论后发现T2有个很简单的优化可以去掉log,就是用一个bool数组维护每个点是否合法,这样可以$O(1)$查询,插入点后把他左下和右上的矩形全部赋为false,这样每个点最多被赋一遍。又发现有人和我复杂度一样也过了,当时我就傻了,我二分还能比我快?又想了想,发现二分里面全都是取模,每次二分有5、6个取模。。

本来考完了想开始浪了,发现好多人day2跪烂了,尤其是一些高二没保送的,比如zyn zkc xzt。。洋溢着悲伤的气氛。。

晚上线出来,离Au差了50分,想了想这些题,觉得有各种方法再捞50分。。syf神预测自己Au倒二,和智障签了THU。和前面提到的同样忧伤的还有A类银牌rank1的gyh,去年就签了THU一本今年还是这样,注定要高考。

吃饭时候发现省中有高二烂掉的传统!!

晚上还是掼蛋到深夜,还来了发惊天大逆转。。

after day2

浪。 智障给普及组+提高组出题,帮他写个暴力,跑得比标算还快。。最后用一种神奇的构造数据方法卡掉了,简直流氓。