Подход Дейва кажется правильным.Я поделюсь своим, что я понял после того, как я разместил вопрос здесь.
Пусть число нулей будет z, теперь убедитесь, что если k < n, мы можем перевернуть любые два бита (пары), используя комбинацию k-битной операции, упомянутой в задаче.Вот аргумент, который поможет вам удовлетворить этот факт, выберите любые k - 1 биты, кроме пары, которую вы хотите перевернуть;затем выберите один бит из пары вместе с k - 1, который мы только что выбрали, примените операцию;затем выберите другой бит из пары вместе с теми же k - 1 битами, которые мы выбрали ранее, примените операцию снова.Мы гарантированно найдем эти k - 1 вспомогательные биты, если k < n или n не меньше k + 1.
Поэтому, естественно, возникают два случая:
k == n: ясно, что мы можем только перевернуть все или перевернуть ни одного.Таким образом, ответ будет max(n - z, z)k < n: в этом случае мы можем перевернуть любые k биты или мы можем перевернуть любые 2 бита (используя аргумент выше).Теперь, если z < k, мы можем использовать только 2-битные перевороты, а если z нечетно, у нас останется один бит, все еще 0, ответ - n - 1;если z четное, мы переворачиваем их все на 1, поэтому ответ n.Теперь, когда z >= k, мы можем использовать как k-битные, так и 2-битные переходы, утверждается, что если z нечетно и k четно, у нас остается один 0 (ответ n - 1)в противном случае мы всегда можем превратить все 0 в 1 (ответ n).
Объяснение последнего утверждения: Если мы можем использовать как k-битные, так и 2-битные и z нечетно, мы пытаемся использовать один k-бит перевернуть, чтобы изменить четность оставшихся 0 (четность z - k).Мы можем сделать это только в том случае, если k нечетно, иначе мы не сможем это сделать, и использование 2-битных операций с нечетным числом нулей оставит нас с одним нулем.Итак, в двух словах, если k четное с нечетным z, у нас останется один 0, в противном случае мы получим все 1.