2018年11月10日,NOIP2018普及组复赛。
这是我初中阶段最后一次复赛了。
和往常一样,我们在预定的早上7点,没有出发。
10分钟之后,人终于到齐了,于是出发了,一路无话。
到了南航,合照三张,在慧园食堂吃了午饭。
赛前有听说是吉老师命题,非常紧张,几乎什么都没吃。总是在担心开题看到第一句:“九条可怜是一个热爱出题的女孩子。”
中午,依旧在长空学院休息。在那里,拿到了参赛证、准考证和身份证。
我是JS-0300,机位号6A-098,建立文件夹的名字为6A-098JS-0300
一点半,我们从长空学院出发,到了考点楼前,已经排起了很长一条队。手机关机,放进包里,该拿的东西放到口袋里。
一点五十,在志愿者的带领下,进入了考场。
两点,试机开始,话说选手守则播报和监考员通知声音重叠什么操作。
打了一个快读模板,适应了键盘。
两点二十五,试题下发,开题。
没有看见“九条可怜”好评。
我发生了什么!我昨晚毒奶一口,int*int要记得强转long long,第二题。
我在车上放卧虎藏龙音乐,然后第二题,龙虎斗???
我毒奶有图论,第四题,树?
两分钟第一题,十分钟第二题。
开了第三题。
第三题这是什么鬼?哪个屑出的?
我还是先看第四题吧。
第四题好评啊。
看到题,一开始没有什么思路。
先想想看,往在车上背的树剖想想,好像可以利用dfs序重编号id对子树操作。
但是那又怎么判断是不是对称呢。
诶,画个图。
设当前结点为\(x\),左孩子为\(l_x\),右孩子为\(r_x\),父亲为\(fa_x\)。
当\(x\)为\(fa_x\)的左孩子的时候,对其按左右根的顺序遍历,反之,按右左根的顺序遍历,如果得到的东西是相同的,好像这棵子树就是一个合法的树诶。
考虑考虑。
诶,我会\(O(n^2)\)的了。
不过这个数据范围,好像要么是\(O(n \log{n})\),要么是\(O(n)\)的诶。
不太好是\(O(nlogn)\)的诶。
好像所有的过程一遍遍历就行了,这就是\(O(n)\)了QAQ。
狂码一通。
过样例1.
样例2输出1什么鬼。
回头看一眼,好吧,把\(add(v[x],z)\)打成\(add(x,z)\)了。
改过来,过样例2.
测极限数据-样例3。
诶,输出9什么玩意。
不管了,回头看看T3.
T3这什么屑,完全没思路啊。
看看数据范围。
诶!我会\(m=1\)(逃)!我会\(puts("0")\)!
于是思维渐渐游离了。
突然,灵光一现。
我T4好像没有考虑树的形态相同。
回头加了五句,过了样例3.
在连i3都不如的竞赛机上,跑了1.1秒。
最后,大概310吧。
半退役了,回归文化课。
明年6月,中考,考上淮中,我就会继续走在OI的世界中。
update after getting the score
mmp
第四题写挂一个小点被卡了,就少一句话。
100+100+10+62