2023/1/13考试总结

· · 个人记录

本次考试时间 3.5h,共 5 题。

试题中 T_{3,4,5} 是从前做过的,不出所望,都 A 了。但是 T_{1,2} 一个数组开小,一个空间超限。。。(教训:认真看题目个变量定义;对拍要大数据,用 mt19937_64;不要随便define int long long

T1——Secret Message 秘密信息

容易发现,我们可以用字典树进行维护字符串,然后注意数组的大小就可以了。

T2——子序列

依然是字典树,对于一个 s 和字典树 TT 中按位异或 s 的值大于等于 k 的元素个数可以沿着树边走条树链,然后如果 k 那一位是 1,则为了使异或值大于等于 k 我们这里就必须让异或值的这一位也为 1,即选与 s 的这一位相反的方向。但如果是 0,我们就选这一位异或值为 1 的所有元素和继续往 0 的方向维护。

T3——播放列表

这题是用单调队列维护从每首歌可以往后最多可以播放到哪一首歌,即第一个会让我们不开心的。每个元素在队头被弹出时记录位置,然后输出答案即可。

T4——特别行动队

可以推出转移式:

dp_i=dp_j+a(sum_i-sum_j)^2+b(sum_i-sum_j)+c

然后推出斜率优化的四个数:

\begin{cases} x=sum_j\\ y=dp_j+asum_j^2-bsum_j\\ b=dp_i-asum_i^2+bsum_i+c\\ k=2asum_i \end{cases}

然后就没有然后了。。。

T5——Product Sum

我们可以推出:

\begin{cases} C_0-a_i(i-j)+sum_{i-1}-sum_{j-1}&(0<j<i)\text{这是将i移至j前面}\\ C_0+a_i(j-i)-(sum_j-sum_i)&(i<j\le n)\text{这是将i移至j后面} \end{cases}

然后,我们可以发现这玩意好像可以斜率优化。

就可以继续分别找出四个量:

\begin{cases} x=j\\ y=C_o-ia_i+sum_{i-1}\\ k=-a_i\\ b=dp_i \end{cases} \begin{cases} x=j\\ y=C_0-ia_i+sum_i\\ k=-a_i\\ b=dp_i \end{cases}

从前往后再从后往前跑两次就可以了。

完整代码