对于一个字符串,如果将这个字符串取反后,再将整个串反过来和原串一样,就称作“反对称”字符串。比如就是反对称的,就不是。
现在给出一个长度为字符串,求它有多少个子串是反对称的。

第一行一个正整数。第二行一个长度为字符串。

一个正整数,表示反对称子串的个数。

8

11001011

7

个反对称子串分别是:(出现两次), (出现两次), ,

思路:第一眼看到这个题目毫无头绪,只会暴力判断,但是,仔细观察后,如果一个子串翻转后是一个回文串,那就代表这个子串是符合条件的,于是我们自然而然的就想到了算法。
考虑如何使用算法。
可以发现,原题的关键就是要使、'#'和'#'匹配('#'是要用的符合,视个人情况而定吧),而其他都不匹配。显然,使用异或操作是可行的,但是这样'#'的值就不好定义,因为无论'#'定义成什么,('#')^('#')=0。
考虑算法更新(回文半径)是如何更新的,就是能扩展的就扩展,分类讨论一下,然后在这个题目当中只要匹配就可以了,那我们暴力扩展的时候直接判一下就可以了。
另外,在的时候,可以只考虑偶数位字符,因为奇数个字符组成的子串不可能反对称。

然后这个题就做完了。。

当然这个题目不只可以用,还可以二分+哈希搞一下,这里就不展开说了,有兴趣的同学
可以 上网搜一下(自己想一下),我才不会说是因为我不会呢。。。

剩下的是我简洁(逃……)的代码:

#include<cstdio>
#include<algorithm>
#define int long long
#define maxn 1000007
using namespace std;
char s[maxn>>1],str[maxn];
int n,p[maxn],ans;
int init() {
  str[0]='@',str[1]='#';
  int p=1;
  for(int i=1;i<=n;++i) str[++p]=s[i],str[++p]='#';
  str[p+1]='@';
  return p;
}
void Manacher() {
  int maxx=0,id=0,len=init();
  for(int i=1;i<=len;++++i) {
    if(i<maxx) p[i]=min(maxx-i,p[id*2-i]);
    else p[i]=1;
    while((str[i+p[i]]=='#'&&str[i-p[i]]=='#')||(str[i+p[i]]-'0'+str[i-p[i]]-'0'==1)) ++p[i];
    if(maxx<i+p[i]) maxx=i+p[i],id=i;
  }
}
signed main() {
  scanf("%d%s",&n,s+1);
  Manacher();
  n<<=1;
  ++n;
  for(int i=1;i<=n;++++i) ans+=p[i]>>1;
  printf("%lld\n",ans);
  return 0;
}