Educational Codeforces Round 157 (Rated for Div. 2)

C.Torn Lucky Ticket

一道经典的前缀哈希题
先看代码

str a[N];
void moon(){
     cin>>n;
    eps(i,1,n)cin>>a[i];
// 奇数+奇数 偶数+偶数
 ll res=0;
map<pll,ll>p;
map<ll,ll>pp;
 eps(i,1,n)
{
  res=0;
  for(auto j:a[i])res+=(j-'0');
  p[{a[i].size(),res}]++;
  pp[i]=res;
}
res=0;
 eps(i,1,n)
 {
  m=a[i].size();
  ll op=a[i].size()-1;
  ll k=0,ans=0;//偶数串一定一个长一个短
  eps(j,0,op)
  {
    k+=a[i][j]-'0';//默认他更长，后面出现更长的会补上去
  ans+=a[i][op-j]-'0';//反着的
  res+=p[{j+1-(op-j),k-(pp[i]-k)}];
  if(j!=op)
  res+=p[{j+1-(op-j),ans-(pp[i]-ans)}];
  }
 }
    cout<<res<<endl;
}

解释一下思路：

题目有一个很重要的细节就是：串最长也只有5，可以察觉到两个信息

1.可能可以直接直接分情况讨论 （5+5最长串也只有10的长度

2.可能可以循环枚举串

思考了一下，第一种情况是做不出的，因为有字符串切割的情况

所以我们可以枚举串的长度，

for(i 1---> n)//这里是长度的意思

假设当前左边或者右边是len的长度，我们的串溢出的部分就是len-i

这样这个题目的做法就显而易见了，map<pair<ll,ll>,ll>p先预处理所有串的长度和对应大小

后面枚举k前缀 ans后缀大小 分别计算溢出，再用也就知道的那一边剪掉溢出就是结果

注意：当长度等于len后，会出现重复计算，因为我们一开始是分为前缀和后缀的

我们的余缀为0时，整个串前后缀时重合的，所有不要计算