AT_abc418_g 题解

buowen123 · 2026-04-24 17:54:20 · 题解

因为崇拜 @Moya_Rao 所以拜读了她的 ABC418D 题解！嘎嘎喵好强喵！

为了防止被单调队列，这就来写一篇 ABC418G 题解！

设 s^k 表示 k 个 s 的拼接，例如 \texttt{001}^2 = \texttt{001001}。设 T 是我们要判断合法性的串。

(0,0,0,0)

不能操作，要不然就得到 \texttt{0} 了，因此仅有 \texttt{1} 满足条件。

(0,0,0,1)

等价于与运算，因此仅有 \texttt{1}^k 满足条件。

(0,0,1,0)

如果第一个字符为 \texttt{0}，则不论怎么操作第一个字符永远是 \texttt{0}，寄了；

如果第一个字符为 \texttt{1}：

如果 T = \texttt{1} 那么显然可以；
如果第二个字符为 \texttt{0}，那么用这个 \texttt{0} 把后面删空，得到 \texttt{10}，合并即可。
如果第二个字符也为 \texttt{1} 且存在第三个 \texttt{1}，那么用第二个 \texttt{1} 把后面一段 \texttt{0} 删空，此时 T 以 \texttt{111} 为前缀，然后 \texttt{1\color{red}11} \to \texttt{10} 即可转变为第二种情况。
如果第二个字符也为 \texttt{1} 且不存在第三个 \texttt{0}，那么下一步只能删掉一个 \texttt{0} 或者同时删掉两个 \texttt{1}，发现总是会寄掉。

因此当 T 的第一个字符为 \texttt{1} 且 T \neq \texttt{11} + \texttt{0}^k 时满足条件。

(0,0,1,1)

操作不改变第一个数，如果 T 的第一个字符为 \texttt{1} 则她满足条件。

(0,1,0,0)

将 s 反转（reverse 而不是 flip）就变成了 (0,0,1,0)。

(0,1,0,1)

将 s 反转就变成了 (0,0,1,1)。

(0,1,1,0)

等价于异或运算，因此当 T 的异或和为 1 时满足条件。

(0,1,1,1)

等价于或运算，因此当 T 中存在 \texttt{1} 时满足条件。

(1,0,0,0)

考虑 |T| = 4，四个数分别为 a,b,c,d。

如果 a,b 中有 \texttt{1} 且 c,d 中有 \texttt{1}，则 \texttt{{\color{red}ab}cd} \to \texttt{0{\color{red}cd}} \to \texttt{{\color{red}00}} \to \texttt{1} 即可。
否则，不妨设 a=b=\texttt{0}：
- 若 T = \texttt{00c0}，则 \texttt{{\color{red}00}c0} \to \texttt{{\color{red}1c}0} \to \texttt{{\color{red}00}} \to \texttt{1} 即可。
- 若 T = \texttt{00c1}，则 \texttt{0{\color{red}0c}1} \to \texttt{0{\color{red}?1}} \to \texttt{{\color{red}00}} \to \texttt{1} 即可。

然后考虑 |T| \ge 5，发现随机分成 4 段分别合并就可以转化为 |T| = 4 的情况。

综上，|T| \ge 4 总是满足条件。

### $(1,0,0,1)

等价于同或运算。同或运算指的其实就是 x \oplus y \oplus 1。

由于仅有 0 参与同或运算时会改变值，因此当 T 中恰有偶数个 0 时满足条件。

（题外话：在嘎嘎喵的题解里面，这个叫做“异或非”运算，感觉这个名字确实比“同或”运算更好？）

(1,0,1,0)

操作会将第二个数取反。

若 |T| \ge 3，我们可以先将前 |T| - 1 个字符删成只剩一个，然后和最后一个字符合并；也可以删成只剩两个然后和最后一个字符依次合并。

容易发现最后一个字符可以被取反一次或两次，总有一种是 \texttt{1}，因此总是满足条件。
若 |T| \le 2 只有 \texttt{1},\texttt{00},\texttt{10} 满足条件。

(1,0,1,1)

只考虑 |T| \ge 2。

如果 T 的前两个字符不是 \texttt{01}，合并一下前缀变成 \texttt{1}，那么满足条件。

如果 T 的前两个字符是 \texttt{01} 并且后面还有 \texttt{0}，则用第一个 \texttt{0} 把后面一段 \texttt{1} 删空，此时 T 以 \texttt{00} 为前缀，于是满足条件。

如果 T = \texttt{0} + \texttt{1}^k，那就寄了。

(1,1,0,0)

将 s 反转就变成了 (1,0,1,0)。

(1,1,0,1)

将 s 反转就变成了 (1,0,1,1)。

(1,1,1,0)

考虑 |T| = 4，四个数分别为 a,b,c,d。

若 a, d 中有 \texttt{0}，则合并剩下三个然后和 \texttt{0} 合并即可；
若 b, c 中有 \texttt{1}，不妨设 b = \texttt{1}，那么 \texttt{a1{\color{red}{cd}}} \to \texttt{a1?}：
- 当 \texttt{a} 或 \texttt{?} 中有 \texttt{0} 时，不妨 \texttt{a} = \texttt{0}，那么 \texttt{0{\color{red}1?}} \to \texttt{{\color{red}0?}} \to \texttt{1} 即可；
- 否则 \texttt{1{\color{red}{11}}} \to \texttt{{\color{red}{10}}} \to \texttt{1} 即可。
若 T = \texttt{1001}，那么 \texttt{1{\color{red}{00}}1} \to \texttt{{\color{red}{11}}1} \to \texttt{{\color{red}{01}}} \to \texttt{1} 即可。

所以 |T| \ge 4 总是满足条件。

### $(1,1,1,1)

