省流
整体进步明显,女生赛再砍一金,我们走在正确的道路上。
在解决掉 \(vivid\_stareium\) 这个问题之后,\(ZWU\) 进入了 \(jianfeijian\) 和 \(yrjzs\) 的时代。
10.12
内含剧透,请vp后再来。
不是题解!!!!!!!
赛前
\(7\) 天之前的成都站东西还没写完,状态越拖越差,这一周只有三天按时起床了。但是这种时候真的要感谢提前安排的日程,不然我估计又进入完全摆烂期了。以及前一天知道了 \(yrjzs\) 的含义,于是今天叶神将以 叶最帅 的名义出现在这篇游记里。(其实并不会我还在和这个该死的输入法磨合)
赛时
上来看题目,我们正常读题,然后我随便感觉了个 D 就开始看,当然这个感觉错了。很快在 \(2min\) 时叶神说 K 有人过了,于是我去瞄一眼 K。
K 题是把石头剪刀布换成有 \(n\) 种选项,相邻的选项种大的击败小的,最小的击败最大的,玩了 \(m\) 场后总胜场多的人胜,问获胜的概率。我直接直觉爆发,认为获胜概率与轮数无关,那么获胜的概率就算 \(n\) 分之一。我和简说我猜了个结论,让他直接写,就这样 \(5min\) 通过了。
简自己在我们看 K 的时候读了 A 题发现是小模拟,于是他接着就去码 A,而我和叶则是继续看后面的。很快 F 和 L 都有强队通过,我选择先看 L。L 题是有 \(1 \leq m \leq 100\) 个评委,每个评委会对 \(2 \leq n \leq 6\) 个 评分在 \(0-8\) 的能力中的两个各给一个系数,然后这两项能力和系数相乘后再相加,如果大于 \(0\) 就获得 \(v\) 分。要求你构造一只小栗帽的能力表,让最后总评分最高。我很快发现由于能力和范围很小,所以只需要对所有能力值都跑一遍所有评委就行了,可能性是 \(8^6\)。我按照我们的新规定让叶神查五分钟,我去看下一题,然后叶神发现能力可以取 \(0\),所以实际上是 \(9^6\),但不影响这道题目。
简此时还没码完,我和叶去看 F,给定一个 \(1 \leq n \leq 1e6\), 然后你每个以第 \(i\) 个数为结尾的最长上升子序列的长度,要求你构造一个长度为 \(n\) 的排列满足要求,或输出不可能。我一开始看成是前 \(i\) 个数中的最长上升子序列,于是提出了把数按顺序放在同长度的第一个就行了,剩下的从大往小放,然后叶提醒我是以第 \(i\) 个数结尾。我反应过来后认为结论应该差不多,只是改成从长度大的往小的放,然后每个相同的之间倒序放就行,最后查一遍是不是都满足。叶觉得查一遍比较麻烦,自己想了一下说是到出现的最大长度之间不能有一个没出现的,我想了一会认为没毛病。这两题思路搞定之后大约在 \(30min\) 左右,然后我们商定等一下叶先写 F,同时我给简讲 L 待会让他去写。
这时候我们已经把榜覆盖了,所以只能去试着看一下一开始我猜的 D,但没什么进度。我们前期进度很快,但简码 A 花的时间比较长,有短暂的时间掉出了金牌区。
到了 \(41min\),简写完了 A 题,于是叶上机我给简讲 L。中途我和简说复杂度足够,但他自己算了一下发现不行,我一看发现还真不行,于是想了五分钟别的方法,突然发现我们算成了 \(6^9\),其实就是暴力,所以这道题就也没什么说的了。这个时候榜单还是没什么变化,我就和简说你去看 G 题是大模拟,还真对不起他我们队伍的配置情况导致了我写大模拟太亏思考时间叶神写大模拟太容易出问题,只能简去写。我同时没什么建树。
\(58min\) 叶神码完 F,简去码 L 题。此时榜单终于有了变化,有人过了 H 题。H 题其实题面写的麻烦,但本质很简单。我们花了一些时间把这个题转换成了人话,就是给定 \(n\) 个查询串,给定 \(m\) 个询问串,要求对每个询问串找到出现的每一个查询串和出现的位置。查询串总长度不超过 \(2e5\),询问串不超过 \(1e6\)。我一开始想着 \(KMP\) 或者哈希一类的东西,然后想着哈希可以,但叶不太明白字符串的东西没办法太帮到我,于是在简下机后我就去试着写一个哈希。结果发现复杂度爆炸,还是要 \(KMP\),我就又下机,简上机开始码大模拟,此后就一直是我要求上机他就下。然后我发现 \(KMP\) 要很多个查询串一块搞才行,不太明白,于是直接查怎么搞,发现是 \(AC\) 自动机。我上 \(OIwiki\) 上拷了一个,稍微改了一点点交了就过了。此时 \(139min\)。
接下来我和叶基本就没做什么,虽然后面的 D E J 都有人过,但我们都有点疲乏了。简码完大模拟之后挂了两发,他自己改了之后交又 T 掉了。发现是有一些实现麻烦了,我说用链表他说用队列就行,总之最后三发通过了,\(206min\)。
此时总罚时 \(585\),砍下金牌。
赛后
这场比赛其实打的对我来说比较满足,问题存在点主要是简的 A 有点拖沓,以及下半场队伍整体没有再去做难题的状态了。还有一个未来可能面对的问题,就是队伍在面对不能跟榜的情况时找简单题能力弱,往后开题欲望低,不过短时间这个问题将不会是主要的。
看了 D 题题解一眼是网络流,那么留着以后再说吧。
F 题题解给出了另一种构造方法,对于两个点,如果长度相等那么前一个一定大于后一个,这个长度加一的第一个一定大于这个长度的最后一个,然后把前面的点连一条边到后面的点,然后拓扑排序的结果就是要求的序列。
2025年10月12日