CSP-S2 2020 参赛总结

2020-11-08 11:39:02


I. 前言

时间过得好快啊,感觉国赛还在不久之前。

10.12 ~ 11.4,连续打了 24 天比赛。总体状态还行。主要是把基础题做得更熟练一点,然后在效率和准确率之间寻找一下平衡。由于大多数比赛难度比较友好,并不是很吃力;于是见缝插针地做了一部分作业题,不过也感觉很多题水分比较大。

II. 时间轴

由于珠中要举办校运会,我校的考场撤了。然后被分到了铁一。

感觉机位质量马马虎虎,我的空格键必须要在正中央按下去才会有反应。

  • T1:要求把儒略历的每一天映射到公历上,有一堆映射规则。 $T\le 10^5$ 且保证答案年份不超过 $10^9$。

  • T2: $n$ 个动物,每个动物有 $k$ 种属性的若干种。如果存在属于 $i$ 属性的动物,就要买 $i$ 属性所需的所有种类饲料(共 $m$ 个如此的要求)。求还能加上多少种动物,使得饲料种类不增加。 $0\le n,m \le 10^6, 0\le k \le 64$。

  • T3:有 $n$ 个变量, $m$ 种函数,求调用某种函数之后 $n$ 个变量的值,每种函数功能是以下之一:

    • 给某个位置加上 $v$;
    • 给全部变量乘上 $v$;
    • 依次调用 $t_i$ 个函数,保证没有死循环。

    $n,m\le 10^5, \sum t_i\le 10^6$。

  • T4: $n$ 条蛇,蛇的强弱顺序按照二元组 $(c_i,i)$ 来比较。每一次最强的蛇 $u$:

    • 可以选择吃掉最弱的蛇 $v$, $c_u\leftarrow c_u-c_v$, $v$ 被删除;
    • 可以选择结束整个过程。

    求最优策略下最终会剩下几条蛇。 $T\le 10,n\le 10^6$。

T1 真是一道极其无聊的题;并且这种题居然还放在第一题的位置,似乎有种害人之心。由于保证答案不超过 $10^9$,可以直接二分年份,确定后枚举月份,确定后枚举日期。时间复杂度 $O(T(\log Y + M + D))$。实现细节的话,可以把公元前 $k$ 年看成公元 $-k+1$ 年,二分和求闰年的时候注意负数的取整是向 $0$ 取整(可以加一个除数的倍数转成正的做)。

然而,不知道为什么,我当时潜意识中儒略历第 $0$ 天是公元前 $400$ 年还是 $1000$ 年左右,求闰年负转正的时候仅仅加了 $1200$,导致一些比较大的询问答案恰好差了一天,非常让人无语。后来先去写了 T2 冷静一下,再回来查了一下,才算搞完了。后来发现本地要 1000 ms 上下才跑出来,然后又优化掉了几个除法,才搞到 800 ms,之后没管了。

T2 直接求出所有需要的饲料种类,枚举一下每个 bit,看这个 bit 是否能够为 $1$ 就行了。设有 $t$ 个 bit 为 $1$,则答案为 $2^t-n$。注意 $t=64$ 的时候不能写 1ULL << t,要特判一下;进一步地, $t=64, n=0$ 的时候 unsigned long long 也存不下,还要特判一下。虽然我觉得测试数据不会存在后者这样极端的 case,但是从这道题以及去年 D1T1 能够感觉出来,出题人有时刻意地制造细节,制造麻烦,让选手必须连简单题都不能放松警惕。

由于搞完 T2 后又去给 T1 查错,耽误了时间,影响了心情,过了好几分钟才缓过神来。这时候才把 T3 想出点眉目。对于每个加法操作,它对该位置的贡献是 $v\times \prod u_i$,后者表示在该操作之后的乘法操作的乘积。首先可以把 DAG 建出来。按照拓扑序倒序预处理一下调用每个函数之后连锁反应得到的乘法操作的乘积,记为 $f_i$。则每个加法操作就是一条 DAG 的调用路径,它后面的乘法操作的乘积就是路径上每个中间节点(三操作)后继操作的 $f_i$ 的乘积。这个可以按拓扑序正序来进行 DP,记为 $g_i$。到达底层的加法操作后,直接贡献一下该位置就好了。 $O(n+m+\sum t_i)$,此处初始值当作加法操作,调用序列看作一个三操作。

这时候还有 2 h 少一点,所以更能沉下心来好好思考 T4 了。

