Antisymmetry（信息学奥赛一本通- P1462）

【题目描述】

【输入】

【输出】

【输入样例】

8 11001011

【输出样例】

7

【提示】

这道题目是经典的 POI（波兰信息学奥赛）真题。表面上是一个回文串的变种问题，但如果在考场上没有识破数据范围的陷阱，极容易写出正确但超时的 O(N^2) 暴力解，我第一次也是这么写的。

这篇文章将完整复盘这道题从“暴力枚举”到“二分降维”的进化过程，并拆解如何将红蓝边界二分法完美融入其中。

一、 题目分析

什么是“反对称”字符串？题目定义：将01串取反（0变1，1变0），再整体翻转，如果和原串一模一样，就是反对称。 翻译成数学语言就是，对于一个长度为 L 的子串，必须满足对于所有对应位置：S[左]!=S[右]（即互为相反数）。

核心破局点：奇数长度绝对不可能合法。只要看破了上面那个等式，你立刻就会发现一个物理规律：如果字符串长度是奇数，那么它最中间的那个字符，必须满足S[中]!=S[中]。这在现实宇宙中是不可能的。结论：所有的反对称子串，长度必然是偶数。它们的“对称中心”必定在两个字符的夹缝中。

二、 思考过程

既然对称中心在夹缝中，一个长度为N的字符串，一共有N−1个夹缝。

初级思维：枚举这N−1个夹缝作为中心点。从中心点开始，向左向右不断扩展半径 R，每次检查最外层的两个字符是否相反。只要相反就继续扩展，不相反就停下。 这就是解法一的思路。它的最坏时间复杂度是O(N^2)。当N=500,000时，计算量高达百亿级别，面对极限拉扯数据（如010101...）绝对会超时。

进阶思维：我们需要在扩展半径时砍掉无用的试探。单调性：如果一个夹缝向外扩展半径R（长度2R）是合法的反对称串，那么砍掉最外层，半径为R−1的串绝对也是合法的。只要状态呈现出[合法,合法,合法,不合法,不合法...]的绝对单调性，我们就可以直接上二分查找。用O(logN) 的跳跃探测，代替O(N) 的步步为营。

三、 算法设计

要让二分查找跑得快，每次验证“当前半径 R 是否合法”的操作必须是O(1) 的。这就需要请出我们的字符串哈希黑盒。

1. 处理“翻转+取反”的哈希比对：我们要对比“左半边取反”和“右半边翻转”。你可以建两个哈希数组：

   • ans2：把原串所有0和1颠倒，做一遍普通的从左到右前缀哈希。

   • ans1：不取反，但是从右往左扫一遍做哈希。这样你提取任意区间，它天然就是倒着读的。

   • 比对逻辑：半径为mid时，只要gethash2(左半边)==gethash1(右半边)，说明它完美反对称。

2. 红蓝边界二分法：使用while(l+1<r)的开闭区间模板。

   • l是蓝方阵营，维护已知合法的最大半径。初始为mi-1（即 0，绝对合法）。

   • r是红方阵营，维护已知越界的最小半径。初始为ma+1（绝对非法）。 当双方贴脸时，l就是我们要的最终最大合法半径。

四、 时空复杂度分析

• 空间复杂度：需要开几个长度为500,000 的unsigned long long数组存哈希值和次幂，内存占用约十几MB，O(N)。

• 时间复杂度：预处理哈希：O(N)

  • 枚举中心点+二分查找：N个中心点，每次二分最多切分约19次，哈希校验O(1)。计算量严格在10^7级别，O(NlogN)。一秒内AC。

五、 易错点总结

1. 爆int：500,000长度的字符串，最多可能有约个反对称子串，这个数字远超int极限的 21 亿。存储总答案的cnt必须开long long。

2. 越界读到\0：C++的string下标从0开始。如果要强行1-based建立哈希数组，取字符时必须老老实实写s[i-1]，如果写成s[i]，在末尾会读到隐藏的终止符\0，导致整个哈希值全盘崩溃。

3. 最大合法半径的木桶效应：向外扩展时，左边界和右边界哪边短，最大极限半径就受限于哪边。所以ma=min(i,n-i)，避免了下标越界的风险。

六、 完整代码

版本一：逻辑完美但会超时的暴力解 (O(N^2))

这份代码极其适合用来验证自己的哈希提取逻辑是否正确，但是信息学奥赛一本通会有一个测试点过不去

