这里是人肉爬虫114514号awa,这是我爬出的第3个题目,以下是由生物计算机(已迭代20次)生成的内容:

我的天啊，终于让我遇到水题了！！上一道KMP+DP花了我四个小时啊啊啊啊啊啊啊啊啊啊啊啊！！！

水题就不多说了，直接上代码了。

（好像不那么水?） 知识点（我之前居然想要在这里解释）

• Manacher 算法 https://www.bilibili.com/video/BV1Sx4y1k7jG
• // 马拉车算法核心
• //对于每一个点：
• //1检查是否在大蘑菇内,如果是，P[i]=min(P[2*C-i],r-i)
• //2能不能再长。如果i+P[i]+1与i-P[i]-1所对应的值相等,P[i]++
• //3是不是成为了新的大蘑菇。如果i+P[i]>r,则更新r=i+P[i],c=i;

题解(复制到编译器里看)

#include <bits/stdc++.h>
#define N 500010
#define int long long
using namespace std;

int n;
string s;
int hw[2 * N];  // 回文半径数组
//反对称子串的特性：
//1.必须是偶数长度
//2.满足 s[i+k] = 1 - s[j-k] 对于所有 k
void manacher()
{
    // 初始化
    int mid = 0, maxright = 0;
    
    for (int i = 1; i <= n * 2; i++) 
	{
        if (i < maxright)//在蘑菇里面 
		{
            hw[i] = min(hw[2 * mid - i], maxright - i);//看过视频的都知道 
        } 
		else
		{
            hw[i] = 1;//蘑菇外面,先设置它为1 
        }
        
        // 马拉车算法扩展，检查反对称条件,之前是“正”对称，半径增长的条件是left和right相等；现在是"反"对称，要满足if里的条件。 
        while (i - hw[i] > 0 && i + hw[i] <= n * 2 + 1) 
		{
            char left = s[i - hw[i]];
            char right = s[i + hw[i]];
            
            // 反对称条件：0-1 或 1-0 配对，或者都是分隔符
            if ((left == '0' && right == '1') || 
                (left == '1' && right == '0') ||
                (left == '#' && right == '#')) 
			{
                hw[i]++;
            } 
			else
			{
                break;
            }
        }
        
        if (i + hw[i] > maxright)//新大蘑菇 
		{
            maxright = i + hw[i];
            mid = i;
        }
        
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    cin >> s;
    
    // 构造插入分隔符的字符串
    string t = "#";
    for (int i = 0; i < n; i++) 
	{
        t.push_back(s[i]);
        t.push_back('#');
    }
    
    s = t;
    n = s.length() - 1;
    
    manacher();
    
    int ans = 0;
    // 只统计偶数长度的反对称子串
    for (int i = 1; i <= n; i++) 
	{
        if (s[i] == '#')
		{
            // 以分隔符为中心，找到的半径对应偶数长度子串
            //#0#0#1#1# 中心是'#',hw[5]=4有两个反对称子串 0011和01 
            ans += hw[i] / 2;
            
        }
    }
    
    cout << ans << endl;
    return 0;
}