日记

我们拥有最强大的码力和最靠谱的队友。

我的俩队友一道题都没做出来。。。

列车# Link to

我们把线段的两个端点们离散化。然后每个整的区间就被切成了许多小区间。对于一个区间，他的每个子区间都要加上 $c_i$。然后最后的答案就是所有子区间的最小值。

这个 子区间 卡了我一天。

黄金替罪羊# Link to

我们发现，每个 $\texttt{?}$ 的取值是会影响后面的，也就是说它有后效性。不能搞普通的 dp。

我们钦定在 过去的自己 开始行动的时候自己的位置在 $p$，枚举每个 $p$。设 $dp_{i,j,k}$ 表示 过去的自己 走了前 $i$ 步，自己走了 $n + i$ 步，过去的自己 位移为 $j$，自己的位移是 $k$ 的方案数。

考虑转移：

• $s_i \in \{\texttt{L},\texttt{?}\}$，可以从 $j + 1$ 转移而来。
• $s_i \in \{\texttt{R},\texttt{?}\}$，可以从 $j - 1$ 转移而来。
• $s_{i + n} \in \{\texttt{L},\texttt{?}\}$，可以从 $k + 1$ 转移而来。
• $s_{i + n} \in \{\texttt{R},\texttt{?}\}$，可以从 $k - 1$ 转移而来。
• 在 $p + k = j$ 时不转移，$dp_{i,j,k} = 0$，因为自己黑化了，不合法。

注意这个 $k$ 和 $j$ 是同时变化的。就比如如果同时满足条件 $1,3$，就可以从 $dp_{i - 1,j + 1,k + 1}$ 转移来。对于每个 $p$，答案就是 $\sum dp_{n,p,i}$（就是枚举自己最后的位置），最终的答案就是把每个 $p$ 的答案加起来。

我们发现 $n \le 50$，$|s|$ 就小于 $100$，坐标区间的长度就是 $200$，而对于我们的 $O(n^3)$ 状态和一个 $O(n)$ 的枚举 $p$，总共 $O(n^4)$ 的复杂度，肯定是跑不过的。我们需要优化。

我们发现，在第 $i$ 步是，还能做的位移至多为 $n - i$，而还要做的位移就是 $|p - j|$，如果有 $|p - j| > n - i$，就肯定不可行，直接 continue。

时间复杂度还是 $O(n^4)$，但是现在跑的过了。

Quartet Swapping# Link to

我们发现交换的时候不会改变位置的奇偶性。比如有个数在 $a_3$，再怎么换也换不到 $a_2$ 或者 $a_4$ 去，只能在 $i$ 为奇数的位置上动。于是我们盲猜一个结论：把奇数位置上的数和偶数位置上的数排序后输出。成功的吃到一发罚时。

我们又发现一个性质：交换的时候，逆序对的变化是 $\pm 2$。也就是说，逆序对数量的奇偶性也不会发生变化。于是我们把原序列的逆序对数量算出来，排序后的数量算出来。如果奇偶性相同就直接输出，反之把排序后数组的第 $n,n - 2$ 项交换一下，因为这样既能改变奇偶性又能使字典序次小。

后日谈 # Link to 后日谈

总结了一下，感觉这次 CCPC 还是收获颇丰。

拼命练就的本领绝不会辜负自己