DAY -1
到达NOI赛场成都七中!
太美丽了成七
哎呦,这不考场吗
乐!
来成七报道,各种拍照领资料,折腾半天才到寝室。
宿舍没有电梯(拎箱子累死我了),差评
空调吹完还是好热,差评
床好小虽然只是正常寝室床大小,差评
晚上折腾半天终于睡着了
DAY 0
这一天我们开始了万众瞩目的开幕式,然而年轻的山西代表队还不知道自己将面临怎样的震撼(物理)
开幕式第一项表演是交响乐团的演奏,但是一个室内的交响乐团不知为何偏偏要放个音响,所以坐在音响前面的我感觉耳朵都快聋了,后面大镲老哥每一次都直击我的心灵(物理)
不过里面表演的变脸雀实好看,直到最后都不知道这是怎么做到的,而且我右面的高一大佬有幸成为了幸运观众
说到开幕式怎么能不说我们成七的优秀学生代表--陈睿呢
不愧是叔叔
DAY 1
早上起床,感觉非常的神清气爽,吃完饭就开考
一开始看T1,发现这是一道简单题,不管是主席树树套树线段树等等都能很轻而易举的解决,然而我考场上只想到树套树,所以发现95很轻松,于是连想带写共花1h写完了;之后开始看T2,大致就是往一棵树里面插点,其中m=0,m=1的情况很轻松就解决了,前两个点也是最暴力的暴力,但在想m=2的时候卡住了,我推出的式子在大样例中过了一个挂了一个,过了一会儿发现k=0时可能有特殊情况没有判断,改了一下就对了,然后考虑n=1,k=0的情况,先写了个dp,然后挂了,之后仔细想想,发现往树里面插点有如下几种情况:插点上,插边上,摘下来几棵子树然后连上该点在连回去,其中第三种情况根本不符合题目要求,所以每次加一个点有(2n-1)种情况,之后发现这种思路可以推广到仅k=0,于是就拿到了70(部分分为什么会给这么多);对于T3,考场上看了5分钟发现只要选的边没有横叉边即可,所以可以共O(n^k)求出每条边对于每个点是否可行,对于k<=6时,bitset+容斥即可解决,能拿36
最后期望得分95+70+36=201,实际得分95+70+36=201(没有挂分,赢!)
中午吃饭的时候有人在群里说输入未保证x1<=x2,我也没判,我还以为我t1要挂0,幸好没有,感谢出题人大恩大德
晚上被舍友fake,rp--
DAY1.5
早上起来感觉中暑头晕,所以在宿舍里躺了一天
晚上和舍友讨论算法,并着重讨论了我最差的字符串部分(划重点)
DAY2
即使前一天躺了一天,DAY2早上依旧有些难受,磕了点药就进了考场
打开题面第一题,在思索半天后想到可以把每一条向下的边拆成O(n) 条起点一致的边,在这之后我们发现每两点间的路径都可以变为沿一类边一直向上在沿二类边一直向下,首先我们考虑每一条二类边对答案的贡献,然后卡住了,原因是不知道如何处理这一条边的终点同时作为另一条边的起点的情况(枚举显然复杂度会炸),之后因为肚子疼到厕所蹲着去了,蹲的时候突然想到,如果提前把边按深度排序就不存在上述情况,然后在开考1.5h后写完了代码,但根本过不去样例,所以又花了半个小时重构了一下,然后就过了(考完发现好像没有人思路和我一样);之后看t2,首先把给分的O(nq)哈希写了,喜提36,之后看到性质A中的“随机”,突然想到一种邪门的写法,我可以仅比较两个子串的前40个字母(假定一定可以比出大小),然后把每一个长40的后缀塞进一个线段树里(线段树上每个点开个vector),之后把线段树上每个区间排序,询问时在每一个对应点上二分找出大于的数量即可,但考场上由于大小于以及边界条件没搞清的原因,花了将近2h才写完,跑大样例时发现当n=1e5时只多测两次就已经跑满,于是决定可以将树的大小开小一半(由于奇偶原因开了2棵线段树),但再测大样例发现错了就又改回去了(事后想可能是边界条件依然还有问题的锅);看了t3,打了个10分的暴力就跑了
预计得分:100+36~44+10=146~154,实际得分100+52+10=162
由于数据太水,我T2的邪门做法把性质B的对应分也冲过去了(那是不是我考场上卡了那个常就能冲72了)
赛后问了同学,发现t3的30也很好写
DAY2.5
上午听了“我与NOI”的演讲
队爷疯狂fake引起不适,差评
我的一个机器人朋友堂堂连载,好评
下午开始闭幕式+颁奖典礼
今年的金银线为什么会比去年高100啊!!!今年队线再创新高
闭幕式感觉没什么好看的
闭幕式完了还不让我出校园,我还想在成都玩一天,差评
总而言之,今年的题目其实出的还行,但部分分的设置简直是依托答辩
本人今年拿到了一块银牌,达到了自己预期的标准,最后也祝愿还能再来打NOI的同学能拿到理想的成绩,没打金的高二同学文化课加油,金牌的选手......算了不祝愿了