ALPC_Natural_Selection

刚刚结束的ICPC2023沈阳是自然选择号的最后一场 XCPC 区域赛,很高兴也很幸运能拿到校排名 rk4,圆了一个这半年才开始做的梦。在这里讲一下这支队伍的故事。

组队、训练

本来和@wjy666(aka maple)打完 EC Final 之后是想要退役的,因为一直处在基本不怎么训练只打比赛的状态,如果打不出更好的成绩也没什么意思了。之后在教练的建议下吸纳了大一零基础的大腿@geruome,想看看有没有可能冲击一下 WF。CCPC Final 是我们这支新自然选择号的首秀,当时没训裸打打了银。虽然成绩不亮眼,但是我们发现三个人的状态是舒服的,打好配合说不定真的有机会。

那就试试吧。

虽然这时候信心几乎为零。

后面一段时间在忙保研,于是8月初的 thu camp 成为了我们开始训练的第一站。打得很惨,场场被按在后排。坐在我们后面的银色子弹,几乎每场比赛都从头到尾压着我们打,给我打得有点自闭,不知道这个状态怎么能赢。现在看来,当时打得不好完全是因为三个人都好久没写代码,并且还没开始磨合。三个人的磨合,可能比个人的硬实力更为关键。

来只 maple

开始狂训是在9月。平均2天一场 vp,赛后再去补知识点。geruome 训练热情非常高,带着我们一起泡在俱乐部补题。这一个多月的时间打了差不多 20 场比赛,写题写多了手逐渐热了起来,我开始有了一点信心。期间去打了一场湖南省赛,也是拿到了第一次 ak。

秦皇岛、西安、桂林

秦皇岛赛前,信心差不多四成。

因为打了几场成绩还不错的 ucup,也很想在现场赛施展一下拳脚。不料,最终连金牌都没有拿到。maple 过了超高难度的 K,我最后 I 题写了一个多小时还是没有调出来。

西安的最后20min,是我们这辈子第一次看到出线的希望。当时我和 geruome 10min 内连续通过 I 和 A,过题数达到了8。此时压力全部来到了 maple 身上,这场能不能打到前五可能就看他能不能把 B 调出来。用他复盘的话来说,在我们8题的时候,他一瞬间被“过了就能出线”的压力给压垮了,完全不能静下心来调试。最终因为有一个变量名没改过来,还是没能通过。

但是这场比赛,让我们看到了希望,我们好像就要触碰到梦想的边缘了。即使在强队如云的情况下,只要我们发挥出正常水平也是可以一战的。面对后面强度预计不如西安的沈阳,我觉得我们有八成胜算。

然而之后的桂林,也是简单题卡住,H 没有人想到可以从父亲节点删元素。maple 深陷极具迷惑性的 L,本应该会做的 E 却因为没有早看而没能写完。

打了三场 XCPC,每场都暴露出来各种致命的问题,其实这些问题的根源还是比赛策略的问题。从秦皇岛放着 M 不做,C 不看,到西安没有把题目给到适合的人,再到桂林做不出 H 做了半场 L,还没有早看到会做的 E,关键的决策好像没有一步是对的。虽然复盘的时候,我们认为每一场的失误都是在赛中可以预判并即使修正的,但到了沈阳真的就能避免这样的问题吗?我不知道。

这时候我的信心又降回40%了。

这三站打完没什么心情合照了,放一张省赛的图

线下练手的机会已经没有了,下次就是沈阳的最后一舞,我需要静下心来沉淀一下。想要打出好的成绩,就必须把我们的特长发挥出来。我们三个的风格太不同了:maple 算数飞快,擅长贪心、dp 、构造等一切不需要科技的题,然而却不会写线段树;geruome 数据结构水平高超,擅长写恶心题以及计算几何,但好像不是非常懂 tricks,有的题会无从下手;我技能树比较全,对题目方向猜的比较准,思维比较灵活,但是上机脑子容易发懵,细节稍微一多就写不对。我们三个人单打能力应该都不大行,但合在一起恰好优势互补,哪种类型的题都有人做。

然而本应该分工明确的我们,在复盘的时候,总是有某段时间三个人都想不起来自己做了什么,好像没有任何进展,5h的比赛被我们打得像4h。其实,一道题目其实就那么几个关键点,思考方向正确的话不会花费太长时间的;如果思考方向错了,那就是在无用功,扔给队友或者一起讨论都要比一个人死磕要强。于是我们决定要调整比赛的节奏:每个人先看足够多的题,分给合适的人。如果一个人卡题了,那就大家一起看这个题并把它做出来,尽可能减少无意义的罚坐。

