CTSC2018&APIO2018游记

CTSC2018&APIO2018游记

Day 0

傍晚出发，从长沙通往帝都的软卧哟。
然而长沙某中学坐高铁比我们晚出发还早到

Day 1

为了正经地写游记我决定忍住不在博客里吐槽酒店。
午饭在八十中。学校很nice，机房也不错（主要是机子配置好）。
居然有个Day 0？打开一看，看见了什么眼熟的东西。
九省联考Day 1。话说那道coat我到现在都还没写。
愉快地敲着FFT和NTT，其他的题目也不想写。就这么一直混到了晚饭。
晚上看了看去年CTSC的题。感觉不太妙啊。
不管了明天加油吧。

Day 2

早上发现餐票丢了qaq
8:30开考？不急不急。
然而时间不是已经到了吗？？？

非常抱歉，我们鸽了。---松松松

415考室表示9:07才开考。
不方不方先看题。
T1 faceless 假面 (神tm不要脸)
第一眼：诶我怎么只会(O(2^Q))暴搞啊，只有(20)分啊qaqqqqq
第二眼：好像(u=v)我会写！直接模拟！有(30)分辣！
然后滚去看T2 wronganswer 暴力写挂
按题意模拟得分。。。这数据究竟可以过多少啊。。。
再看T3 green 青蕈(音迅)领主
暴枚排列暴力check，复杂度(O(T*n!*n^2))？
把每个状态hash一下然后直接查表就是(O(n!*n^2+T*log n!))。
然后(L_{i,j}=j)的特殊性质就是(ans=2^{n-1})。
(25)分？？？
三题加起来没上三位数，显然是不够的。
很明智地决定去刚(T1)。
11:00的时候发现了(m_ile100)这个条件。要是再晚一点看见我可能就要凉了。
那不是，直接设(f_{i,j})表示第(i)个人现在有(j)滴血的概率？
操作(0)直接(O(m_i))暴力转移。
操作(1)？
想了蛮久。单独考虑每个人被选中，然后对剩下的(k-1)个人处理出(g_i)表示有(i)个人存活的概率。那么这个人的答案就是(sum_{i=0}^{k-1}frac{g_i}{i+1})再乘上这个人活下来的概率。
这样子是(O(Cn^3))的，可以过(70)。
然后看(100\%)，显然是(O(Cn^2))的。机智地发现前面处理的那个(g_i)数组就是一个背包，而考虑每个人的时候都相当于给这个背包插入(k-1)个物品，同时每个人也被插入了(k-1)次。
先处理出(k)个人背包然后考虑吧其中一个人给删掉？
按照原先的(dp)式子倒退回去即可。
下考前40分钟写完的。拍了十万组，舒服。
然后T2就是一个(O(n^2log n))的树剖，T3(25)分。
下考前估分(100+35+25=160)。


讲题前一个人跑到机房去看成绩。
(100+40+25=165)。
T2的树剖居然过了。我因为没判两个点在同一个位置然后(WA)了一个点。
今天这场的区分度不高啊。非(15)人里面有大概(frac 14)的人切了T1，然后T2不管是写有理有据的部分分还是乱搞获得了超过(45)的成绩的也不在少数。
比起冬令营少(10)分失(Au)，我并觉得今天这少的(5)分会出多大的锅。倒是没写乱搞这一点上吃了很大的亏。
（不过话说回来，就算现在让我写一个T2的乱搞，我也不能保证可以获得比(45)分更高的成绩）
乱搞能力有待提升啊。
不过让我更不爽的是我居然忘记带U盘蒯走文件了。讲完题后我再回去的时候机房都已经锁门了qaqqqqq。


二试加油吧。明天不考试的话晚上就可以gtf了。

Day 3

上午看各位候选队大爷答辩。
讲的很精彩啊，然而完全跟不上qaqqqqq（尤其是讲命题报告连看题的时间都没有）。
Q&A环节，不得不说，真是尬的不行。

复杂度不及是什么意思，是说复杂度更低吗？
莫队算法为什么没有给出解释？相关的参考文献呢？

吃完午饭就溜回酒店了，当是校外参观吧。

day2 rp++！

Day 4

换到了一个布局很迷的机房，三排电脑围一个扇形的那种。
开始看题啦！
T1 混合果汁juice
一看数据范围(n,mle10^5)一定就是数据结构题啦。想了一下想到了一个二分+主席树两个(log)的做法。
先没急着去写。毕竟要先看提答啊。
T3 组合数问题placement
标准提答？
(op=1)的答案其实就是(sum_{i=1}^{n}t_{i,a_i}+sum_{i=1}^{m}r_{a_{u_i},a_{v_i}})。
直接退火就上去了。暴搜都没写。
第一个点过了之后看见第十个点也是(op=1)，直接退火就过了？？？
开始拿退火去跑第五个点，趁着这段时间回去写T1。
写了半个小时写到10:30，直接过大样例，然后一拍就(WA)？
debug了半个小时发现一个变量名写错了。。。
暴力写的是(O(nmlog^2n))的，拍(n,m=500)的数据跑的还很慢？？？
拍了四千多组就没管了。
接着回到提答，发现第五个点跑出来了而且还过了。开心。
尝试解决一些特殊情况，比如说第七个点就是个二分图匹配，第四个点是个(dp)等等的。
尝试写(op=2)的(checker)，然而写不出来啊qaqqqqq
在下考前四十分钟的时候我发现那个可执行文件simulator会生成一个res.txt并把答案输入进去。
emmmmmm...
于是机智如我——

int calc()
{
    freopen("placement2.out","w",stdout);
    for (int i=1;i<=n;++i) printf("%d ",a[i]);puts("");
    fclose(stdout);
    system("./simulator placement2.in placement2.out");
    freopen("res.txt","r",stdin);
    int res=gi();fclose(stdin);
    if (res<ans)
    {
        for (int i=1;i<=n;++i) b[i]=a[i];
        ans=res;
    }
    return res;
}

然后靠着这种操作+模拟退火在(op=2)的数据中拿到了不错的分数吧。
最终第三个点(3)分（其实这个点也可以(dp)的），八九两个点加起来(10)分（并没有看出有什么可利用的性质qaq），加起来(83)。
后果就是，我的T2直接弃掉了。直到下考前十五分钟我才开始看题，看第一档暴力。复杂度(11^8)？再见。
所以预估得分就是(100+0+83=183)。要是T1(fst)就完蛋了。


选手复测从开始时间一直咕到了结束时间，到最后都咕没了。讲题也咕没了。
口试。又是喜闻乐见的环节呢。


晚饭后闭幕式。仿佛什么事情都没有发生？
放心，一定会有的。
由于某种技术原因导致某些选手成绩丢失，CCF表示我给你们重测好了。具体题目？无可奉告。

然而几乎是所有人都知道重测是考原题稳了。
CCF：你们只交了两场的钱我让你们考三场就已经不错了，你们还想着要我再出一套题？
不过据说有人在赌女装？而且不论考不考原题都有人要女装？喜闻乐见XD

Day 5

出去玩了一趟。13:30准时开始水群，果真考的是原题。CCF紧急动用了85名参赛选手耗时5小时终于恢复了莫名丢失的部分选手代码，厉害厉害。
不过似乎是算标准分，考虑到day3的全场最佳达到了神仙的285，这样一来重测选手恐成最大输家？
然而并没有算标准分qaqqqqq，重测选手成为最大赢家。


下午领到了APOI的狗牌，这次来帝都的两个牌子都拿到了，开心。

Day 6

讲课。。。
上午是二分专题+可持久化动态完全图图的匹配算法。
下午是wyy的折纸专题+dota直播其实是AI专题啦
好休闲啊好休闲啊
明天apioRP++啊。

Day 7

进考场。为什么我进不去那个网站？看了三分钟发现是自己网址输错了。。。
T1 不会做。只会(O(nq))。
T2 不会做。只会(O(n^2))。
T3 不会做。我连暴力分都不会打。
T1想到一个(log^3n)的做法。写了一个小时，交上去又(WA)又(T)。
我完全调不出来啊qaqqqqq
写暴力。只有(5)分。
T2(O(n^2))暴力(7)分。
T3倒是可以搞一搞部分分。有(23)分是一片森林的情况，直接一个树(dp)就过了。写了一个(n^3)枚举点然后(Dinic)判断是否合法的暴力居然过了(nle50)，所以就有(23+16=39)分了。然后度数不超过2的存在链和环两种情况，分别算一下就好了。所以T3总计是(47)分。
T1那个店一直开着的点有一个(log^2n)的想法，写完交上去(T)了。
？？？
又写了一个(O(nklog n))的东西，然后第二个subtask(TLE)。
？？？黑人问号脸.jpg

所以就是(5+7+47=59Fe)滚粗。


下午得知自己CTSC Day2T1没有(fst)，所以(165+183=348)，(rank52)，貌似能踩个线(A)个(u)啊。
但是一想到自己APIO打铁了就感到很不爽啊qaqqqqq

Day 8

并不记得自己上午听了啥。。。
下午要讲有限状态自动机跟(SAM)，我决定咕。
晚上闭幕式啦。完结撒花！
(CTSC)踩线(Au)，(APIO)卡线(Cu)。
也许这就是RP守恒吧。

尾声

此次帝都之行就这样结束了，有收获也有遗憾吧。
这应该是我最后一次以高一选手的身份参加(OI)比赛了吧。
回去又要拥抱学科了，可能要暂时地(AFO)了。
加油吧！