问题来源

洛谷P6366

问题的数学描述

以0-9以及A-F为表示字符，输入一个字符串$S$，代表一个十六进制数，其对应的二进制数的位串为$S_B$，长度为$n$（去除前导零）。
定义操作$L(i)$：将$S_B$的第$i$位¹、第$(i-1)$位、第$(i+1)$位取反，若其中某位不存在则忽略（即$i-1<0\vee i+1>n-1$）。
设计程序，求解最少进行多少次操作$L(i)$，能够使得$S_B$转换为全0串。

问题分析

将输入的字符串$S$转换为$S_B$并不困难，因为每个十六进制位(digit)唯一对应一组4-bit二进制串。主要的问题在于操作$L$。

这个问题的目标是要进行操作，使得$\forall i\in [0,n)(i\in \mathbb{Z}),S_B[i]=0$。其实对于特定的位置$i$，我们只有两种选择，即进行或不进行$L(i)$，因为在同一$i$处，不论进行多少次操作，其效果都相当于进行0次或1次操作。

涉及到按位取反，可以想到在布尔代数中$\bar{A}=A\oplus 1$²。所以，如果将操作$L(i)$用包含异或运算的伪代码来表示的话，它可以变成这样：
procedure $L(S_B,i)$
$S_B[i-1]:=S_B[i-1]\oplus 1$
$S_B[i]:=S_B[i]\oplus 1$
$S_B[i+1]:=S_B[i]\oplus 1$
end procedure

如果操作$L$对同一位置取反了$k$次（$k\ge 0$)，则该位置的值会变为$$b_{\text{orig}}\oplus \left(\underset{k个1}{\underbrace{1\oplus 1\oplus \cdots \oplus 1}}\right)=\{\begin{array}{ll}{\bar{b}}_{\text{orig}},& k\text{ is odd},\\ b_{\text{orig}},& k\text{ is even}.\end{array}$$

我们可以定义一个长度为$n$的二进制串$p$，某一位为1表示在该处应当进行$L(i)$（或进行奇数次），为0则表示在该处不应当进行$L(i)$（或进行偶数次）。在按照$p$进行完操作之后，为了满足全零的条件，由上面的公式可知$$\{\begin{array}{ll}p[i-1]\oplus p[i]\oplus p[i+1]=S_B[i],& 1\le i<n-1,\\ p[0]\oplus p[1]=S_B[0],(\ast )& \\ p[n-2]\oplus p[n-1]=S_B[n-1].& \end{array}$$
所以，解决这道题的目标就变成了寻找满足上述等式的$p$。如何找到它呢？我们可以从边界上入手，因为这些地方影响因素只有两个，相比于既要考虑左侧又要考虑右侧的中间位置显然简单得多。根据题目条件，前导零不会在$S_B$中存在，所以$S_B[0]=1$，我们就从这里入手。

此时，等式$(\ast )$便转化为$p[0]\oplus p[1]=1$。根据异或运算的性质，$p[0]={\left(p[1]\right)}^{\prime }$，因此，前两位的组合要么是$(0,1)$，要么是$(1,0)$，只有这两种情况，我们可以逐个尝试。在已知前两位的情况下，我们我们可以继续应用第一个等式，将$p$的剩余部分求出。比如，当$i=1$时，$p[0]\oplus p[1]\oplus p[2]=S_B[1]$，该式中已经只有一个未知数$p[2]$。
在接近末尾的时候，再根据第三个等式判断当前的$p$是否能够满足要求，如果满足，那么目的就达到了。最终的答案就是两种情况下能够满足要求的$p$中1的个数的最小值。

代码？

没有代码。