在最后两周的训练中,我们主要往年的区域赛题目为主,目标不再是做出难题,而是主要训练在可做题较多的情况下如何写的又快又稳,以及卡题时要怎么做。我让自己多读题,每道题扔出一些我的思考,然后分给对的人去做,我尽量不去陷入细节较多的题目。如果一道题我和队友讨论出来了,那就尽量扔给队友写,我再去开别的题。

出发前,我的信心处在叠加态中。想到我们没有人写过难一点的计算几何,我的数论水平还不够高超,Todo 里还有很多东西没有梳理……但没关系,我选择相信我们(洗脑)。

沈阳

两周没有参加比赛,热身赛坐在不大且摇摇晃晃的桌子前,居然有一点陌生的感觉。虽然两个略难的题目都没能通过,但没怎么影响到我。因为我知道,我们的训练量已经有了,默契程度已经够了,这两个月的训练成果,就看明天5h内的发挥了。挺残酷的,但这就是 ICPC,不是吗?

正赛总算开始了。拆开信封 2.5s 之后,geruome 就通过题目名发现签到题。之后 maple 也迅速过 E,此时排在 rk1。我读了 I,感觉是没什么技术含量的讨论题,应该是要过的(伏笔1),果断扔给 geruome。简单讨论后我发现 J 是简单题,贡献一发罚时后通过了(伏笔2)。这时候稳健跟榜,maple 看了 K 说一眼数据结构,直接丢给我,我看了看就写了,maple又迅速通过了 M。B 很快想到了一个 n^3 的思路,但是细节较多。于是先看了 H,猜了个做法扔给了 maple 去细想。在我上机写 B 的时候其实还没有完全想清楚,心里是没有一点底的,但我知道这道题必须过,所以只能先硬着头皮写,等着队友把我换下来想细节。当我发现我怎么也想不清楚细节的时候真的有点慌了——我写题的时候,信心会给我正反馈,当某道题我没有信心写出来的时候,我就写不出来,当我有信心能写出来的时候,我就能写出来。这时距离比赛结束还有1:40左右,手里还有三个没过的题目。我心里发毛,训练赛遇到这种情况,我基本就知道这题是出不来了。但是,今天是我最后的机会了。于是我出去上了个厕所,告诉自己说:没事,我今天就算没有别的任务,剩下的时间只要把这个 B 做出来就算没有遗憾了。强迫自己冷静下来以后,发现根据对称性能把很多细节都给扔掉。于是我思考清楚后,等着上机重构了一下代码,在 4:29 通过了。这期间,geruome 把 D 给过了,I 写了大部分。这时候,情况变得和西安一样,压力全部集中在了 geruome 身上。我们都知道,只要过了 I 就肯定能出线。看着 geruome 独自调试,我却帮不上忙,心里比我自己上机还要紧张。终于在比赛结束前40s,发现了可能是最后一个错误,但已经没有时间改完了。

比赛结束,全场掌声响起,我觉得没了。掏出手机想算一算到底有没有机会,但紧张到根本没法静下心来算罚时。看到出去打探的 maple 竖着四根手指回来的时候,我挤压了许久的情绪才终于释放了出来。

前进四:前进到 rk4

稍有遗憾的是,我们差 11min 罚时就能拿到杯子。如果我签到 J 没有 wa,我们三个就能一起上台共同举起季军奖杯。不过没有关系,rk4 也已经足够美好了。

后记

算了算时间,距离我敲下第一行 “Hello, world!”差不多刚好六年半,我也终于可以给磕磕绊绊的算法竞赛生涯画上一个圆满的句号。

如果说我们在这两个月学到了什么,一是经验,尤其是现场赛的经验。三场比赛,从 rk28 到 rk8 到 rk8,每一场比赛我们都能从中发现很多问题。比如秦皇岛 I 题,告诉我我不适合写细节多的题;秦皇岛 M,桂林 H,告诉我们卡住的题要大家一起看;西安 B,告诉我们题目要今早交给擅长的人。二是默契,三个人泡在一起训练的过程知根知底。谁擅长什么不擅长什么都互相了解的很透彻,于是在比赛中话说一半就能够心领神会,沟通非常高效,才能发挥我们各自的长处,真的达到了 1+1+1>3 的效果。

