十月太摆了没有随便做做环节。

测试题目选集

20241106 - D. 盼君勿忘

题解等会写 qwq。

Miscellaneous

[AGC022D] Shopping

神秘题目，比较酷。

首先发现对于 \(t_i\ge2L\) 的 \(t_i\) 可以直接将 \(t_i\lfloor\frac{t_i}{2L}\rfloor\) 加入答案并将 \(t_i\) 对 \(2L\) 取模。然后只考虑 \(t_i \ne 0\) 的 \(i\)。

考虑如何优化这个策略。首先简化操作，如果从一个点出来之后往某个方向走到最边上之后折返回来经过这个点，那么选择在后面上车。因此得到了好像更简单的操作序列。之后在操作序列中将花 \(2L\) 时间的点去掉之后，会发现每次从一个点出来一定会改变方向，这个序列（如果存在的话）一定是第一次会往左走时进，往右走时出，最后一次和第一次的方向一定相反，这个序列长度为偶数，贡献为长度除以 \(2\) 乘以 \(2L\)，因为实际上是第 \(2i-1\) 个和第 \(2i\) 个配对优化一个 \(2L\)。这启发出了更进一步，将（可以左走变右走的点）和（可以右走变左走的点）进行尽量多的配对，因为每个配对可以优化一个 \(2L\)。似乎是一个很难的问题。

这时构建一种思路，对于每个 \(i\)，直接花 \(2L\) 的时间走，这样时间就是 \(2L\cdot (n + 1)\) 的。之后对于剩余的每个非 \(0\) 的位置，记 \(l_i= [2x_i\ge t_i]\) 表示车下了人之后往左走再回来是否可以直接接上，\(r_i\) 同理。\(l_i=1\) 说明可以右走变左走，\(r_i\) 同理。实际上我们就是找 \(i<j,l_i=r_j=1\)，最大的不交 \((i,j)\) 对数，因为通过一些思考得到对于 \(\{(i,j)\}\) 一定存在 \(|\{(i,j)\}|=|\{(i',j')\}|\) 的 \(\{(i',j')\}\) 可以拼出一个顺次的操作序列。

考虑观察性质：

• \(l_i=r_i=0\) 时，无法优化。

• \(l_i=1,r_i=0\) 时，\(2x_i\ge t_i > 2L - 2x_i\)，得到 \(x_i\ge L/2\)。

• \(l_i=0,r_i=1\) 时，同理可得 \(x_i\le L/2\)。

• \(l_i=r_i=1\)，可以随便匹配。

于是发现 \(l_i+r_i=1\) 的匹配一定是和 \(l_j=r_j=1\) 的合并，而 \(l_i=r_i=1\) 的也可以自己合并，于是分开贪心匹配就可以了。

有个小细节是，\(n\) 一定存在一种最优操作序列使得它不会被匹配，此时 \(r_i=1\) 还可以额外少一次 \(2L\)。

Submission #59511721 - AtCoder Grand Contest 022