茉莉花新闻网

中華青年思想與行動的聚合地

如何评价 2022 ICPC 杭州站?

彭博的回答

占个坑,赛后可能会更新更多东西(如果出锅就连夜跑路了) 写一下热身赛的来源,A是去年浙工大校赛的某题,B是听说pta支持交互了热身赛出一个玩一玩,顺便给大家复习一下Useful Algorithm。C是去年香港省赛的DP,正解做法就是将所有有用的状态拿出来,复杂度是 \Theta(n^{\log_3 ⁡4}) ,当然可以发现转移是个卷积用任意模数FFT做到更大的范围。D是ZJOI2022的题目,听说有很多中学生来打星于是就放进来了,出题人认为还是比较不错的一道题目,大家感兴趣可以上网搜索一下题解。

祝大家比赛顺利!


比赛圆满结束了!除了A题题面忘记说可以输出任意解,题目基本没有出锅,暂时不用跑路了。感谢出题组所有同学的努力,主办方为举办比赛做出的努力,和所有验题队伍提出的宝贵意见!

按照题目难度从低到高来点评一下题目:

F: dgg的大米老师喜欢的题。签到字符串小模拟。背景大概是群友转发一些很变态的东西的时候都会说是大米老师爱看的,并且群友经常会催大米老师入坑原神。现在大米老师真的入坑原神了,望周知。

D: 我的小清新签到题。 结论很好猜,但是证明可能有亿点点麻烦的签到。对着样例手玩、直接解方程、打表都能看出 2:1:1:1\dots 的规律,try a try, AC is OK。

A: osc的数论题。原来的版本是不取模,而是让绝对值最小,没有输出方案。但是这样和第四个题的难度就有一个gap,于是修改成了带取模的版本。既可以直接用exgcd解两个方程来得到解,也可以观察到加一个等差数列等于加上 n 个中间的数来只需要解一个方程。同时因为 n 不大,也可以通过枚举对 m 取模减了几个 m 来避免exgcd,可能是一道略有细节的签到。

K: 我的小清新字符串题。当时缺一个铜牌题,一拍脑袋就想到了这个题,检查了一下不是很原就出出来了。思路整体来看比较自然,而且数据范围应该有很强的提示作用。其实可以在 \mathcal O(26) 的时间完成每组询问,但是因为会提升难度并且与原来的题目比较割裂,所以就没有修改,有兴趣的选手可以思考一下。样例揭示了Putata和Budada到底是什么,引人深思。

C: Cls的背包题,据说有着真实的背景,把装备穿穿脱脱攻击力就变高了。本来的版本是 n,k,p\leq 3\,000 的,但是考虑到整体难度就把数据范围调小来放过跟简单的做法了,这样难度可能就更偏向思维。可能有一些corner case,需要选手更加细心。

G: osc的图论题。又是一道结论相对好猜,但是证明可能有亿点点麻烦的题目,可能是本场的图论担当。需要注意的点可能有要使用正确的树哈希和注意到 \texttt{ababab} 的case。可以通过用 <img src="https://www.zhihu.com/equation?tex=%5Ctexttt%7Bstd%3A%3Amap%3Cvector%3Cint%3E%2C+int%3E%7D" alt="\texttt{std::map<vector, int>}" eeimg="1" referrerpolicy="no-referrer"> 来给树标号和把环当成字符串来判断循环、翻转同构来避免踩坑。

M: 我的大骗题。题面有一点点长的题目,希望大家没有都错题。读完题转化之后如果想到枚举一个点 x 来计算答案,那么应该很容易发现是一个区间加,维护所有数 \text{gcd}的问题,这个问题有一个比较经典的线段树做法,就是维护差分。如果再想到换根,那么就会发现操作实际上只有合并两个集合和一个集合一起加 w ​,只需要对每个集合维护两个数即可,代码会简单不少。可能是一道每一步都非常经典的题目,训练有素的选手应该能够很快解决。

E: 我的构造题。题目名致敬了去年CCPC桂林的“Assumption is all you need”,赞扬了oscar作为构造高手高超的解题能力,秒杀所有构造题,只需要一个oscar。难点可能在于要先想好用什么排序,再搞出相应的基本操作。验题的时候有些选手先想出了三步交换两个数之类的基本操作就使得做起来比较困难。另外一个需要注意的点就是对于 n=4 的情况要么上机打表,要么发现操作只有 3 种,于是可以手玩一下,比较考验选手对机时的利用。

I: osc的交互题。听说pta支持交互了,于是出了一道交互题。本来是 \sqrt n 步的签到题,但是有些无聊了,后面发现如果编号是个固定排列是有性质的,于是就变成了现在的样子。 10\,000 步应该是个迷惑性非常强的限制,但是解法的两步又非常自然,可能一位选手单独想到所有方面需要对这种题比较熟练,如果有两个选手交流可能做起来就轻松一些。这题可能是本场若干比较妙的题中的一个,希望大家比赛中玩的开心。

