date: 2022-11-14
%%
CodeChef上的题号就是一串 Problem Code ，所以我就这样记了
吐槽：
AK DIV4 再加1题就AK DIV1了
CodeChef的四个div的题目高度重合
%%
[[bitmasks]]
[[division]]
因为有一个情况没考虑到，昨天晚上调了很久
还是QY的暴力拍出来的
二进制按位考虑，发现：
\(2^0\equiv 1,2^1\equiv 2,2^2\equiv 1\dots \pmod3\)
所以先算出目前的01串在二进制下模3等于几（设这个值为an）
如果an=0，那么直接输出0
如果an=1，那么就是从2到1移一个，或者是从1到2移两个
如果an=2，那么就是从1到2移一个，或者是从2到1移两个
（实际上还有一种最特殊的情况，等会儿再考虑）
所以现在我们需要数出
从2到1 和 从1到2 最大移动的次数
对一个0，如果两侧有1，那么到这个0的位置的移动是可行的
但这样会出现一个问题，比如010的情况，-1不能算两次
问题出现的原因是一个1不能填两个0，所以如果两侧至少有一边是1就可以全部覆盖
所以只需要对孤立的01间隔区间进行计数，然后少算一个之前多算的转移类型
这样会WA4个点，问题就是之前提到的特殊情况
拍出来的数据是 11100000
答案是3！
目标状态是 10101000
这种情况为什么会发生？
如果这是一个无限01串，那么答案是不会出现3的
这有这样1区间靠一侧，只有一个"眼"的情况会发生
如果有两个"眼"，可以证明，不会出现3
所以这种是特判一下就行了，不是普遍情况
#include<bits/stdc++.h>
using namespace std;
bool mem1;
#define _WD_ bool mem2; signed main
#define int long long
mt19937 gen(time(0));
const int mod=998244353,N=300005;
int T,n,k,l,m[2],an;
char a[N];
void jg(){
int i=1,s,sf,l;
int f=!(n&1);
if(a[1]==1){
while(i<=n&&a[i]==1)i++,f=!f;s=i,sf=f;
while(i<=n&&a[i]==0)i++,f=!f;
if(i==n+1&&s>2&&n-s+1>=2)puts("3");
else puts("-1");
}else{
while(i<=n&&a[i]==0)i++,f=!f;s=i,sf=f;
while(i<=n&&a[i]==1)i++,f=!f;
if(i==n+1&&n-s+1>=2&&s>2)puts("3");
else puts("-1");
}
}
void sol(){
cin>>a+1;
m[0]=m[1]=0;
n=strlen(a+1);
int f=!(n&1);
an=0;
for(int i=1;i<=n;i++)a[i]-='0';
for(int i=1;i<=n;f=!f,i++)if(!a[i]){
if(a[i-1]==1||a[i+1]==1)
m[f]++;
}else an+=f+1;
f=!(n&1);
for(int i=1;i<=n;f=!f,i++){
while(i<=n&&a[i]==a[i-1]&&a[i]==0&&a[i+1]==1){
int he=i;
while(1){
i++;f=!f;
if(i>n)break;
if(a[i]==a[i-1]&&a[i]==0){
m[!f]--;
break;
}
if(((i-he)&1)!=a[i])break;
if(a[i]==0&&i==n){
m[f]--;
break;
}
}
}
}
cerr<<m[0]<<m[1];
an%=3;
if(an==0)puts("0");
else if(an==1){
if(m[0]>=1)puts("1");
else if(m[1]>=2)puts("2");
else jg();
}else{
if(m[1]>=1)puts("1");
else if(m[0]>=2)puts("2");
else jg();
}
}
_WD_(){
cin>>T;
while(T--)sol();
cerr<<"MemoryCost:"<<(&mem1-&mem2)/1024./1024.<<"MB\nTimeCost:"<<clock()*1./CLOCKS_PER_SEC<<"s";
return 0;
}