题解：AT_abc391_e [ABC391E] Hierarchical Majority Vote

· · 题解

更好的阅读体验

建议难度：\color{#FFC116}\text{普及/提高-}

题目大意

定一个长度为 3^N 的二进制字符串 A，通过 N 次操作将其压缩为长度为 1 的字符串 A'_1。每次操作将字符串分成长度为 3 的组，取每组的多数值作为新字符串的元素。目标是通过最少的修改次数（将 0 改为 1 或将 1 改为 0），使得最终的 A'_1 发生变化。

解题思路

  1. 操作过程： 每次操作都将字符串分成每 3 个字符为一组，对每组的 3 个字符取多数值：如果大于等于 2 个字符是 1，则该组的值为 1，否则为 0。每次操作都会使得字符串的长度缩小为原来的三分之一。

  2. 目标： 我们最终希望通过最少的位变化，将经过 N 次操作后得到的字符串的结果从当前值变为相反的值。

  3. 步骤：

    • 模拟操作： 从输入字符串 A 开始，反复执行 N 次操作，得到最终的一个字符。
    • 计算最小改变次数： 对于每次操作，我们需要计算在将字符串压缩的过程中，最少需要改变多少个位来改变最终结果。

  4. 数据结构： 使用一个结构体 ST 来存储每个字符变为 0 和变为 1 的代价。然后，通过动态规划的方式，逐步计算出最少的改变次数。

动态规划思路

通过动态规划，我们逐步压缩字符串，计算每次压缩的代价，并最终得出最少修改次数。每一步的状态转移考虑当前字符的变换代价，以确保最小化最终的修改次数。

  1. 状态定义： 对于每个子串（每 3 个字符），我们需要知道将其压缩成 0 或 1 的代价。这个代价的计算基于每个字符变为 0 或 1 的代价。

  2. 操作过程：

    • 每次操作都将字符串的长度缩小为原来的三分之一，每 3 个字符会根据多数值生成新的字符。
    • 我们计算每组字符（3 个字符）压缩为 0 或 1 的代价。我们希望通过最少的改变次数，决定当前字符的转换方式。

  3. 转移方程： 对于每组 3 个字符，我们可以遍历每种可能的组合（变为 0 或 1），然后选择使得多数值符合目标的最小代价。最终，动态规划状态会记录每个位置的最小代价。

  4. 最小改变次数： 每次操作后，通过动态规划更新状态，并计算最小改变次数。最终，我们得到将字符串最终值从当前的 0 或 1 转换为目标值的最小操作次数。

  5. 结果计算： 完成 N 次操作后，通过动态规划数组中存储的代价，计算最少修改次数，得出最终结果。

时间复杂度

每次操作都会将字符串的长度减少为原来的三分之一。每次对 3 个字符的子串进行处理，因此总体时间复杂度为 \text{O}(3^N)。对于 N \leq 13 的情况下，是完全可以被接受的。

link