AT_abc418_g

类似题目 gym102586J，P12294。按某种简单规则判定 01 串，可以考虑造一个自动机判定。

考虑直接根据等价关系建自动机，根据 Myhill-Nerode 定理，

x\equiv_L y

当且仅当对于任意字符串

z

，

xz\in L

当且仅当

yz\in L

。因为规则简单，自动机的结构应该也很简单，经试验，仅考察

|x|\leq 4

的

x

的等价关系就可区分出所有串。同理，对于

z

，长度较长的

z

也只会在自动机上绕圈，经试验，只用考察

|z|\leq 2

的

z

。实现时根据接受

xz

的情况划分

x

的等价类，每个等价类取长度最小的串为代表元，考察代表元的转移建出 DFA。此题里自动机的结构都很简单，最大点数为

7

。

有了自动机，剩下的部分很简单，枚举右端点，记当前转移到每个自动机节点的最左左端点/左端点个数。

CPP

#include<bits/stdc++.h>
using namespace std;
int n,g[65536],p[32],type[32],id[10],f1[10],f2[10],t1[10],t2[10];
string s;
vector<bool>l[32];
bool cmp(int a,int b){
  return l[a]==l[b]?a<b:l[a]<l[b];
}
struct DFA{
  int tr[50][2],cnt,s;
  bool b[50];
  bool dfs(int s,int opt){
    if(g[s]!=-1)return g[s];
    for(int i=0;i<__lg(s)-1;i++){
      int x=s>>(i+2),y=s>>i&3,z=s&((1<<i)-1);
      if(dfs(x<<(i+1)|(opt>>(y==0||y==3?3-y:y)&1)<<i|z,opt))return g[s]=1;
    }
    return g[s]=0;
  }
  void build(int opt){
    int num=0;
    cnt=0,memset(g,-1,sizeof(g)),g[1]=g[2]=0,g[3]=1;
    for(int lenx=0;lenx<=4;lenx++){
      for(int x=1<<lenx;x<2<<lenx;x++){
        l[x].clear(),p[num++]=x;
        for(int leny=0;leny<=2;leny++)for(int y=1<<leny;y<2<<leny;y++)l[x].push_back(dfs(y<<__lg(x)|(x&~(1<<__lg(x))),opt));
      }
    }
    sort(p,p+num,cmp);
    for(int i=0;i<num;i++){
      if(!i||l[p[i]]!=l[p[i-1]])id[++cnt]=p[i];
      type[p[i]]=cnt;
    }
    s=type[1];
    for(int i=1;i<=cnt;i++)tr[i][0]=type[3<<__lg(id[i])^id[i]],tr[i][1]=type[3<<__lg(id[i])|id[i]];
    for(int i=1;i<=cnt;i++)b[i]=dfs(id[i],opt);
  }
}d[16];
int main(){
  for(int i=0;i<16;i++)d[i].build(i);
  cin>>n>>s;
  for(int t=0;t<16;t++){
    int ans1=-1;
    long long ans2=0;
    memset(f1,0x3f,sizeof(f1)),memset(f2,0,sizeof(f2));
    for(int i=0;i<s.size();i++){
      memset(t1,0x3f,sizeof(t1)),memset(t2,0,sizeof(t2)),f1[d[t].s]=min(f1[d[t].s],i),f2[d[t].s]++;
      for(int j=1;j<=d[t].cnt;j++)t1[d[t].tr[j][s[i]-'0']]=min(t1[d[t].tr[j][s[i]-'0']],f1[j]),t2[d[t].tr[j][s[i]-'0']]+=f2[j];
      for(int j=1;j<=d[t].cnt;j++){
        f1[j]=t1[j],f2[j]=t2[j];
        if(d[t].b[j])ans1=max(ans1,i-f1[j]+1),ans2+=f2[j];
      }
    }
    cout<<ans1<<' '<<ans2<<'\n';
  }
  return 0;
}

文章操作

相关推荐

评论

AT_abc418_g