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

【题目描述】对于一个01字符串如果将这个字符串0和1取反后再将整个串反过来和原串一样就称作“反对称”字符串。比如00001111和010101就是反对称的1001就不是。现在给出一个长度为N的01字符串求它有多少个子串是反对称的。【输入】第一行一个正整数N (N ≤ 500,000)。第二行一个长度为N的01字符串。【输出】一个正整数表示反对称子串的个数。【输入样例】8 11001011【输出样例】7【提示】7个反对称子串分别是01(出现两次), 10(出现两次), 0101, 1100和001011这道题目是经典的 POI波兰信息学奥赛真题。表面上是一个回文串的变种问题但如果在考场上没有识破数据范围的陷阱极容易写出正确但超时的 O(N^2) 暴力解我第一次也是这么写的。这篇文章将完整复盘这道题从“暴力枚举”到“二分降维”的进化过程并拆解如何将红蓝边界二分法完美融入其中。一、 题目分析什么是“反对称”字符串题目定义将01串取反0变11变0再整体翻转如果和原串一模一样就是反对称。 翻译成数学语言就是对于一个长度为 L 的子串必须满足对于所有对应位置S[左]!S[右]即互为相反数。核心破局点奇数长度绝对不可能合法。只要看破了上面那个等式你立刻就会发现一个物理规律如果字符串长度是奇数那么它最中间的那个字符必须满足S[中]!S[中]。这在现实宇宙中是不可能的。结论所有的反对称子串长度必然是偶数。它们的“对称中心”必定在两个字符的夹缝中。二、 思考过程既然对称中心在夹缝中一个长度为N的字符串一共有N−1个夹缝。初级思维枚举这N−1个夹缝作为中心点。从中心点开始向左向右不断扩展半径 R每次检查最外层的两个字符是否相反。只要相反就继续扩展不相反就停下。 这就是解法一的思路。它的最坏时间复杂度是O(N^2)。当N500,000时计算量高达百亿级别面对极限拉扯数据如010101...绝对会超时。进阶思维我们需要在扩展半径时砍掉无用的试探。单调性如果一个夹缝向外扩展半径R长度2R是合法的反对称串那么砍掉最外层半径为R−1的串绝对也是合法的。只要状态呈现出[合法,合法,合法,不合法,不合法...]的绝对单调性我们就可以直接上二分查找。用O(logN) 的跳跃探测代替O(N) 的步步为营。三、 算法设计要让二分查找跑得快每次验证“当前半径 R 是否合法”的操作必须是O(1) 的。这就需要请出我们的字符串哈希黑盒。处理“翻转取反”的哈希比对我们要对比“左半边取反”和“右半边翻转”。你可以建两个哈希数组ans2把原串所有0和1颠倒做一遍普通的从左到右前缀哈希。ans1不取反但是从右往左扫一遍做哈希。这样你提取任意区间它天然就是倒着读的。比对逻辑半径为mid时只要gethash2(左半边)gethash1(右半边)说明它完美反对称。红蓝边界二分法使用while(l1r)的开闭区间模板。l是蓝方阵营维护已知合法的最大半径。初始为mi-1即 0绝对合法。r是红方阵营维护已知越界的最小半径。初始为ma1绝对非法。 当双方贴脸时l就是我们要的最终最大合法半径。四、 时空复杂度分析空间复杂度需要开几个长度为500,000 的unsigned long long数组存哈希值和次幂内存占用约十几MBO(N)。时间复杂度预处理哈希O(N)枚举中心点二分查找N个中心点每次二分最多切分约19次哈希校验O(1)。计算量严格在10^7级别O(NlogN)。一秒内AC。五、 易错点总结爆int500,000长度的字符串最多可能有约个反对称子串这个数字远超int极限的 21 亿。存储总答案的cnt必须开long long。越界读到\0C的string下标从0开始。如果要强行1-based建立哈希数组取字符时必须老老实实写s[i-1]如果写成s[i]在末尾会读到隐藏的终止符\0导致整个哈希值全盘崩溃。最大合法半径的木桶效应向外扩展时左边界和右边界哪边短最大极限半径就受限于哪边。所以mamin(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(lr) return 0; return ans1[l]-ans1[r1]*p[r-l1]; } //计算ans2的闭区间[l,r]内哈希值 ull gethash2(int l,int r){ if(lr) return 0; return ans2[r]-ans2[l-1]*p[r-l1]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; cins; //预处理131的i次方 p[0]1; for(int i1;i500005;i) p[i]p[i-1]*131; //先预处理出s倒着存储的前缀哈希 for(int in;i1;i--){ ans1[i]ans1[i1]*131s[i-1]; } string s1s; //然后把s1每一个字符都反转 for(int i0;in;i){ if(s1[i]0) s1[i]1; else s1[i]0; } //接下来计算s1的前缀哈希 for(int i1;in;i){ ans2[i]ans2[i-1]*131s1[i-1]; } //接下来开始遍历所有子串(子串大小只能为偶数 for(int i1;in-1;i){//子串左端点 for(int ji1;jn;jj2){//子串右端点 int mid(ij)/2; if(gethash2(i,mid)gethash1(mid1,j)) cnt; } } coutcnt; 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(lr) return 0; return ans1[l]-ans1[r1]*p[r-l1]; } //计算ans2的闭区间[l,r]内哈希值 ull gethash2(int l,int r){ if(lr) return 0; return ans2[r]-ans2[l-1]*p[r-l1]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; cins; //预处理131的i次方 p[0]1; for(int i1;i500005;i) p[i]p[i-1]*131; //先预处理出s倒着存储的前缀哈希 for(int in;i1;i--){ ans1[i]ans1[i1]*131s[i-1]; } string s1s; //然后把s1每一个字符都反转 for(int i0;in;i){ if(s1[i]0) s1[i]1; else s1[i]0; } //接下来计算s1的前缀哈希 for(int i1;in;i){ ans2[i]ans2[i-1]*131s1[i-1]; } //接下来枚举所有可能的字符串中心点(i与i1之间为中心点) for(int i1;in;i){ int bj0;//存本轮最终半径 int mi1;//字符串最小可能半径 //为了中心点左边右边长度相等且都不超过边界 //左边长度lefti-11 右边长度rightn-i //两者取min就是最大可能半径 int mamin(i,n-i);//字符串最大可能半径 int lmi-1,rma1;//我的二分范围需要大于边界 int mid0; while(l1r){ mid(lr)/2;//本轮所取半径 //如果这个半径情况下 左半边哈希值和右半边哈希值相等 //可以扩大半径 if(gethash2(i-mid1,i)gethash1(i1,imid)){ lmid; bjmax(bj,mid); } //如果这个半径情况下 左半边哈希值和右半边哈希值不等 //就要缩小半径 else{ rmid; } } //这里直接cntl也可以因为我是红蓝二分 //但为了同学们看着更好理解 我还是开一个bj //我的l就代表符合条件的最大一个 //因为是从1开始的连续合法半径最大半径的值即代表有几个合法子串 cntbj; } coutcnt; return 0; }