C
很久没见到过这么清晰的讲题人了。
我们先来考虑一些边界情况。
全是 \(0\) 时
这个时候其实就是划分成至少 \(k\) 段的方案数,组合数计算即可。答案大概为
\[\sum_{i = k - 1}^{n}\binom{n - 1}{i} \]存在前导零长度大于等于 \(k - 1\) 时
例如 001111
想分成至少 \(3\) 段,发现仅仅是开头的 00
就已经可以分出去两段了,这个时候我们把最后的一段直接分给除前导零外的段即可。最大值即为除去前导零的剩余段,方案数可以组合数计算,设前导零长度为 \(c(c \ge k - 1)\) 则答案大致为
事实上,第一种情况就是第二种情况中 \(c = 0\) 时,这里拿出来单独讨论了。
一般情况
实际上,这里的 一般情况 指的就是前导零不够分的时候。我们可以从前导零够分段的情况获得一些启示,显然分开算两段一定是没有合在一起算好的。
还是简要证明一下吧。
考虑两个二进制数 \(A, B\),如果分开算的话,和为 \(A+B\),如果合到一起算的话和为 \(A \times 2^{|B|}+B\)。结论显然。
根据上面的证明,我们一定是要从前 \(c(0 \le c < k - 1)\) 个前导零中分出尽量多的段出来,则 \(k' = k - c, n' = n - c\)。
这一部分的方案数就是 \(1\),我们已经确定了每一位单独一段。
问题进行了转化,我们有一个第一位为 \(1\) 的二进制串,根据我们上面的证明,我们分段的策略也仍然是分出 \(k'- 1\) 段长度为 \(1\) 的段和一段长度为 \(n' - k' + 1\) 的段,我们考虑它答案的形式。
令当前选择的大段为 \(S\),那么整段的答案变为 \(S - \text{popcount(S)} + c\),后面这个 \(c\) 实际上就是整段的 \(1\) 数量,将 \(S\) 内计入大段的 \(1\) 减掉即为长度为 \(1\) 的 \(1\) 的贡献。
问题来了,关于方案数,我们是否可以对当前的 \(S\) 进行一些小变化使得答案还是最大的。
考虑当 \(S\) 的末尾为 \(1\) 时,如果这一位变成了 \(0\),\(S \to S - 1, \text{popcount(S)} \to \text{popcount(S)} - 1\),\((S - 1) - (\text{popcount(S)} - 1) = S - \text{popcount(S)}\),答案没有任何变化。
注意,当 \(n = k\) 时,答案为 \(\text{popcount(S)}\),方案数为 \(1\)。
标签:10,26,方案,text,popcount,答案,2023,前导,我们 From: https://www.cnblogs.com/Rainsheep/p/17802273.html