题解 CF1658F

dead_X · 2022-03-29 11:00:53 · 题解

思路

脑筋急转弯，为什么不是 div.2 C 呢。

记字符串有 A 个 \texttt{0} 和 B 个 \texttt{1}，那么将一个 \texttt{0} 的价值记为 -B，一个 \texttt{1} 的价值为 A，显然价值和为 0 的子串的可爱度和整个串的可爱度就是一样的。

抛出一个重磅结论：我们把最后一个字符和第一个字符连起来，形成一个环，环上一定存在一个长度为 m 的区间的价值和为 0。

证明：如果每个区间价值和都 >0 或每个区间价值和都 <0，整个串的价值和不可能为 0。如果存在一个 >0 的区间和 <0 的区间，因为相邻区间中字符 \texttt{1} 的数量的变化量不超过 1，所以中间总存在一个价值和为 0 的区间。

于是答案不超过 2，检查答案是否能为 1 即可。

别忘了特判一个串里要有小数个 \texttt{1} 的情况，这一定是不合法的。

代码

signed main()
{
    for(int T=read();T--;)
    {
        int n=read(),m=read();
        scanf("%s",s+1);
        int c0=0;
        for(int i=1; i<=n; ++i) c0+=s[i]=='1';
        if((m*c0)%n)
        {
            puts("-1");
            continue;
        }
        for(int i=1; i<=n; ++i)
            a[i]=s[i]-48,a[n+i]=s[i]-48;
        int N=n<<1;
        for(int i=1; i<=N; ++i) if(a[i]) a[i]=n-c0; else a[i]=-c0;
        for(int i=1; i<=N; ++i) a[i]+=a[i-1];
        int l=0,r=0;
        for(int i=m; i<=N; ++i)
            if(a[i-m]==a[i])
            {
                l=i-m+1,r=i;
                break;
            }
        assert(l);
        if(r<=n) puts("1"),printf("%lld %lld\n",l,r);
        else puts("2"),printf("%lld %lld\n",1ll,r-n),printf("%lld %lld\n",l,n);
    }
    return 0;
}