NOIP2018游记

\(Day0\):
今天应该是要看考场的。
早上没有训练。在机房趴着睡到了九点多。然后起来划水到了十一点多。
中午吃完饭回来在机房和两个同学一起刷知乎,然后补番到一半又开始复习数论。接着看到了一道“好”题,就和同学一起口胡了一下。
然后上去试机,开始打之前看到的那道题,但是没打完试机就结束了。然后下楼以后继续开心debug,但是还是没有弄出来。回到宿舍以后继续开心debug,终于调出来了。真是一道丧题。
对,我说的就是NOI2004 郁闷的出纳员
(话说调到一半调不下去了,看了一集「黄金拼图」,然后回来就调出来了,愿吉老师赐予我力量(大雾))

\(Day1\):
T1大水题,T2有点小坑,以为是数论结果写了正解思路自己以为是暴力,T3给了很多部分分然后拿部分分的时候想到正解来不及打(也打不出来)。
感觉这场有点水,大家都考得很高,我估分好像也比较高,我觉得有点方。主场作战也是有优势的,上厕所调整思路真是超有用的。
大概就是这样。
今天并没有见到某个喜欢做很多事情的女孩子,希望明天也不要见到。(大雾)
话说打开空间才发现明天竟然是双十一。虽然在广告中有看到但是好像没有实感的样子。

\(Day2\):
令人欣慰的是,今年真的没有那位女孩子。而且本人在群里说了并没有参与出题,太爽了。
今天的题比昨天不知道丧到哪里去了。传说今年的题存在一个叫做时间-难度不等式的东西,居然是真的——
$$ D_{1}T_{1}<D_{1}T_{2}<D_{1}T_{3}<D_{2}T_{1}<D_{2}T_{2}<D_{2}T_{3} $$
试卷的解压密码是「笑书神侠」,仔细想想昨天的解压密码是「飞雪连天」。莫名间一阵伤感。
T1和我出过的某一道题非常神似,都是在求一些特定的\(DFS\)序。就连对\(DFS\)的描述也和我的描述非常相似。
所以在考场上我用了几分钟的时间概括出了简要题面,然后用了十分钟写掉了。
T2和T3简直丧心病狂。
T2我一开始以为是一道结da论biao题,然后就写了个暴力硬上。打了一张5*6的表格,然后找规律推了\(65\)分的公式出来;
很容易可以发现两个定理:
一:对于一个点,如果它的左下方是0,那么它就不可能是一。
二:对于一条左下-右上的斜线段,如果它的颜色一样,那么位于它右下方的所有斜线段颜色都必须一样。
那么我们就可以考虑\(DP\),具体来说,就是,记每一条斜线的\(0-1\)分界,然后从左上往右下转移。
T3先是写了链的部分,一开始思路错了,是把序列拆成三个部分然后分别处理并且合并,写了一个三十多行的转移。然后上了一下厕所回来发现自己简直是智障,其实就是,把「要求放的地方的花费设0,不要求放的地方花费设无穷大」。然后其实就变成求带权树上覆盖集。这种做法的复杂度是\(O(n*m)\)的。如果足够聪明你就会发现,其实在求出初始花费之后,每一次询问造成的影响只会影响从这一个点到根的一整条链。所以找到树的重心之后用这种方法更新,可能可以缩小常数。
总之T2、T3我到现在都不会写正解。
考试剩下五分钟的时候感觉还不错,可能今天可以拿\(233\)分。结果测一下大样例发现我T3的暴力写挂了。所以就不知道会炸成什么样了。
出来以后在考场门口合了个影,然后就开始愉快划水了。
(尽管明天需要期中考qwq)
题目解析:
解析什么的…不存在的23333
祝大家RP++

NOIP2018 D1T1铺设道路
NOIP2018 D1T2货币系统
NOIP2018 D1T3赛道修建
NOIP2018 D2T1旅行

NOIP2018 福建赛区 初赛游记

初赛前状态不是很好。先是忘记带身份证,然后发现自己笔只带了一只、很方。
直到考前都比较紧张,然后对着窗外调整了一下呼吸,念了两句诗,稍微恢复了一些状态。
拿到卷子以后感觉不错。前面几道常识题有些不是很会做。鬼知道第一届NOI是什么时候举办的(不过我现在知道了,是1984)红球、篮球那道题其实和以前在知乎上看到过的一个问题:【生男孩、生女孩,生了一个男孩以后就不再生,那么这个社会男女比例是否会因此不均衡】很像。
事实上是没有改变的——接在一起即可。
然后关于长度为一的线段上任取两点的期望长度,比较合理的做法是硬上一个积分套积分,最后可以发现是一个二次函数从而得到三分之一的答案。另外一种做法就是,可以发现最大值不会超过二分之一、最小值不会小于四分之一,而符合条件的答案仅有三分之一,于是得解。
卡特兰数那一题,A选项没注意到是n+1个节点的二叉树排布,所以做错了。
还有就是那个数二进制1的个数的,x&=x-1,玄学位运算,吉如一tql。
姚期智是唯一一个华人图灵奖得主,是我记错了,尴尬。
阅读程序写结果,所有输入写在一行简直是个坑人设定。反正我一开始也被它搞糊涂了。据说第四题很多人错了,不过我好想检查出来了。
考了一个康托展开和逆康托展开。如果按照程序模拟复杂度是O(n!k)的,相信是算不出来的(笑)

程序补充,第一题的双向链表做法简直绝妙,反正对称写就没错了。
第二题是一道复杂背包问题。不,本来未必是背包问题,但是当做背包问题来求解简直是绝妙做法。佩服出题人。但是第三个空感受了很久还是写错了。

出来的话感觉状态还行,发挥出了屡次模拟以来的最高水准。但是仍然不一定能过初赛。所以只能祈祷不要初赛退役。