//这种做法会有一个测试点刚好1000ms然后超时。。。 //首先子串内字符个数不能为奇数，必为偶数 #include <iostream> using namespace std; typedef unsigned long long ull; int n; string s; ull ans1[500010];//存储s倒着进行的前缀哈希 ull ans2[500010];//存储s1的前缀哈希 ull p[500010];//存储131的i次方 long long cnt;//存储反对称子串个数 //计算ans1的闭区间[l,r]内的哈希值 但这个是要倒着算 ull gethash1(int l,int r){ if(l>r) return 0; return ans1[l]-ans1[r+1]*p[r-l+1]; } //计算ans2的闭区间[l,r]内哈希值 ull gethash2(int l,int r){ if(l>r) return 0; return ans2[r]-ans2[l-1]*p[r-l+1]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; cin>>s; //预处理131的i次方 p[0]=1; for(int i=1;i<=500005;i++) p[i]=p[i-1]*131; //先预处理出s倒着存储的前缀哈希 for(int i=n;i>=1;i--){ ans1[i]=ans1[i+1]*131+s[i-1]; } string s1=s; //然后把s1每一个字符都反转 for(int i=0;i<n;i++){ if(s1[i]=='0') s1[i]='1'; else s1[i]='0'; } //接下来计算s1的前缀哈希 for(int i=1;i<=n;i++){ ans2[i]=ans2[i-1]*131+s1[i-1]; } //接下来开始遍历所有子串(子串大小只能为偶数） for(int i=1;i<=n-1;i++){//子串左端点 for(int j=i+1;j<=n;j=j+2){//子串右端点 int mid=(i+j)/2; if(gethash2(i,mid)==gethash1(mid+1,j)) cnt++; } } cout<<cnt; return 0; }

版本二：哈希+红蓝边界二分查找 (严格O(NlogN))

抛弃双层for循环，采用枚举夹缝中心+二分猜测半径的方法。

//优化 枚举中心点 然后二分查找半径 //首先子串内字符个数不能为奇数，必为偶数 #include <iostream> using namespace std; typedef unsigned long long ull; int n; string s; ull ans1[500010];//存储s倒着进行的前缀哈希 ull ans2[500010];//存储s1的前缀哈希 ull p[500010];//存储131的i次方 long long cnt;//存储反对称子串个数 //计算ans1的闭区间[l,r]内的哈希值 但这个是要倒着算 ull gethash1(int l,int r){ if(l>r) return 0; return ans1[l]-ans1[r+1]*p[r-l+1]; } //计算ans2的闭区间[l,r]内哈希值 ull gethash2(int l,int r){ if(l>r) return 0; return ans2[r]-ans2[l-1]*p[r-l+1]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; cin>>s; //预处理131的i次方 p[0]=1; for(int i=1;i<=500005;i++) p[i]=p[i-1]*131; //先预处理出s倒着存储的前缀哈希 for(int i=n;i>=1;i--){ ans1[i]=ans1[i+1]*131+s[i-1]; } string s1=s; //然后把s1每一个字符都反转 for(int i=0;i<n;i++){ if(s1[i]=='0') s1[i]='1'; else s1[i]='0'; } //接下来计算s1的前缀哈希 for(int i=1;i<=n;i++){ ans2[i]=ans2[i-1]*131+s1[i-1]; } //接下来枚举所有可能的字符串中心点(i与i+1之间为中心点) for(int i=1;i<n;i++){ int bj=0;//存本轮最终半径 int mi=1;//字符串最小可能半径 //为了中心点左边右边长度相等且都不超过边界 //左边长度left=i-1+1 右边长度right=n-i //两者取min就是最大可能半径 int ma=min(i,n-i);//字符串最大可能半径 int l=mi-1,r=ma+1;//我的二分范围需要大于边界 int mid=0; while(l+1<r){ mid=(l+r)/2;//本轮所取半径 //如果这个半径情况下 左半边哈希值和右半边哈希值相等 //可以扩大半径 if(gethash2(i-mid+1,i)==gethash1(i+1,i+mid)){ l=mid; bj=max(bj,mid); } //如果这个半径情况下 左半边哈希值和右半边哈希值不等 //就要缩小半径 else{ r=mid; } } //这里直接cnt+=l也可以，因为我是红蓝二分 //但为了同学们看着更好理解 我还是开一个bj //我的l就代表符合条件的最大一个 //因为是从1开始的连续合法半径，最大半径的值即代表有几个合法子串 cnt+=bj; } cout<<cnt; return 0; }