nocriz的博客

苔花如米小,也学牡丹开。

CTSC/APIO游记

第一次参加全国赛事啊,理论上还是要写游记的,包括之后基本上就AFO了,于是我还是写了游记(流水账)了。

[latex]

Day 0

到了珀丽酒店,发现只有一个1.5米的床,然而两个人住。跟预期有些差距啊。房间似乎是随机分的,室友是南师附中的。他来了之后,我们都表示想换房间,他立即出了门,最终带着一个江西的同学来了,于是很愉快地又带他换到了六楼。据他讲他已经换了4次了。这就是一般图匹配问题啊!

Day 1

原本八点半开始,CCF最终鸽到了九点,在考场外面等待半小时。进了考场,喝水看题,提供了纸质题面,好评。这大概是第一个提供纸质题面的比赛了。题目一共11页,T1大概有六页,一看是道期望,学的不是很好决定最后做。然后看了T2,T3。T2秒出n方做法之后想了一想,觉得两棵树都是链的可能也会,码了T2,T3的暴力,然后就开始想T2。T2想了挺长时间,其中一度误以为会了另外一些部分分,花了好长时间。

之后就开始想T1,最后才做。想了一阵子,40分的暴力很简单,后来会做70分了,然后开始写,还剩一小时的时候,有点着急,仍然想“继续前进!写出这道题”还剩45分钟的时候还是调不出来,终于稳不住了,开始写40分暴力,最后四十分暴力没写出来,只好交了错误的程序,仍然得了20分。

最终 20+50+15,T2n方dfs被卡常只过了35分,但是不知道为什么错误算法把第一棵树是链,第二颗树是树的情况过了(???)T3暴力写的太暴力了,只得了15分。

出来以后好多200+的,TQL!

Day1主要失误的地方在于开场看到T1有六页纸,题面很长,被吓到了,然后在动题目之前就没想T1,甚至可能都没真正搞懂题目。导致最后没时间稳不住了。如果一开始就写T1的话,剩下两条暴力也是能写的。

还是弱啊

Day 2 

T1是道主席树(常州的同学说整体二分可做,然而没学过),二十分钟就会了,然后看了T2,T3。由于有之前做题答题的经验,决定T3最后做。T1花了一个小时写完了,但是大样例过不去,答案总是差1-2。然后又对拍,调了一个小时……真是太不熟练了。

这时候时间已经过去一半了,看了T2没思路,就看了T3。T3读完了以后就没想,但是提供了一个答案评分工具,我就想,只要不断调用答案评分器,就可以跑爬山/模拟退火等玄学做法了,于是用Python尝试写。一开始我是这么写的: ./xxx xxx.in xxx.out > xxx.ans ,发现那个程序坚持向屏幕上输出……真不知道为啥,于是想起来之前用Cent OS的经历,我就使用了nohup指令,这个指令本来会令程序无视任何关闭信息,在系统后台运行,因此输出会自动输出到nohup.out中,然后直接从这个文件读取结果就行啦,这样就把问题解决了。然后模拟退火的公式忘记了,只好爬山乱搞,爬过了两个点,剩下的也都有一些分数。

爬山的过程中,我开始尝试写T2。本来有一个半小时可以供我写T2的20分暴力,然而我总是想看看我爬山爬的怎样了,同时对T2暴力的时间复杂度一点自信也没有,于是颓到只剩45分钟,然后就真正认真的写了。写到还剩十五分钟的时候终于有些对了,然而还是过不了样例。最后十五分钟我还需要检查其他程序,于是T2也就弃疗了。直到比赛结束,还在找T2暴力的问题,然而找不到…… T2就挂了

得分100 + 0 + 36,和期望不差。出场听说模拟退火第三题63分……背过模拟退火公式就好了。

Day 3 / APIO Day -1

去了故宫,买学生票20元。而后在北海公园和苏州中学的同学划了两条船,由于天气原因(风大)只有电动的,我们就一起赛艇,在北海公园爬山。晚上吃烤鸭,5个人点了两只烤鸭,各种菜,非常爽。全天走了很多路。

APIO Day 0

上午上课,下午听一部分课,后来就回宾馆做题,在CF上写了一些期望水题。

APIO Day 1

看了题,俄罗斯人开了C++14,不评论,很多特性都不会用……

NOI Linux 不支持C++14差评,不过理论上正常写本机能编译也不会遇到什么问题,我也没有遇到任何编译问题。

看了T1,不是很会啊,于是看了T2,T3。给的暴力部分分是真的少,就5-7分。

T2是一个关于圆计算几何题,看上去可以搞一搞。T3是道图论,两档部分分还是会做的。

先写了T3的树的情况的两档部分分,直接dfs就结束了。于是就写了,提交两次失败,拿了点分。然后写了个5分小数据暴力,本来真的很暴力,大概

    \[n^2 n!\]

的,然后还是过了n=10,感觉不错。

T3有一个8分的部分分,似乎也很简单,就是点的度<=2,然后一开始只想到了链的情况,没有考虑环的情况没写出来。考场上竟然以为一个点只能在一个环内的情况是基环树,差点就要开始硬写了。考完了才发现是仙人掌……想想都后怕,仙人掌真的一题都没做过,要是当成基环树写了估计就浪费很多时间,然后挂了啊。

还有不少时间,就开始搞T2,写了个分块,然后就WA了。写暴力也WA,暴力花了半个小时,然后对拍,最终分块过了57分。之后觉得自己得的分还不行啊,就继续看T1,T3。后来就想到T3的8分部分分可能是环了,但是写了还是WA。这么简单的东西还WA,我也不知道怎么做,就盯着程序和题面看,以为除了链和环还有其他的。然后突然想到错误,开始重写,重写一半以为没有错误,又改回来了,于是就再也没写对。浪费了挺多时间,最终这个部分分也没有得到。

然后想T1,觉得只要会iterator和set就能写12分暴力了,但是我不会用iterator。而5分的暴力才五分,我又觉得5分用处不大啊,又跑去看T2,想想卡过10^5就是三十分,不如试试。那时候还是WA的,我改了改,提交上去就只有19分了,原本过的都有T的。其实没改多少啊,感觉后来评测不够快了?不懂。

只剩半个小时的时候开始写五分暴力,然后提交一次WA了,改了改,又提交,然后就不评测了。可能提交的人太多了吧,但是感觉能过。

最终T1 fst 0分,T2 57分,T3 28分。

APIO Day 2

上午下午听课,晚上颁奖。拿了一个 Cu 一个 Ag 。这之后也不知道能不能再来了,毕竟明年去西安了,还不知道怎么报名怎么学。又听说预科二文化课非常困难,肯定不能停课了,也不知道能搞成什么样…… 于是基本上就AFO了。

END.


评论

《“CTSC/APIO游记”》 有 1 条评论

  1. IJNYamato 的头像
    IJNYamato

    始终跟随伟大领袖cyy同志的步伐
    cyy带领我们从胜利走向胜利

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注