xy0v0's Blog

Back

题面#

For a binary string B=B1B2…B3nB = B_1 B_2 \dots B_{3^n} of length 3n3^n (n≥1n \geq 1), we define an operation to obtain a binary string C=C1C2…C3n−1C = C_1 C_2 \dots C_{3^{n-1}} of length 3n−13^{n-1} as follows:

  • Partition the elements of BB into groups of 33 and take the majority value from each group. That is, for i=1,2,…,3n−1i=1,2,\dots,3^{n-1}, let CiC_i be the value that appears most frequently among B3i−2B_{3i-2}, B3i−1B_{3i-1}, and B3iB_{3i}.

You are given a binary string A=A1A2…A3NA = A_1 A_2 \dots A_{3^N} of length 3N3^N. Let A′=A1′A' = A'_1 be the length-11 string obtained by applying the above operation NN times to AA.

Determine the minimum number of elements of AA that must be changed (from 00 to 11 or from 11 to 00) in order to change the value of A1′A'_1.

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

题目分析#

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

解题思路#

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

举例:000110001

叶子结点计算得:

C1=2,C2=1,C3=1C_{1}=2, C_{2} = 1 , C_{3} = 1

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

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