感谢两位给力的队友,和我一起实现了这个去年还不敢做的梦。还要感谢明日之风和金色传说出线 23WF 给我们的激励,以及感谢教练的 push。

祝 ALPC 越来越好。


说一下我 B 的做法吧,题解好像是 O ( n 4 ) O(n^4) O(n4) 的,我的做法可以做到 O ( n 2 ) O(n^2) O(n2),不知道大家是怎么做的。

定义 f ( n ) f(n) f(n) 表示长度为 n n n 的 turning permutation 中,1 在 2 左边的排列有多少。枚举第一个数填 i i i ,那么 1 , . . . , i − 1 1,...,i-1 1,...,i1 i + 1 , . . . , n i+1,...,n i+1,...,n 之间是独立的。于是有 f ( n ) = ∑ i = 1 n f ( i − 1 ) f ( n − i ) ( n − 1 i − 1 ) f(n)=\sum_{i=1}^nf(i-1)f(n-i){n-1\choose i-1} f(n)=i=1nf(i1)f(ni)(i1n1) 。因为要求字典序最小,所以从小到大枚举每个位置填什么,需要计算确定一个前缀的 turning permutation 有多少。同样,已经填了的数把没填的数分成若干个连续的段,每一段之间互不影响,任意一段要求长度为奇数,并且段中第一个数在第二个数的右边,因此方案数可以通过 f f f 数组和组合数计算出来。确定前缀后,计算一次方案数是 O ( n ) O(n) O(n) 的,但是按字典序枚举某个位置时只会将某个连续段划分为两段,因此也可以根据之前的答案 O ( 1 ) O(1) O(1) 计算,这样总复杂度可以做到 O ( n 2 ) O(n^2) O(n2)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/147999.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

“程序员们的奔溃瞬间”——分享你最令你哭笑不得的程序员经历

文章目录 每日一句正能量前言编程趣事后记 每日一句正能量 每件事最后都会是好事。如果不是好事,说明还没到最后。 前言 作为程序员,我们时常会遇到各种奇怪的错误和挑战,有时候我们会崩溃,但更多的时候,我们会从中学…

从0开始学习JavaScript--JavaScript基础

JavaScript作为一门前端编程语言,在现代web开发中扮演着不可替代的角色。它不仅为网页增添了动态和交互性,而且随着Node.js的崛起,也在服务器端开发中占据了重要地位。在本章节中,我们将探讨JavaScript的作用、重要性以及与其他前…

第二证券:大爆发!道指一夜大涨近500点

当地时间11月14日,美股三大股指显着上涨,其间,道指涨1.43%,标普500指数涨1.91%,纳斯达克指数涨2.37%。 标普500指数创4月份以来的最大单日涨幅。美债收益率大跌。美国10月CPI数据进步了美联储结束加息行为的希望&…

Find My平衡车|苹果Find My技术与平衡车结合,智能防丢,全球定位

随着人们环保意识的加强,电动车的数量与日俱增。与此同时,科学家经过潜心的研究,终于开发出新款两轮电动平衡车。两轮电动平衡车是一种新型的交通工具,它与电动自行车和摩托车车轮前后排列方式不同,而是采用两轮并排固…

舞台演出控制软件:QLab Pro

QLab Pro是一款功能强大的现场多媒体控制器软件,专为Mac用户设计。它提供了一个直观简洁的用户界面,使得用户能轻松管理和组织所有的媒体资源。QLab Pro支持导入各种音频和视频文件,并具备强大的音频、视频处理和灯光控制功能,可以…

Umi-OCR :一个完全离线的OCR图片转文字识别软件。

Umi-OCR :一个完全离线的OCR图片转文字识别软件。 开源免费,支持截屏或批量导入图片,并能识别多国语言,合并段落,处理竖排文字。 排除图片中的水印区域,提取干净的文本。 忽略特定区域的文字识别&#x…

什么是Vue.js中的单向数据流(one-way data flow)?为什么它重要?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 欢迎来到前端入门之旅!感兴趣的可以订阅本专栏哦!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…

colormap与colorbar应用

一,colormap 常见色度枚举值如下 应用如下 img cv2.applyColorMap(img, cv2.COLORMAP_JET) cv2.imshow(img,img) cv2.waitKey(0) cv2.destroyAllWindows() 常用的COLORMAP_JET效果如下,该模式常用于生成热力图 二,colorbar colorbar所有…

