bzoj2084:[POI2010]ANT-Antisymmetry_综合

2084: [Poi2010]Antisymmetry

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 982 Solved: 613
[Submit][Status][Discuss]

Description

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

Input

第一行一个正整数N (N <= 500,000)。第二行一个长度为N的01字符串。

Output

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

Sample Input

8
11001011

Sample Output

7

hint
7个反对称子串分别是：01(出现两次), 10(出现两次), 0101, 1100和001011

回文串的本质就是对称关系

所以改改Manacher就可以用了

有一些小性质要注意，比如本题不可能有奇回文串(中间那位取反一定不等)，所以在分割符上统计就行了(我用的#)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>const int MAXN = 1500100;
char s1[MAXN], s2[MAXN];
int len1, len2, p[MAXN];inline bool check(char i, char j) {if(((i - '0') ^ (j - '0')) == 1) return 1;if(i == '#' && j == '#') return 1;return 0;
}inline void init() {len1 = (int)strlen(s1);s2[0] = '♂';s2[1] = '#';for(int i = 0; i < len1; i++) {s2[(i << 1) + 2] = s1[i];s2[(i << 1) + 3] = '#';}len2 = (len1 << 1) + 2;s2[len2] = '♂';
}inline long long calc() {long long ans = 0; for(int i = 1; i < len2; i += 2) ans += (long long)(p[i] >> 1); return ans;
}inline void manacher() {int id = 0, mx = 0;for(int i = 1 ; i < len2; i += 2) {if(mx > i) p[i] = std::min(mx - i, p[2 * id - i]);else p[i] = 1;while(check(s2[i + p[i]], s2[i - p[i]])) p[i]++;if(i + p[i] > mx) {mx = i + p[i];id = i;}}printf("%lld\n", calc());
}int n;
signed main() {scanf("%d", &n); scanf("%s", s1);init(), manacher();return 0;
}