题目互讲 个人题解

· · 个人记录

CF1383E Strange Operation

\mathbf{Question. 1}

容易猜到是根据答案序列的某种性质进行计数，那有什么性质？

::::info[\mathbf{ANSWER}] 考虑将答案视作一段一段的连续块，那我们发现：

但这里的合并操作（将两个连续块合并）使得这个看起来很复杂。考虑换一种刻画方式，我们设最终的序列 a 表示相邻两个 1 之间的 0 的个数。 :::warning[举个例子]{open} 对于一个串 \texttt{00101100010}，最终的序列 a = \{2, 1, 0, 3, 1\}。

对于一个串 \texttt{101101}，最终的序列 a = \{0, 1, 0 ,1, 0\}（两边的就算没有 0 也要记录） ::: 那么我们现在再来考虑两个操作：

我么先计算开始和结束的那两个 a_1, a_k，这个的贡献是 (a_1 + 1)(a_k + 1)。

假设初始为 a，因此，最终生成的 b 序列要满足，存在一个 a 的子序列 a'，使得 b_i \leq a'_i ::::

\mathbf{Question. 2}

我们需要加条件，使得我们可以通过 a 的子序列来不重不漏的算出 b 的方案数。

::::info[\mathbf{ANSWER}] 考虑一个贪心算法，假设我们当前要对于一个 b，找到对应的 a 子序列。

我们直接从左往右扫 a，如果当前 a_i \geq b_j，那就将 i 和 j 匹配，且 j 加一。

这样，我们可以保证每个 b 序列都是对应着一种情况。现在，我们对于每个 a 的子序列计数即可。 ::::

\mathbf{Question. 3}

是否存在多项式复杂度的计数方法？

::::info[\mathbf{ANSWER}] 考虑 DP，设 f_i 为匹配到 a_i 时，b 的方案数。考虑 f_j \to f_i 会发生什么。

设与 a_i 匹配的 b 值为 x。根据 \mathbf{Question. 2} 中的贪心方法，\max\limits_{t = j + 1}^{i - 1} a_t < x \leq a_i。

因此，f_i = \sum\limits_{j = 0}^{i - 1}f_{j} \times \max(0, a_i - \max\limits_{t = j + 1}^{i - 1} a_t)。复杂度为 \mathcal{O}(n^2)。

注意 j = i - 1 时，由于没有 \max 的限制，f_j \times (a_i + 1)。 ::::

\mathbf{Question. 4}

能否对这个 DP 进行优化？

::::info[\mathbf{ANSWER}] 观察这个 DP 式子，显然只有 a_i > \max_{t = j + 1}^{i - 1} a_t 时才有贡献。

考虑单调栈，我们在加入 a_i 到单调栈的时候，弹出的 a_j 都满足 a_j 小于 a_i 的条件。因此，对于单调栈内的每个元素，维护以该元素为最大值的 f_i 总和。

转移是普通的，时间复杂度 \mathcal{O}(n)。 ::::

CF1383F Special Edges

\mathbf{Question. 1}

我们能否不考虑特殊边的边权去跑最大流？

:::info[\mathbf{ANSWER}]

首先可以把最大流转化成最小割。

如果我们想不考虑特殊边的边权，那我们可以考虑直接枚举这些边在最小割中是否选择。

:::

\mathbf{Question. 2}

现在，我们只需要考虑如何对于网络流，固定某条边是否选 / 不选即可。但我们要让边权尽量小，否则网络流无法通过。

:::info[\mathbf{ANSWER}]

首先，一种很显然的方法是将必选的边视为 0，不选的是 +\infin，但是这样边权过大。

我们考虑将不选的边权视为 25，这样虽然这条边有可能在最小割里，但是这时这条边的代价是 25，还不如本来就选这条边，代价是 w_i \leq 25。时间复杂度为 \mathcal{O}(2^k \times flow(n, m) + q \times 2^k)，无法通过。

:::

\mathbf{Question. 3}

如何优化？

:::info[\mathbf{ANSWER}]

注意到边权很小，所以我们考虑使用 FF 算法（一种基于流量的网络流算法）。

我们考虑先对不选边的情况跑一遍网络流，求出剩下来的残余网络。然后，我们要找到一个枚举二进制数的顺序，使得每次改变的量尽量小。

考虑格雷码，相邻两个格雷码只会差一个二进制位。因此，就有 0 \to 1 和 1 \to 0 两种情况。

:::

CF1268D Invertation in Tournament

不会，回家补，先记几个结论。

:::warning[\mathbf{Lemma. 1}] 当 n \leq 7 时，反转的点至多一个。 :::

:::warning[\mathbf{Lemma. 2}] 当 n = 4 时，答案为 -1，当 n = 6 时，答案为 2 和 18。 :::