T4 的数据范围意图应该是线性维护每组数据的答案。一开始,又是潜意识的错误,莫名认为最强的蛇可以一次性选择吃若干条最弱的。耽误了十几二十分钟。然后才意识到,如果不考虑中止的问题,操作序列是固定的,似乎可以直接根据性质双队列维护一下。每次可以先假设操作成立,然后进行下去,最后发现做某个选择会导致后面自己被吃(矛盾),就退回来。初步的想法有了,但是不知道中间有没有地方想得不够仔细或准确,所以先写了一个暴力(std::sort / 插入排序维护序列)。就这么写着写着,可能差不多六点了。发现一下过了所有样例。然后就立刻魔改成了双队列。不过时间还是不太够,可能还差个几分钟才能调出那个双队列,所以只交了一个 $O(Tn^2)$ 的暴力。事实上,考场上写的两个版本都有一定的瑕疵,不过大方向应该是对的,实际测试下来,运行效率和正确率都非常可观。

大概就这么结束了。最后几分钟冲得口吐白沫。

前三题估计都没啥问题了,第四题要看数据的强度了,就估个 $[320, 365]$ 吧。马马虎虎。

upd: 实际得分 $345$。


upd on 11.9:

在和大家讨论之后和研读了 EI 的题解 之后,对 T4 有了更深层次的思考,在这里补充一下。

首先我们确实希望能够把整个过程持续地模拟下去。如果后面过程中一条在前面存在选择权的蛇被吃了,那它就会不进行操作。得到所有这样的逻辑关系后,倒着推一遍,就是模拟了每条蛇作出决定的过程。而难点就在怎样在线性时间内进行模拟。

一种想法是双队列。但是,设某次取出的最小值和最大值分别为 $d$ 和 $u$,若 $u-d<d$,那么情况就会发生一定的转折。这个转折点之后,新产生的值要么是严格最优先的;要么是和最优先的同值的(值为在该转折点出现时的最小权值 $v$),而不一定是最优先的。在 $v$ 同值处暴力插入排序等等做法,不排除势能分析正确等可能性,是比较难并且应该是尚未卡掉的。

但是我们可以有其他解决办法。

先考虑转折点后最大值严格大于 $v$ 的阶段。我们在 $v$ 值处建立一个类似线性求 prufer 序的数据结构(不妨称为“线性堆”)维护该值的所有下标,支持插入和弹出最小值。如果每次操作新产生的是严格最优先的,下一轮直接把它选成最小值;否则插入线性堆,下一次弹出一个下标最小值。不难发现,除了最开始的若干次 push(可以理解为初始化插入若干),每一次额外 push 操作之后都有一个 pop。因此我们可以维护一个只会向右移动的指针,使得至多有一个存在元素在指针左边(特判掉)。该数据结构在此情况下的正确性和时间复杂度都比较显然。

然后是最大值不超过 $v$ 的情况。根据上述过程,此时要么权值全部都是 $v$;要么只有一个 $<v$ 的权值。都可以轻松解决掉。

时间复杂度 $O(Tn)$。

总体上讲,感觉这种做法的思维难度还是比较大的,需要对整个模型有较好的直观感受,以及较好的分解问题、推导、运用“工具”的能力。不过是否有其他好方法,笔者尚不清楚。如果有各种奇思妙想,欢迎与笔者(以及大家)交流。


upd on 11.9:

我的四题 AC 代码,希望能帮助到有需要的同学。

III. 后记:总结与展望

首先,感觉今年的题质量比较一般。能出 T1 这样的题,看起来是没题了凑数的?

其次,综合这两年的情况,感觉出题人喜欢在一些不太难的问题上顺便挖一点小坑,比如两年都碰到的 1ULL << 64 的问题。个人认为没太大意思,但是要这么搞我也没话说,只能说大家都要留个心眼,不能在简单问题上放松警惕。

然后是对自己的评价吧。

  • 简要概括出几个需要长期留心的事项,其实就是效率、准确率(看题、思路、实现)还有能耗。提高各方面效率;降低在基础题乃至难题上花费的精力;不(因为求快而)看错题、想假、写假。需要继续在效率和准确率之间寻找平衡。同时,发现问题不要一味地去堵截,经过足够的训练,问题往往都能够自然而然地解决了。

  • 这次比赛进一步给我提示,正式比赛的心态还是很可能和平时模拟赛的心态不同的。正式比赛时,送分题没有调出来、时间紧张等等,对心态的影响可能更大,更容易让人乱了手脚,丢了大局。此次只是 T1 的弱智错误让我有点烦躁不安并且没有造成太大影响;不过今后还是要有意识地提示自己,调控好心态;心态好了,效率、准确率又能更高。

  • 这次写 T4 没有足够重视时间的风险,下次要更有意识地评估一下时间,更加抓紧;不过抓紧不等于慌神,依然要保持心态平和。

  • 这一次的 T1,如果实现得不好可能会比较恶心;并且难度并不明显比 T2 甚至 T3 低。下次可以考虑把恶心题排在稍后的位置处理,以免一不小心一开始就自闭了,严重影响做后面题的状态。

  • 此次提交格式的检查比较仓促,不过还可以接受。此外由于一题都没来得及拍,需要更加谨慎一点;要更加意识到大样例的局限性(例如,不是极限规模的,或者非常水)。

继续努力吧。再写下去就是废话了。


dqa2020

2020.11.8