通过一次翻转k位使最大值为1

Question

给定一个n位向量和一个整数k，1 <= k <= n，我们必须通过多次应用以下操作（包括零次）来最大化其中的个数：

• 精确选择k位（不一定是连续的）并翻转其状态（0到1、1到0）；

经过分析，我得出结论，如果n> k，我们也可以同时翻转任意两位。例如，对于n = 5，k =4。我们可以这样做，仅翻转最后两位。

• xxxx_
• xxx_x

“ x”表示我们在该位置翻转位。

但是我不确定之后该如何进行，而且我无法再进行任何观察了。那么，什么是正确的方法呢？您可以假设使用n ^ 2算法是可行的。

Answer 1

戴夫的方法似乎是正确的。我将在此处发布问题后分享我的想法。

设零的数量为z，现在让自己相信，如果k < n，我们可以通过使用问题中提到的 k 位运算的组合来翻转任意两位（一对）。这里有一个论据可以帮助您满足这一事实，选择除k - 1您想要翻转的对之外的任何位；然后从我们刚刚选择的一对中选择一位k - 1，应用操作；然后从该对中选择另一个位以及k - 1我们之前选择的相同位，再次应用该操作。如果或至少为 ，我们保证找到这些k - 1辅助位。k < nnk + 1

那么自然会出现两种情况：

• k == n：显然我们只能全部翻转或不翻转。所以答案是max(n - z, z)
• k < n：在这种情况下，我们可以翻转任何k位，也可以翻转任何 2 位（使用上面的参数）。现在，如果z < k，我们只能使用 2 位翻转，如果z是奇数，我们剩下一位仍然是 0，答案是n - 1；如果z是偶数，我们将它们全部翻转为 1，所以答案是n。现在z >= k，当 时，我们可以同时使用 k 位 fips 和 2 位翻转，要求是，如果z是奇数且k是偶数，我们只剩下一个 0（答案是n - 1），否则我们总是可以将所有 0 变成 1（答案是n）。

最后一个主张的解释：如果我们可以同时使用 k 位翻转和 2 位翻转并且z恰好是奇数，我们尝试使用一次 k 位翻转来改变剩余 0 的奇偶校验（parity of z - k）。仅当 k 为奇数时我们才能这样做，否则我们无法这样做，并且对奇数个零使用 2 位运算将留下一个零。所以，简而言之，如果k与 odd 为偶数z，我们将剩下一个 0，否则我们将得到全 1。