只要操作了就得到 \texttt{1}，因此当 T \neq \texttt{0} 时总是满足条件。

实现细节

有一些找最大长度的点还是有细节的。

首先如果不存在满足条件的字符串，答案直接是 -1，否则：

所有需要特判小长度的部分也需要特判 T 的长度，当然也可以枚举左端点然后循环内取 \max。

呼~ 终于推完啦！

整个推导过程不到 1h，看来我还是没有被单调队列的。

所以最终的代码（的各个部分）也都是特别简略的 ~~（偷偷尝试模仿嘎嘎喵码风）~~：

#include<bits/stdc++.h>
#define LL long long
#define Uint unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define PLL pair<LL,LL>
#define PDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 2e5+5;
LL n;string s;
void sol_0000(){
    LL cnt=0;
    for(int i=1;i<=n;i++)if(s[i]=='1')cnt++;
    if(cnt)cout<<1<<" "<<cnt<<"\n";
    else cout<<"-1 0\n";
}
void sol_0001(){
    LL len=0,ans=0,mx=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')len++;
        else len=0;
        ans+=len,mx=max(mx,len);
    }
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_0010(){
    LL len=0,ans=0;int p=n+1,flg=1,mx;
    for(int i=1;i<=n;i++)
        if(s[i]=='1')ans+=n-i+1,p=min(p,i);
    mx=n-p+1;
    for(int i=n;i>=1;i--){
        if(s[i]=='0')len++;
        else{
            if(s[i]=='1'&&s[i-1]=='1')ans-=len+1;
            len=0;
        }
    }
    if(p<n){
        flg=(s[p+1]=='1');
        for(int i=p+2;i<=n;i++)flg&=(s[i]=='0');
        if(flg)mx--;
    }
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_0011(){
    LL ans=0,mx=0;
    for(int i=1;i<=n;i++)
        if(s[i]=='1')ans+=n-i+1,mx=max(mx,n-i+1);
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_0100(){
    reverse(s.begin()+1,s.end());
    sol_0010();
    reverse(s.begin()+1,s.end());
}
void sol_0101(){
    reverse(s.begin()+1,s.end());
    sol_0011();
    reverse(s.begin()+1,s.end());
}
void sol_0110(){
    LL lst[2]={0,-1},t[2]={1,0},sum=0,ans=0,mx=0;
    for(int i=1;i<=n;i++){
        sum+=(s[i]=='1');
        ans+=t[(sum+1)%2],t[sum%2]++;
        if(lst[(sum+1)%2]!=-1)mx=max(mx,i-lst[(sum+1)%2]);
        if(lst[sum%2]==-1)lst[sum%2]=i;
    }
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_0111(){
    LL len=0,ans=n*(n+1)/2,mx=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='0')len++;
        else len=0;
        ans-=len;
    }
    if(ans)cout<<n<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_1000(){
    LL ans=0,mx=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')ans++,mx=max(mx,1ll);
        if(i<=n-1&&s[i]=='0'&&s[i+1]=='0')ans++,mx=max(mx,2ll);
        if(i<=n-2&&(s[i]=='0'||s[i+2]=='0')&&(s[i]=='1'||s[i+1]=='1'||s[i+2]=='1'))ans++,mx=max(mx,3ll);
        if(i<=n-3)ans+=n-2-i,mx=max(mx,n-i+1);
    }
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_1001(){
    LL lst[2]={0,-1},t[2]={1,0},sum=0,ans=0,mx=0;
    for(int i=1;i<=n;i++){
        sum+=(s[i]=='0');
        ans+=t[sum%2],t[sum%2]++;
        if(lst[sum%2]!=-1)mx=max(mx,i-lst[sum%2]);
        else lst[sum%2]=i;
    }
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_1010(){
    LL ans=0,mx=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')ans++,mx=max(mx,1ll);
        if(i<=n-1&&s[i+1]=='0')ans++,mx=max(mx,2ll);
        if(i<=n-2)ans+=n-1-i,mx=max(mx,n-i+1);
    }
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_1011(){
    LL ans=n*(n+1)/2,mx=n,len=0;
    for(int i=n;i>=1;i--){
        if(s[i]=='1')len++;
        else{
            if(len==n-1)mx--;
            ans-=len+1,len=0;
        }
    }
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_1100(){
    reverse(s.begin()+1,s.end());
    sol_1010();
    reverse(s.begin()+1,s.end());
}
void sol_1101(){
    reverse(s.begin()+1,s.end());
    sol_1011();
    reverse(s.begin()+1,s.end());
}
void sol_1110(){
    LL ans=0,mx=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')ans++,mx=max(mx,1ll);
        if(i<=n-1&&(s[i]=='0'||s[i+1]=='0'))ans++,mx=max(mx,2ll);
        if(i<=n-2&&(s[i]=='0'||s[i+1]=='1'||s[i+2]=='0'))ans++,mx=max(mx,3ll);
        if(i<=n-3)ans+=n-2-i,mx=max(mx,n-i+1);
    }
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
void sol_1111(){
    LL ans=0,mx=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')ans++,mx=max(mx,1ll);
        if(i<=n-1)ans+=n-i,mx=max(mx,n-i+1);
    }
    if(ans)cout<<mx<<" "<<ans<<"\n";
    else cout<<"-1 0\n";
}
int main(){
    cin>>n>>s;s=" "+s;
    sol_0000();sol_0001();sol_0010();sol_0011();
    sol_0100();sol_0101();sol_0110();sol_0111();
    sol_1000();sol_1001();sol_1010();sol_1011();
    sol_1100();sol_1101();sol_1110();sol_1111();
    return 0;
}

~~如果觉得本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢了喵！~~

欸，真的能有帮助吗？