NOIP2018游记

2018/11/12 22:47
阅读数 14

高清重制版 于 12.17

Day -1

上午考了qbxt的模拟赛2
T1 T3 都是书上问题,我没打树剖都切了rp--。T2被卡边界卡了30分,rp++。
菜是原罪,还有100天就要省选了,我连树剖都没打过。

下午教练让我们依次说些注意事项?
我:直播上知乎:link,rp--。。。

晚上透彻rp+=rand()%2-0.5

Day 0

由于这次拉了20多个高一学弟学妹们,这次我们包车去秦皇岛。
早上五点五十出发后,果不其然,HE又下了大雾。无奈走下道,下道肯定是很慢的。
过了衡水收费站,走S282往北走,逐渐地天亮了。 水汽还凝结在窗户上,窗外的景色也模糊不清
车里同学们有的还在睡觉,而我在膜lrt(大雾 膜人并不会掉rp啊 不过rp--
中午11点多,大雾散得差不多了,太阳还是若隐若现,已经到了霸州了,终于能上高速了。
上了荣乌G18高速,lrt感觉心情顺畅了许多。过大沽时候,路边的风车吸引了我们的眼球。
已经到了秦滨高速了,司机师傅给我们放了奇怪的电影,我并不想看,颓了会儿窗外荒凉的风景
终于,下午三点半到了YD。累tm死了。。。

先去第三教学楼试机。由于我很菜,敲了发树状数组就不知道敲啥了。教练找到我,告诉我我在第八考场??
当时我很纳闷,考场不是晚上才知道么 后来才得知,今年人多,在信息馆那边又单独设了一个考场
失去了和这边dalao谈笑风生的机会,不过也趁机在YD多转悠了一圈。。。
去那边转悠一圈后腿很累,终于要去入住了。这次我们订的YD宾馆,据说不咋地,不过离考场近也很好吧
进屋之后,转悠一圈,发现屋里的插座是坏的,没有电,差评。。电梯停运了差评(记得之前看过某dalao的博客里说YD宾馆的电梯很不稳的,这次竟然直接停运了)
晚上本来想和leizi去找拉面馆的,结果被主任勒令去宾馆的餐厅吃晚饭。12个人一桌,饭做得还不错,不过一盘菜对于12个人来说,一人一口就吃完了。
吃完饭被主任勒令回去看书,幸好带了《线性代数》。
晚上开完会后并没有洗澡,呆了会就直接睡觉了,保证Day1的状态

Day1

早上吃宾馆自助餐竟然没有蛋炒饭差评不过有吃的已经不错了

教练带我们去第八考场,没想到主任没有跟着大部队去第三教学楼,竟然跟我们去信息馆,当时就担心主任奶我
然而...主任进场前真奶了一句,影响我Day1 AK,Day1真的没有AK

进场了。8考场座位没有靠背差评,不过是俩人面对面的桌椅摆放,去厕所不会碰到挡板好评。挡板做得没去年的高级中评
有Notepad++好评!!!

8点半发卷了。 先看T1,看完一遍一看这不洛咕原题吗??什么积木的那个??那道题正解记得很清楚,因为做那道题时候我在机房里炫耀不用数组就能AC。
然后是T2,一看这个表示式子像是线性组合的那种式子,就一个劲往线性基上想估计是受线性代数影响过深了,后来发现不满足八条公理。期间穿插看了T3,没看出来T3正解,部分分倒是比较简单。后来一看,由于a是25000以内的,所以可以用类似筛法的做法,枚举数字,枚举所有已经被筛掉的数,枚举差去筛数,YY出来一个O(n25000^2)的做法。然后一看,这里有很多重复标记,完全可以写出O(n25000)的做法,然后对拍过了。出了考场后才发现这不是完全背包转移吗。 果然,数学和DP分不开。T2简要题解:

我们把给定数组中的能够由其它数字表示的数字删去,剩下的数不能互相表示,这些数字的数量即为答案
由于a最大25000,所以可以开个vis数组表示某个数是否能被表示
从小到大检查每一个数是否vis,如果没有就把它加入,然后枚举所有vis为true的数,完全背包转移
复杂度O(n*25000) 然后是T3,先想出来了二分,干完T2后,莫名其妙地就想出了正解,然而卡在最后一步用multiset上了。那一步就是给定一个数列和一个阈值mid,然后要求将数列里的数两两配对,每一对的和大于等于mid。要求最大化配对个数,但是如果有剩余的数字没有配对,要最大化这个数字。我想先排序然后O(n)双指针维护但是炸了,写链表发现复杂度不对又炸了,反正大样例死活出不来。写了三次,炸了三次。然后看快没时间了,写了个N方暴力走人。顺便写个生成数据跑一下,菊花图50ms????不可能。出考场后回忆才发现忘了生成m了,50ms是输入的用时。

考完后发现我那种方法是给<=3的部分分的,菊花图肯定T到飞起。Day1估分:200+
本来Day1是能AK的,T3炸了。出了考场之后并不知道全世界都在刷AK,而是听教练说三道题都是原题。心里并无波澜,记得教练之前说过480pts可能去PKUWC或THUWC,想着这个,说明day2要继续稳住。记得以前zyl(upd:突然想起来,绝对不是zyl说的??)说过,一切都是最好的安排,听从出题人的安排就行了

中午吃盒饭不错。

中午听第三教学楼那边说,olinr被我奶凉了,t2没推出来。。。好多人好像都凉了,但是leizi好像AK了

看完丑陋的程序后去海边转一圈。今年4月HEOI2018时候并没有去海边,所以说这次是今年第一次也是最后一次了吧。lrt说我把他的rp奶没了,他要捡贝壳把rp捡回来。我转悠了一圈,WA了个沙坑来洗手??来体现我的幼稚心理。那天真的不是很冷,并没有穿羽绒服,还把校服褂子脱了,感觉不错。
回来时候,海边有个很小的小岛???(貌似是海平面上升造成的),距离海岸两米,雷子成功地跳到了岛上,然鹅,cjh和js都踩水了。回来时候他们都踩水了。幸好体育不好的我没有去。

回来后又被勒令看书,于是和GMPotlc下五子棋,GMPotlc真的是大佬,赢了我三盘。
晚上在楼下等盒饭时候,碰到了bike大佬,貌似是明天来讲题的。主任竟然还记得2月份他给我们来培训过,记性真好。
晚上洗了个澡 舒服 然后跟GMPotlc扯淡扯到11点影响Day2的考试,GMPotlc竟然口出狂言自己奶自己,说得我迷惑不解,果然Day2毛琛凉了

Day2

(按照时间线写了一遍)

由于昨天晚上和GMPotlc聊天过晚,早上起来有点困但是比学校里好多了
走的时候,主任终于不跟我们去第八考场了QAQ好险 不过Day2都没上200分(其实是197pts)
由于Day1在第八考场,并没有感觉Day1题有多简单,心情一直很平静,并不知道Day2要出毒瘤题
到了信息馆4楼,xjb呆了会就进场了。

8点半发题,先看T1,一开始一看以为是神仙题,然后看数据范围,n=m或n-1=m??n,m<=5000?不就是个沙比题了么 n-1=m是树的情况直接贪心搜,带一个环的情况就枚举断边不就得了,复杂度n方的
然而认为n方能过5000的我直接打了,并没有敲tarjan什么的,最后卡常88pts
再看T2?貌似是个状压??矩乘??不对不对。。不管了去看T3
T3?不是那个什么什么树形dp吗?这个限制怎么整??
于是在T2和T3中先写了些T3的暴力,每次重新dp,44pts。然后发现T3一条链上可以维护区间什么什么信息然后瞎搞搞?写了个奇怪的倍增算法,24pts。T3一共68pts,想想已经够了,回去推T2
然后推出了个重要的性质,如果按照副对角线递推,就不用状压了,因为要保证右上方都是1,左下方都是0。然后把dp推出来了,只过了n=2的树,然后推出来下面的结论:(见下),然而为了正确性写了好久,边角的需要特殊处理。。。然而好像只有n=3的能过,不管了,反正也就50分那样。。。
对于n=3,只要存在以下子块的方案就是不合法的

 X
X  0
  1

(其中X是0或1,保证两个X一样)

中午盒饭好评。

下午1点半上大巴回衡水,走G1->G95->G45,一路顺畅成功地避开了所有堵车点
司机师傅好心又给放电影辣,我又没看,因为我要记路方便以后装B

八点到学校,去机房安顿了一下后,回到了教师听毒瘤班主任swh讲语文(详见文化课划水记)

11.17

这天终于上OI课了。洛咕数据测440; 牛客425。。。
D1T2洛谷上被卡常了5分
D1T3由于写的N方,不出所愿,菊花图被卡了。二叉树跑的还可以。
D2T1都被卡了后三个点(我分析复杂度明明O(n^2)是能过的?难道我分析错了?)
D2T2忘了考虑n,m=1的情况和m>n的情况了。。挂的很惨
D2T3倍增果然写炸了。。。幸好暴力分还有44分
leiziD2T3绫分,总分都比我高,肽聚啦 leiziD1AK了%%%%orz
GMPotlcD1晚上使劲奶自己,D2果然考炸了QAQ

今天开始啃网络流了。第一次自己想建模思路
各种毒瘤数据结构等着脱产后吧。
不过我ghj1222依旧保持着对数学的热爱(尽管现在选修2-1椭圆啥都不会啊,好久没做高中数学题啦)
其实是对线性代数的热爱罢了
NOIP总分四百来分,希望接下来备战省选的道路上顺利吧 NOIWC冬眠营应该能去,THU和PKU的就不清楚了...

11.19

中午拿教室的多媒体查成绩,CCF咕咕了。。。说好的放成绩呢。。。晚上有OI课了,说咕咕到第二天。。。

11.20

按照惯例早上成绩出来了,因为忙于文化课没去查。
大课间跑操时考哥说我前十,我想我是巨佬??不存在的//其实按照二中惯例,这里的“前十”一定是第十
第五节课开了个啥表彰高一期中大会,还让我去FA♂言,而且还是在我到了礼堂之后我才知道我有发言的,而且我还没拿笔没拿纸。。。
于是站在台上脑子一片混乱,献丑祭而且还被莫名其妙地奖了点开封菜,我这种蒟蒻怎么能被奖开封菜呢//详见学校官网"高一奥赛期中表彰大会"
回班从swh口中得知我467pts,果然比洛咕数据高,心想这分还凑活 不过去年还是高一第七呢,今年成第十了。。。
中午吃完饭和开封菜(分了好多出去),想用教室里的多媒体查下分,CCF NOI官网炸了。。。
晚上上了OI课,终于知道全省成绩和自己的分(100+100+70+88+45+64)了,感觉申诉找不回来分//反而会让我的名次倒退
用Cena测了一遍(lemon还要提取文件夹麻烦死),D1T3感谢少爷机,D2T2炸了一个点,D2T3数据水,倍增只炸了一个点
果然是rank10,和ywy大神&&shadowice1984大神一个分,感觉自己好菜啊。。。这在zj就是一百名了
不过往后看,YoungNeal/wjh/Zhang_RQ/KingSann/ivanovcraft大佬都比我强为什么他们分偏偏比我低呢

12.4

HE分数线出来了,330pts,一共83个省一,从2016年以来,OI一直保持着很高的省一率。。。 我们机房7人省一 GMPotlc大佬差1pt省一//谁叫他day1晚上奶自己呢,//默哀。。。
ZAGER大佬差2pts省一
去OIerDb查了下,467pts都没进全国前500,刚好508,我太菜了太菜了

后边的删了

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部