题解：CF2065E Skibidus and Rizz

· · 题解

题面

要求构造一个长度为 n+m 的 01 串，其中 0 有 n 个，1 有 m 个，且它的所有子串中，0 与 1 的差最大的恰好为 k。

思路

无解 -1 的情况有两种，即为 n<k 且 m<k，或者 \max(n,m)-\min(n,m)>k 都很好理解。

能发现，形如 

1010...101011...1100...001010...1010

这样的串，左右两侧的 01 交替串对中间并没有贡献。

所以，可以先把 n 个 1 和 m 个 0 先连续放在左右两侧，接着，从两侧开始隔一位交换一对 0 和 1，直到中间的连续 1 和 0 有一个等于 k。

即 

000..00111..11

变为

01000..0011..11101

再变为

010101...00..0011..11..010101

还有一些细节稍微处理一下就 A 啦！

AC code