B: 我的数据结构题。题面有亿点点长的题目,但是其实想说明的东西非常简单。一道数据结构题,思路很多,关键就是枚举进位是第几位然后发现要把值域翻过来维护。代码难度和思维难度都适中。但是因为 \texttt{std::multiset}\texttt{std::priority_queue} 慢非常多,所以最后TL开了6s,是std的四倍左右,分块做法的两倍左右,应该不会有队伍被卡常。

J: Cls的几何题。在纸上画画写写应该不难发现是一棵树,难点在于实现。题目要求输出分数,避免了选手产生精度误差,非常良心,给Cls点赞!但是因为坐标范围开不了太大,导致凸包点数不能卡到很大,所以暴力再树上跳跑的有些快,于是时限只设置了std的两倍,可能存在一些不需要发现是一棵树的性质,直接用 \texttt{std::deque} 维护凸包需要非常细心实现或者不使用stl,直接手写平衡树才能通过。

H: Cls的厉害贪心题。难点可能在于建图、Hall定理的运用、发现是拟阵和具体维护怎么贪心,可谓是处处都是难点,但是每一步都比较妙。如果是熟悉Hall定理的运用和模拟费用流的选手可能会很懂,但是还是会有一定的思维量。实现上可能略有一些细节,但是如果思路清晰相信也不会对选手带来很大困扰。

L: Cls的厉害字符串DP题。验题时唯一没有选手通过的题目。需要选手思考发现结论之后DP,从而避免需要搜索的问题。DP的转移又依赖于贪心,需要快速求解两个字符串某两个后缀的的LCP,是一道知识点考察全面,综合难度比较高的题目,给出题人点赞。

上面这些都是我赛前写下的,实际比赛中貌似KC的难度翻过来了,虽然本来就比较接近,然后I过的比预料中多,E、G比预料中少。G考前紧急加强了一下数据可能是原因之一。E题在验题时一些队伍很用力地去做,最后也通过了,可能是比较需要用力的题目,实际难度比榜上看起来要低。最后结果B题还是有队伍因为使用了过多的 \texttt{multiset} 操作被卡常了,非常遗憾。I在验题时通过的队伍很少,正式赛中可能因为看起来就很有趣(实际上也真的很有趣!),于是大家都来做了。这次的I和绵阳的J都是近几年第一次出现在XCPC区域赛中的交互题,也都是很巧妙的题,希望大家可以多多探索这种题型在XCPC命题中的可能性。

热身赛的题目中有一个需要处理分数的交互,并且有两道题的题目名和正赛一样,不知道有没有细心的选手发现,又着切合实际的背景!

然后再碰瓷一下绵阳,赛前很看好&支持的triple_dogs,在前中期取得了巨大优势,然后在题号为B的数据结构题上写出了复杂度比std大的做法,一直到比赛最后也未能通过,痛失好局,简直就是我们队在CCPC绵阳表现的复刻,只不过绵阳是NJU出题,杭州反过来了,完全不敢想。祝他们在接下来的南京站发挥实力,取得好成绩!

最后的奖牌线是654,其实是比预计中低的,可能这场比赛有着corner case多,有一些题目存在一些正确但通过比正解困难的做法等等会让选手感到“坐牢”的体验,但是出题组仍然认为这套题是一套不错的题目。在我看来,命题者和选手之间的关系,不仅仅在于命题人需要给选手命制一套题目来达到区分、选拔选手的目的,很多时候命题人也希望借此机会和选手分享自己认为还不错的idea,或者认为某个做法很有用,但是好像知道的人不是很多,出一道educational problem来普及这个做法,这往往是出一套好题最难平衡的一点:如果将好的idea出到无关紧要的比赛中,未免有些浪费;而越新颖的题目难度就越难以估计,如果出到区域赛中的题目估计难度与实际难度偏差很大,对于参赛机会不多的选手来讲未免有些残酷。希望选手们都能体验到解出题目的乐趣与成就感,如果有下次命题的机会,我们也会尽全力做到更好。期待与大家再见!

同类信息

查看全部

茉莉花论坛作为一个开放社区,允许您发表任何符合社区规定的文章和评论。

茉莉花新闻网

        中国茉莉花革命网始创于2011年2月20日,受阿拉伯之春的感召,大家共同组织、发起了中国茉莉花革命。后由数名义工无偿坚持至今,并发展成为广受翻墙网民欢迎的新闻聚合网站并提供论坛服务。

新闻汇总

邮件订阅

输入您的邮件地址:

linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram