首页 > 技术文章 > WC2021游记

Cry-For-theMoon 2021-02-05 19:19 原文

开幕雷击

花了十分钟浏览了以下三道题然后发现都不可做(((

然后用了二十分钟想推一下T1有没有啥性质,只推出来一个 \(v->u\) 的结果是 \(u->v\) 的结果倒过来再取反但是感觉没用(但怎么赛后铃音的题解开头就是这个呢(危))然后放弃

然后去看了T3,本来以为 \(n,m<=1000\) 可以暴力 \(O(nm)\) 之类的然后发现好像不太可做,两项是 \(O(m^2)\) 以后才会循环(数学太菜了看不出来 \(m\) 是质数的时候循环节会不会变小),然后 \(a,b\) 又不确定,所以感觉要 \(O(nm^2)\) 爬了

转过头T2,发现 \(m<=10\),然后开始切第一档 20 分简单模拟(不知道写挂了没有....),然后本来想一鼓作气写掉下面第二档15分难一点的模拟的,突然发现我不会处理括号了!完了后缀表达式我都不会了,再次死在sb错误上(不过赛后(((1)))>(((2))))估计卡死一堆人。这个时候大概已经过去一个小时了,转过头看 T1

T1因为有环没dfs爆搜的思路所以继续往下看了,看到有一个 \(m=n-1\) 的应该是树,然后口胡了一个如果是树的话只用走简单路径的结论(好像没问题)然后 \(O(n^2)\) 搞过去了,大概10:00左右调过了大样例3,16分到手(结果赛后:没说图联通啊,这个部分分就是开玩笑的hhhhhh我16分炸了)

然后基本就在浪费时间,一直在T1和T2之间徘徊因为T3感觉是数学估计我拿不到分,浪费了很多时间在T1的样例上找环猜结论,后来发现没辙了,大概十点半的时候T1写了个 iddfs,用前两个样例加上自己瞎造的 \(n=8\) 的数据然后大概上界是 \(n<=4\) 的时候 \(depth=15\) ,\(4<n<=6\) 的时候 \(depth=14\),\(6<n<=8\) 的时候 \(depth=11\),测了一下发现本地机子上差不多都是0.3s左右的样子,不知道32分能骗多少,我是期望能骗20分以上的(前4个点应该没啥问题)

回到T2意识到自己大概是模拟写不完了,也就意味着后面所有带括号的分都拿不到了(赛后听说T2人均70(雾)),然后还剩下第三档部分分 \(n=2\),没有括号只有问号的,写了个 \(O(n|E|)\) 的线性dp然后发现样例1和样例2(样例2我把每个数组的第三个数去掉了测了程序)都能过然后就不去管了。大概这个时候11点半了,然后发现T2一个点是 \(5pts\) 不是 \(4pts\),也就是期望分从 \(24\) 变成了 \(30\),得到了点安慰。

然后颓废了十来分钟开始尝试 T3,先浪费了一点时间尝试了 \(p\) 是质数的发现推不出来啥,然后又乱搞了一会发现没有出路开始老老实实想暴力,然后发现相邻两项之间最多只有 \(O(m^2)\) 个状态,每个状态又后继唯一,只需要把所有 \(O(0,i)\) 的状态和终点 \(T\) 连边,然后边数就也和 \(O(m^2)\) 同级了。本来以为要 Dij 之类的担心T,结果发现这个bfs就行了,建反图从T开始跑bfs,输出 \(dis(Hash(a,b))-1\) 就是答案了(我试了试好像没有什么问题),应该是能拿到这20分的

大概这个时候已经十二点一刻了,颓废了十来分钟,剩下一个小时全用来检查了

一点钟左右发现T2的dp好多地方没取模开始疯狂修改+检查,最后应该是没锅了(LightningUZ赛后跟我说她T2好像全部没取模还拿了int存/jk/jk(默哀)(但她另外两题的分肯定吊打我总分))

然后1:30就交了,完事。

好了赛后部分已经穿插到正文里吐槽了(摊手),这次和NOIP还有CSP-S来说挂分不算多,最多二十分的样子(摊手)(但是如果T1那个地方考试时意识到不是树我也不会做那里,所以也不能叫挂分qwq)因为我这场WC没啥分可挂的/kel

2.5日的得分大概是[0,32]+[0,30]+[0,20]=[0,82]

希望2.6能混个Cu,听说WC2020的Cu线是30分???

算了一切都尘埃注定了,等2.6闭幕式再补结果吧

2.6

Cu线70分!!(然后昨天我记得我最高分82,听到85还没有我心凉了,果然还是Fe人)

结果奇迹来了:Cry_For_theMoon ...中学 88pts

Cu!!!!!!

尘(光) 埃(宗)落(耀) 定(祖)

推荐阅读