AT_abc391_e [ABC391E] Hierarchical Majority Vote
题目描述
[problemUrl]: https://atcoder.jp/contests/abc391/tasks/abc391_e
对于长度为 $3^n \ (n \geq 1)$ 的 $01$ 序列 $B = B_1\ B_2\ \dots\ B_{3^n}$，我们定义以下操作来获得长度为 $3^{n-1}$ 的 $01$ 序列 $C = C_1\ C_2\ \dots\ C_{3^{n-1}}$：
- 将 $B$ 的元素每 $3$ 个一组进行多数决。即对于每个 $i = 1, 2, \dots, 3^{n-1}$，取 $B_{3i-2}, B_{3i-1}, B_{3i}$ 中出现次数最多的值作为 $C_i$。
给定长度为 $3^N$ 的 $01$ 序列 $A = A_1\ A_2\ \dots\ A_{3^N}$。将上述操作对 $A$ 连续应用 $N$ 次后，得到长度为 $1$ 的序列 $A' = A'_1$。
现在考虑将 $A$ 中若干元素从 $0$ 改为 $1$ 或从 $1$ 改为 $0$，求需要修改的最小元素个数，使得 $A'_1$ 的值发生改变。
输入格式
无
输出格式
无
说明/提示
### 约束条件
- $N$ 是 $1$ 以上 $13$ 以下的整数
- $A$ 是由 $0$ 和 $1$ 构成的长度为 $3^N$ 的字符串
### 样例解释 1
对 $A = 010011101$ 应用两次操作的过程如下：
- 第 $1$ 次：
$010$ 的多数结果为 $0$，
$011$ 的多数结果为 $1$，
$101$ 的多数结果为 $1$，
连接得到 $011$。
- 第 $2$ 次：
$011$ 的多数结果为 $1$，
最终得到 $1$。
要将最终值从 $1$ 改为 $0$，例如将 $A$ 的第 $5$ 个字符从 $1$ 改为 $0$，得到 $A = 010001101$。修改后的操作过程如下：
- 第 $1$ 次：
$010$ 的多数结果为 $0$，
$001$ 的多数结果为 $0$，
$101$ 的多数结果为 $1$，
连接得到 $001$。
- 第 $2$ 次：
$001$ 的多数结果为 $0$，
最终得到 $0$。
因此，最少需要修改 $1$ 个元素。
翻译由 DeepSeek R1 完成