题面

For a binary string ​B = B_1 B_2 \dots B_{3^n} of length ​3^n (​n \geq 1), we define an operation to obtain a binary string ​C = C_1 C_2 \dots C_{3^{n-1}} of length ​3^{n-1} as follows:

• Partition the elements of ​B into groups of ​3 and take the majority value from each group. That is, for ​i=1,2,\dots,3^{n-1}, let ​C_i be the value that appears most frequently among ​B_{3i-2}, ​B_{3i-1}, and ​B_{3i}.

You are given a binary string ​A = A_1 A_2 \dots A_{3^N} of length ​3^N. Let ​A' = A'_1 be the length-​1 string obtained by applying the above operation ​N times to ​A.

Determine the minimum number of elements of ​A that must be changed (from ​0 to ​1 or from ​1 to ​0) in order to change the value of ​A'_1.

简单来说，给定01字符串 ​A ，长度为 ​3^n ，每次操作将字符串分割为三个为一组，取出现最多的数替代这三个数字，要使最终得到的字符串改变结果 ​(0 \rightarrow 1 \ or \ 1 \rightarrow 0) ，最少需要改变几个数字

题目分析

首先进行分析 ，不难发现只有 ​0,1,2,4 经过操作后得到的是 ​0 ，其余情况得到的均为 ​1 。要将三个一组的数经过操作得到的结果变为另一种，需要改变1/2个数字，其中改变2个数字的有 ​000, 111 其余情况均只需改变一个数字。我们可以定义要改变的数字数量为代价，考虑建图。

解题思路

可以考虑递归建树，可将字符串 ​A 视为三叉树的叶子结点，对每个节可定义 ​Cost ，代表改变为另一个数所需的代价。首先计算叶子节点的 ​Cost ，非叶子节点可由叶子节点递推得到。

举例：000110001

叶子结点计算得：

其祖先节点计算原始多数值为 ​010 ，计算其 ​C_1 时可以选择改变第一位，也可以选择改变第三位，但是显然改变第三位更优。

对于如何简易计算 ​Cost ，我们不难发现当三数字相同时候需改变其中两个数字，改变两个和最小的即可。当两数字相同时只需改变两相同数字中较小的那个。