首先我们先观察三个串 1010,110110,11101110,答案都是红色部分,我们可以下一个结论,形如 abab ( a 中有非负整数个 1 , b 中只有一个 0 )这类的字符串答案恒为 2 ,也就是 k==2 ,然后就是用这类字符串去构造出我们所需的 k 。我们可以尝试从末尾加一个1,那么之前的串变成了 10101,1101101,111011101,那么答案为红色部分。我们可以发现,通过我们末尾添加的1,导致之前红色部分的 01 与我们末尾添加的1与前面一个0构成的 01 重复,使得之前的红色部分向后挪一位。于是,我们可以用这一规律去构造出我们想要的k,显然答案就是末尾部分的01(蓝色部分111...10111...10111)满足 0 的个数加 1 的个数等于 k-1 ,那么对中间的影响(绿色部分111...1011111...110111)往后挪一位也就是我们的答案 k ,最后就是算出这形如 abab 字符串 a 部分中的 1 的个数有多少就行了,设 x 为 a 中 1 的个数,方程为 2*x+1+k-1=n ,化简为 x=(n-k)/2 ,根据题意 n 与 k 同奇偶,那么 x 也是唯一确定的,最后构造也由此生成。
1 // ——By DD_BOND 2 3 //#include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include