脚本宝典收集整理的这篇文章主要介绍了CF1658F Juju and Binary String 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
Post time: 2022-03-28 15:56:21
A wonderful PRoof of (kleq 2) in Problem.F, which (k) is the the minimum number of subsegments required.
wrITten by @smax
Note: all VARiable names will either be the same ones used in the problem statement or explicitly defined.
Part 1: How many zeros and ones are in the answer?
Let the number of ones in (s) be (ones). The cuteness of the entire string by definition is (frac{ones}{n}). The concatenated string of length (m) that we're looking for has the same cuteness, so the number of ones in it is (frac{ones}{n}cdot m). Therefore, there is no answer if that value is not an integer (i.e. (onescdot mnotequiv 0pmod n)).
Part 2: How do we find the answer with the minimum number of parts?
Let (x=frac{ones}{n}cdot m).
Let's also assume the string is circular for now. Consider any length (m) subarray in this circular string, including subarrays that wrap around. If we can find a subarray with exactly (x) ones, then the minimum number of parts we need is either (1) or (2), dePEnding on whether or not it wraps around. And both can be checked with sliding window/prefix sums.
It turns out such a subarray always exists. Let (c_i) be the number of ones in s[i...i+m-1] if (ileq n-m+1), or s[1...m-(n-i+1)]+s[i...n] otherwise (basically, subarrays that wrap around versus subarrays that don't). Note that (|c_{i+1}-c_i|leq 1) for all (1leq i<n) and (|c_1-c_n|leq 1). This is because if we slide the subarray we're considering From (i) to (i+1), we exclude (s_i) and include (s_{((i+m-1)bmod n)+1}). So the number of ones in our subarray can only increase or decrease by at most (1). The implication of this is that there exists some (c_i=y) for all (min c_ileq yleq max c_i) because there's no way to go from a small to large (c_i) while "skipping" over the values in the middle.
It holds that (max c_igeq x) and (min c_ileq x), implying some (c_i=x). Assume that (max c_i<x). This means (sum^n_{i=1} c_i<ncdot x). Furthermore, each index is included in exactly (m) different subarrays. So (sum^n_{i=1} c_i=mcdot ones). Thus, (mcdot ones<ncdot x), or (x>frac{mcdot ones}n) which is a contradiction by definition of (x). Similarly, assume (min c_i>x). (sum^n_{i=1}c_i=mcdot ones>ncdot x), or (x<frac{mcdot ones}n) which is a contradiction. Therefore, (max c_igeq x) and (min c_ileq x).
以上是脚本宝典为你收集整理的CF1658F Juju and Binary String 题解全部内容，希望文章能够帮你解决CF1658F Juju and Binary String 题解所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。