省流
A 秒了,B 挂了,1t寄了,差点掉到青名。
9.21
内含剧透,请vp后再来。
不是题解!!!!!!!
赛前
毫无压力的新开一把,飞线接上了电源,不会因为电脑没电下班了。
赛时
开局读 A,要求从 n 个数中选一些,使这些数中每个相同的数字出现次数相等,很容易想到统计每个数出现的次数,再把次数从大到小排序,然后用累加的个数去乘次数取最大值即可,2min 很快码出,这是这场比赛唯一顺利的一题。
读B,题目给我们一些集合,要求选取的集合中从 1 - m 中所有的数均出现,问是否有三种或以上的选法。一开始我认为先去按顺序取当前必须取的集合,然后看剩余的集合如果比两个多就可以取够,如果只剩一个就看有没有完全覆盖一个前面选取的集合,交了一发挂掉,然后加了一些特判交了一发又挂。此时时间已经过去半个小时,我感觉到我的做法应该是假了,但由于心态不太稳定必须要自己冷静下来,于是丢下 B 去强开 C 题。
C 题要求你给出一个排列,然后进行一种类似二分查找的做法,要求某些数一定能查出,另一些数则不能查出,是非常经典的考察二分查找理解的题目。在题目的限制下,显然如果能查到必须要在 x 前面的都比 x 小,在 x 后面都比 x 大, x 必须是 x。于是我直接固定了要求能查到的位置,然后把不能查到的位置丢进 set 里,按不能查到就丢比我大的后一个,强行乱搞丢进去,最后再 check 是否成立,交上去果然挂了,不过我做好了一些心理准备,没有要过的打算,只是方便我回头开 B 题。
此时回看 B 发现只要把所有的都选取,然后看能不能取出来两个就行了。码完之后交了又挂,然后写了一个 n == 2 的特判交上去又挂,此时我的心态彻底炸了,昨天刚刚不可接受地掉了五十多分,今天又卡在感觉完全没问题的题目上,于是开始乱改乱交,一直挂掉。
这个时候时间过去了一个小时,大脑有点缺氧,C 也是觉得观察到的性质很对不想再想,于是随便开了 D,D 看上去非常像一个 trie 树的乱搞,但此刻我已经没能力提起笔去模拟了,于是又在一个小时左右提前下班,接受了掉大分的现实。
赛后
第二天早上起来,第一步就看了分数,一下子掉了快二百分,把前面一个月慢慢涨的分在这两把之内全浪费了。于是上午划水。
到了下午课上,小睡了一会,精力恢复了一些,于是用手机开始看 B。点开错误数据发现没有特判 m == 1,在手机上强行加了个 if 就过了。
下课之后去图书馆补题,重温 C 题认为性质没错,然后注意到其实不能变的位置就是把可以变的位置分割成几块,每块中只要有不止一个数,他们之间随便交换一下就都查不到了,很轻松的码过。
此时看 D1 题,题目要求我们把 0 - n 的数两两配对,使他们的或的和最大,那么就是需要让他们的 1 尽量不重叠。乱搞一下,可以发现当 n 是 2 的次幂时可以很容易的把 1 最大化利用,让 n 去配对 n - 1,然后从两边往中间依次配对就行。接着就可以把小于 n 大于 2 的次幂的数去替换掉和前面只有最前面是 0 和 1 的数就可以把所有 1 都用上了。
整体思路没什么问题,然而实现时遇到了 n = 6 和 n = 9 的情况,发现 n = 6 时不能直接 n - 4 下去,因为 1 和 2 已经被后面的抢走了。花了大量时间去推能同时满足这两个例子的式子,过了很久忽然发现对 n = n - 2^x 和 n = n - 2 - (n - 2 ^ x) 取同时取 min 就行,在这道 1400 分的题上浪费了两个小时。
此时已经没什么精力去开 1900 的 D2 了,晚上开一把 vp 训练好了。
2025年9月22日