洗袜子的洗衣机哪款好?家用小洗衣机推荐

最近这两年在洗衣机中火出圈的内衣洗衣机,它不仅可以清洁我们较难清洗的衣物,自带除菌功能,可以让衣物上的细菌,还能在清洗的过程中呵护我们衣物的面料,虽然说它是内衣洗衣机,它的功能不止可以清洗内衣&…

VS2017新建.hpp文件

目录 1、新建h文件的方法:2、新建对用的cpp文件:3、在main.cpp中调用 1、新建h文件的方法: 2、新建对用的cpp文件: 3、在main.cpp中调用 参见大佬博客

[Linux]tcpdump抓包工具

windows中的抓包工具:wireshark linux中的抓包工具:tcpdump cpdump是Linux系统中自带抓包工具 [rootIKUN ~]# rpm -q tcpdump tcpdump-4.9.0-5.el7.x86_64 [rootIKUN ~]# tcpdump tcp -i ens33 -t -s 0 -c 100 and dst port ! 22 and src net 192.1…

SaleSmartly新增AI意图识别触发器!让客户享受更精准的自动化服务

AI意图识别技术是对话式AI中很重要的组成部分,通俗点来说就是一种可以识别用户在对话中表达的意图的技术。通过对大量数据的分析和学习,AI可以理解用户想要获得的信息,并根据这些信息来采取相应的行动或提供相应的响应。而在对话式AI中&#…

node将package.json中的包降为低版本或者升级为高版本

前言 比如现在你用某个包的当前版本,但是你安装的版本高了,那么你应该这么做 1.首先删除node项目中的node_modules目录,防止安装时的包不一致 如果没安装就忽略 例如将package.json中的view-design包降为^4.6.1,当前view-design的版本为^4.…

适合苹果电脑的格式转换器,你都知道几个

我之前都是用windows电脑的,现在突然换了苹果电脑,如何使用苹果电脑进行格式转换呢?有没有好用的格式转换器呢? 不要着急,本文将为你介绍几款常见的格式转换器,可让你轻松的在苹果电脑上进行格式的转换。 …

PyG(torch_geometric)的MessagePassing详解

1. 提出MessagePassing的目的 MessagePassing是图神经网络(Graph Neural Networks,GNNs)的一个基础组件,它被设计用来处理图形数据的问题。在图形数据中,数据点(节点)之间的关系(边…

【python】单词接龙

题目: 这是一个关于“单词接龙”的算法题目。在这个游戏中,我们需要从给定的一组单词中,以特定的开头字母构造出一条最长的“龙”。每个单词在这条“龙”中最多出现两次。当两个单词相连时,它们的重合部分被合并成一个。例如&…

【吐血总结】前端开发:一文带你精通Vue.js前端框架(七)

文章目录 前言1️⃣事件处理器2️⃣表单3️⃣总结 前言 上一篇中我们学习了vue.js 的条件语句、循环语句等知识点.,现在让我们接着Vue系列的学习。 Vue中事件处理器、表单等在开发中的作用不可或缺,本文将基于实例进行以上知识点的讲解。 1️⃣事件处理器…

Oracle如何快速删除表中重复的数据

方法一: 在Oracle中,你可以使用DELETE语句结合ROWID和子查询来删除重复的记录。以下是一个示例: DELETE FROM your_table WHERE ROWID NOT IN (SELECT MAX(ROWID)FROM your_tableGROUP BY column1, column2, ... -- 列出用于判断重复的列 )…

6大赛题,超148万奖池!2023无锡国际人工智能算法大赛等你来挑战!

各位人工智能卓越的推动者们,我们诚邀您参与【2023年无锡国际人工智能算法大赛】,探索未来AI创新的巅峰之战! 比赛为您提供与全球AI开发者技术切磋的机会,不仅是一场竞技,更是智慧的盛宴。 本次大赛总奖金超过148万&…

【FPGA】zynq 单端口RAM 双端口RAM 读写冲突 写写冲突

RAMRAM读写分类RAM原理及实现RAM三种读写模式不变模式写优先读优先 单端口 RAM伪双端口 RAM真双端口 RAM读写冲突和写写冲突读写冲突写写冲突总结: RAM RAM 的英文全称是 Random Access Memory,即随机存取存储器,简称随机存储器,…