题解 CF1158B 【The minimal unique substring】

神仙题，那场CF有三个红黑名没做出来的奇怪构造题。 我也是赛后看的dalao的博客才会的 这么构造 直接上代码,构造正确性的证明放后面： ``` #include<bits/stdc++.h> using namespace std; int n,k; int main() { scanf("%d%d",&n,&k); for(int i = 1;i <= n; i ++) { printf("%d",(i%((n-k)/2+1)>0)); } return 0; } ``` 为什么这样做是对的呢？ 然后您试几组数据，就会发现字符串长这样 设$l = \frac{n-k}{2}$ `[11..11(l个1)0][11..11(l个1)0]...[11..11(l个1)0][11111]`我们把每个中括号里的字串，称之为一个“块” 接下来，我们选取从$s_{l+1}$到$s_{n-l}$这一段字符串。 会发现长度一定为k,且一定不会在$s$中再次出现 证明： 先需要证明一定有一个不重复出现的长度为k的串 首先，$s_{l+1}$一定是一个0,且下一个0要到下一个块里找，至少要到$s_{2l+2}$，但是此时从$s_{2l+2}$开头已经无法容纳一个长度为$k$的子串了 接下来，证明长度$< k$的子串肯定重复出现，设长度为$t$ 对于一个子串，假如它开头不是从第一个块开始的，则将其左移$l+1$的位置即可找到相同的字符串（因为块块之间相同，最后一个块与其他块的前缀相同） 否则，右移 $l+1$位置, 我们可以证明，一定不会超出边界 设初始位置为$p$ 则原来的结束位置为 p+t-1 右移后位置 p + t + l 因为 $p <= l+1 = \frac{n-k}{2}+1$ $t <= k-1$ $l = \frac{n-k}{2}$ 所以 $p+t+l <= n$ 到此证明完毕