专栏文章

题目互讲 个人题解

DDE_aemmprty
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mini0zhd
此快照首次捕获于
2025/12/02 02:44
3 个月前
此快照最后确认于
2025/12/02 02:44
3 个月前
查看原文

CF1383E Strange Operation

Question.1\mathbf{Question. 1}

容易猜到是根据答案序列的某种性质进行计数，那有什么性质？
ANSWER\mathbf{ANSWER}
考虑将答案视作一段一段的连续块，那我们发现：
  • 操作 00/10/0100 / 10 / 01 就相当于将一个 00 的连续块长度减一。如果这个连续块长度为 00，就将两边的连续块合并。
  • 操作 1111 相当于将一个 11 的连续块长度减一（前提是操作前长度大于 11）
但这里的合并操作（将两个连续块合并）使得这个看起来很复杂。考虑换一种刻画方式，我们设最终的序列 aa 表示相邻两个 11 之间的 00 的个数。
举个例子
对于一个串 00101100010\texttt{00101100010}，最终的序列 a={2,1,0,3,1}a = \{2, 1, 0, 3, 1\}。
对于一个串 101101\texttt{101101}，最终的序列 a={0,1,0,1,0}a = \{0, 1, 0 ,1, 0\}（两边的就算没有 00 也要记录）
那么我们现在再来考虑两个操作：
  • 操作 00/10/0100 / 10 / 01 就相当于将一个 ai>0a_i > 0 的 aia_i 减一。
  • 操作 1111 相当于将一个不在首尾的 ai=0a_i = 0 删掉，把两个相邻的 11 变成一个 11。
我么先计算开始和结束的那两个 a1,aka_1, a_k，这个的贡献是 (a1+1)(ak+1)(a_1 + 1)(a_k + 1)。
假设初始为 aa，因此，最终生成的 bb 序列要满足，存在一个 aa 的子序列 a′a'，使得 bi≤ai′b_i \leq a'_i

Question.2\mathbf{Question. 2}

我们需要加条件，使得我们可以通过 aa 的子序列来不重不漏的算出 bb 的方案数。
ANSWER\mathbf{ANSWER}
考虑一个贪心算法，假设我们当前要对于一个 bb，找到对应的 aa 子序列。
我们直接从左往右扫 aa，如果当前 ai≥bja_i \geq b_j，那就将 ii 和 jj 匹配，且 jj 加一。
这样，我们可以保证每个 bb 序列都是对应着一种情况。现在，我们对于每个 aa 的子序列计数即可。

Question.3\mathbf{Question. 3}

是否存在多项式复杂度的计数方法？
ANSWER\mathbf{ANSWER}
考虑 DP，设 fif_i 为匹配到 aia_i 时，bb 的方案数。考虑 fj→fif_j \to f_i 会发生什么。
设与 aia_i 匹配的 bb 值为 xx。根据 Question.2\mathbf{Question. 2} 中的贪心方法，max⁡t=j+1i−1at<x≤ai\max\limits_{t = j + 1}^{i - 1} a_t < x \leq a_i。
因此，fi=∑j=0i−1fj×max⁡(0,ai−max⁡t=j+1i−1at)f_i = \sum\limits_{j = 0}^{i - 1}f_{j} \times \max(0, a_i - \max\limits_{t = j + 1}^{i - 1} a_t)。复杂度为 O(n2)\mathcal{O}(n^2)。
注意 j=i−1j = i - 1 时，由于没有 max⁡\max 的限制，fj×(ai+1)f_j \times (a_i + 1)。

Question.4\mathbf{Question. 4}

能否对这个 DP 进行优化？
ANSWER\mathbf{ANSWER}
观察这个 DP 式子，显然只有 ai>max⁡t=j+1i−1ata_i > \max_{t = j + 1}^{i - 1} a_t 时才有贡献。
考虑单调栈，我们在加入 aia_i 到单调栈的时候，弹出的 aja_j 都满足 aja_j 小于 aia_i 的条件。因此，对于单调栈内的每个元素，维护以该元素为最大值的 fif_i 总和。
转移是普通的，时间复杂度 O(n)\mathcal{O}(n)。

CF1383F Special Edges

Question.1\mathbf{Question. 1}

我们能否不考虑特殊边的边权去跑最大流？
ANSWER\mathbf{ANSWER}
首先可以把最大流转化成最小割。
如果我们想不考虑特殊边的边权，那我们可以考虑直接枚举这些边在最小割中是否选择。

Question.2\mathbf{Question. 2}

现在，我们只需要考虑如何对于网络流，固定某条边是否选 / 不选即可。但我们要让边权尽量小，否则网络流无法通过。
ANSWER\mathbf{ANSWER}
首先，一种很显然的方法是将必选的边视为 00，不选的是 +∞+\infin，但是这样边权过大。
我们考虑将不选的边权视为 2525，这样虽然这条边有可能在最小割里，但是这时这条边的代价是 2525，还不如本来就选这条边，代价是 wi≤25w_i \leq 25。时间复杂度为 O(2k×flow(n,m)+q×2k)\mathcal{O}(2^k \times flow(n, m) + q \times 2^k)，无法通过。

Question.3\mathbf{Question. 3}

如何优化？
ANSWER\mathbf{ANSWER}
注意到边权很小，所以我们考虑使用 FF 算法（一种基于流量的网络流算法）。
我们考虑先对不选边的情况跑一遍网络流，求出剩下来的残余网络。然后，我们要找到一个枚举二进制数的顺序，使得每次改变的量尽量小。
考虑格雷码，相邻两个格雷码只会差一个二进制位。因此，就有 0→10 \to 1 和 1→01 \to 0 两种情况。
  • 0→10 \to 1，即加边：我们直接在这条边上加入 2525 的流量即可。
  • 1→01 \to 0，即删边：考虑强制退流，我们记录这条边原本的流量 ff，然后将 1→u1 \to u, v→nv \to n 两条路径全部删除 ff 的流量即可。

CF1268D Invertation in Tournament

不会，回家补，先记几个结论。
Lemma.1\mathbf{Lemma. 1}
当 n≤7n \leq 7 时，反转的点至多一个。
Lemma.2\mathbf{Lemma. 2}
当 n=4n = 4 时，答案为 −1-1，当 n=6n = 6 时，答案为 22 和 1818。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...