NOI2016滚粗记

orz hhw posted @ 2016年7月28日 23:02 in 游记 with tags NOI 比赛 游记 , 1314 阅读

虽然爆了一题,但还是拿了D类第一。然并卵,THU只给降60,文化课太烂了要不起,只好去SJTU了。。好不爽啊

7.22

四川大暴雨,飞机晚点了2个小时。。

然后买不到火车票,只好做汽车。。还好没在汽车站等太久,大概九点多才到ns。

7.23

笔试时kill那道题不确定,一开始选了killall,后来试了下发现时kill。。

惊险拿到100分。。

7.24

T1看上去像Manacher,T2完全不会,T3完全不会

Manacher怎么写啊。。让我背一个。。错了调调调

调出来了,发现不是Manacher。。

浪费了半个小时。。发现还是直接HASH拿95分吧。。

赶紧写了个自然溢出的HASH,调完过了样例就不管了。。

一道水题竟然做了快一个小时。。

T2不会,暴力都不会

看T3,找规律,自己试验一下,发现十进制下就是求gcd(i,j)=1,j分解质因数后不含2和5的对数

那么推广一下,应该是j分解质因数后不含k的质因数吧。。

先写个暴力点的算法试一下。。暴力跑不出大样例啊。。

啊,我会莫比乌斯反演,而且我只会一个公式:Σ[gcd(i,j)==1]=u(d)(n/d)(m/d)

似乎可以用呢。。求一个S[]表示符合条件的j的前缀和,再枚举符合条件的d,似乎可以做到O(m)。。

然后过了大样例,好爽啊。。对了下数据点,发现只有24分TAT

来容斥吧。。似乎k<=2000就是质因数不超过4,那么加个16的常数就可以做到O(n)

写了发调了会就过了,爽啊,有76~84分了。。

剩下的几分实在是不会了。。估计是杜教筛吧。。然而我只会求裸的莫比乌斯函数

这时过了两个半小时了。。去看T2。。

暴力好难写啊。。让我写一发暴力。。。

过了样例,写一发离散化。。

然后写一发c=0和1的特判。。

然后写一发选周围的点的离散化。。似乎有些问题,不管了。。

觉得能拿48~64分,查了好久应该没啥问题了。。

时间过得好快啊,只剩下不到一个小时了。。

检查下T3,试了下n比较大的数据,发现爆了,赶紧把数组开大。。

然后T2想挣扎着写发c=2的情况,发现太烦了。。

GG了。。一道没A。。估计230左右。。

出考场和黈力交流,黈力说三道题都是SB题。。只是他第一道5分懒得写,第二道8分懒得卡,第三道8分懒得拿罢了。。看来黈力有270+啊,太劲了!

真的考挂了,T2就是个裸割点,裸做就有64分。。

感觉三道暴力可以拿260+啊。。

听黈力说单HASH随便炸,好虚啊。。

下午去复评,又炸了。。T2特判<=1的情况直接continue掉了

挂了最少24分,只剩下24分了。。

还好T1和T3没炸,于是95+24+84=203。。估计在金牌线上下吧。。

7.25

打游戏

7.26

T1就一道傻逼题,按线段长度排序扫一遍就没了。。

确认没看错题后,10min秒了直接过大样例不管了。。这还能错?

T2一看有点难,不过前面几个点大概排序以后来一个n^4暴力就行了。。

先写了发,过了大样例。。先拿了35的暴力分。。

不过题目要高精度。。高精度小数怎么处理啊。。

发现出题人送了个高精度小数库,好良心啊。。

发现这个DP复杂度有点高,高精度的那些分看来拿不到啊。。

觉得肯定可以单调优化,就写了发,拍了下,没错。。

于是改成了单调优化,变成n^3p的复杂度,能拿60分了。。

没什么好办法了,去玩提答了,还有3个多小时啊。。

第1个点送的。。

第2个点送的。。

3、4两个点先拿暴力吧。。

第5个点写个程序跑一发,再手动改一下就行了。。

后面的不会,看第8个点可以随便骗个6分

于是提答只有10+10+10+6+6+0+0+6+0+0=48。。

查了下T1,发现1000000爆掉了,发现离散化后少开了一倍空间。。

回去弄了下T2,把n<=700的换了个n^3的DP,觉得能多拿4~10分。。

觉得拿不了更多的分了。。去弄提答,把第5个点搞出来了。。多弄了4分

然后T2想了想可以写一发贪心,先取一大堆,然后一个一个取,时间复杂度O(n)。。

拍了下,大概100组错一组。。

把给的高精度小数复制了两份,另外一份保留很多位。。

最后几组数据用贪心乱搞搞吧。。看看能骗多少。。

然后提答第6、7个点绞尽脑汁,每个点弄了3分。。

最后1小时啥也摞不出来了。。检查不出啥问题。。

提答明明就是智商题啊。。智商不够啊。。只有58分。。

和黈力交流了下,发现黈力又虐场了。。前两道都A了,提答玩了68分。。

查成绩,100+74+58=232,T2贪心多骗了4~10分。

这应该能上金牌线了吧。。

下午看成绩,D类第一,这总能签THU一本了吧。。

然后老师说THU名额不一定够。。不一定能签到。。于是就先去SJTU报了名

SJTU面试果然让我第一个去了。。面试完直接出来,说和THU先搞好再来决定签不签

然后就和THU撕逼了。。D类选手没人权啊。。还要招办去申请一本。。

最后也没申请下来。。于是只好去PKU看一看。。

PKU老师说也要问。。还要第二天才给答复。。

于是只好先和SJTU签了。。不爽啊。。

7.27

PKU根本没鸟我啊。。变成了SJTU狗了。。

不爽啊。。我作为一个从来没有拿过银牌和铜牌的选手,就因为省选挂了一点,连个一本线都签不到了。。

D类+文化课渣根本没希望上清北啊。。不进省队根本没希望啊。。

曰。。感觉我还年轻啊。。好想留级啊。。

Avatar_small
lijian3256 说:
2016年8月01日 13:18

留级吼啊!兹磁哦!

Avatar_small
lbn小粉丝 说:
2017年5月02日 22:32

据说您现在的实际年龄只相当于高二?注意我的发言时间。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter