NOIP2018 福建赛区 初赛游记

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

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

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