ABC 391 E 题解整理
题面 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-
题面#
For a binary string of length (), we define an operation to obtain a binary string of length as follows:
- Partition the elements of into groups of and take the majority value from each group. That is, for , let be the value that appears most frequently among , , and .
You are given a binary string of length . Let be the length- string obtained by applying the above operation times to .
Determine the minimum number of elements of that must be changed (from to or from to ) in order to change the value of .
简单来说,给定01字符串 ,长度为 ,每次操作将字符串分割为三个为一组,取出现最多的数替代这三个数字,要使最终得到的字符串改变结果 ,最少需要改变几个数字
题目分析#
首先进行分析 ,不难发现只有 经过操作后得到的是 ,其余情况得到的均为 。要将三个一组的数经过操作得到的结果变为另一种,需要改变1/2个数字,其中改变2个数字的有 其余情况均只需改变一个数字。我们可以定义要改变的数字数量为代价,考虑建图。
解题思路#
可以考虑递归建树,可将字符串 视为三叉树的叶子结点,对每个节可定义 ,代表改变为另一个数所需的代价。首先计算叶子节点的 ,非叶子节点可由叶子节点递推得到。
举例:000110001
叶子结点计算得:
其祖先节点计算原始多数值为 ,计算其 时可以选择改变第一位,也可以选择改变第三位,但是显然改变第三位更优。
对于如何简易计算 ,我们不难发现当三数字相同时候需改变其中两个数字,改变两个和最小的即可。当两数字相同时只需改变两相同数字中较小的那个。