[POI 2010] ANT-Antisymmetry 题解

标签: #hash #二分
原题目: luogu-P3501
简要描述: hash求回文字符串

串的长度一定是偶数,反证法,如果是奇数,那么中间的数字取反后,倒过来后,还在中间的位置,那么和原来的符号是不相同的,比如原来是0,现在是1.

000  | 111
left | right

判定:

  • 如果left 取反后和right一样,这就表明right取反后一定和left一样
  • 如果left 取反后和right一样,那么就表明是回文的

 xxxx | xxxx
  xxx | xxx

如果[L,R] 是回文串,那么[L-1,R-1]也是回文串,所以这具有一种二分性. 我们可以把这个数量问题,转成求最长回文串的问题

这是一个基于你提供的 C++ 代码的详细题目解析。你的代码使用了 Hash + 二分答案 的方法来解决这个问题，时间复杂度为 O(Nlog⁡N)O(N \log N)。

1. 核心思路分析

什么是反对称字符串？

题目定义“反对称”字符串为：将 00 和 11 取反，再将整个串反转，得到的结果与原串相同。 这意味着：

  1. 字符串长度必须为 偶数。因为如果长度为奇数，中间的字符在反转后位置不变，它必须满足“取反后等于自己”（即 0=10=1 或 1=01=0），这显然是不可能的。
  2. 若字符串 SS 长度为 2k2k，中心在第 ii 个字符和第 i+1i+1 个字符之间，那么对于任意 1≤j≤k1 \le j \le k，左边的字符必须等于右边对应位置字符的取反。

转化问题

我们要寻找有多少个子串满足上述性质。 通常处理回文串（Palindrome）我们寻找 S[i]==S[n−i]S[i] == S[n-i]。这里我们需要寻找 S[i]==¬S[n−i]S[i] == \neg S[n-i]（¬\neg 表示取反）。

为了快速判断，我们可以构造一个辅助字符串 S2S2，它是原字符串 S1S1 的取反版本（即 S1S1 是 0 则 S2S2 是 1，反之亦然）。 那么，判断 S1S1 的某个子串是否“反对称”，就等价于判断： S1S1 的左半部分 是否等于 S2S2 对应右半部分的“反转”。

2. 代码实现细节解析

你的代码采用了 字符串哈希 (String Hash) 配合 二分答案 (Binary Search) 的策略。

(1) 预处理：构建哈希

代码中定义了两个哈希数组：

  • h1[] (前缀哈希): 维护原串 S1S1 的哈希值。
    • 计算方式：从左向右，H(S[1…i])H(S[1 \dots i])。
    • 用途：快速提取 S1S1 中任意一段子串的哈希值（正序）。
  • h2[] (后缀哈希): 维护取反串 S2S2 的哈希值。
    • 关键点：你的 h2 是从 NN 到 11 计算的（for(int i = n; i >= 1; --i)）。
    • 计算方式：h2[i]=h2[i+1]⋅P+s2[i]h2[i] = h2[i+1] \cdot P + s2[i]。这实际上是在计算 S2S2 反转后的前缀哈希。
    • 用途：hash_range_s2(l, r) 计算出的值，实际上代表了字符串片段 S2[l…r]S2[l \dots r] 反转后的哈希值。

巧妙之处： 通过比较 hash_range_s1(左半区间) 和 hash_range_s2(右半区间)，你实际上是在 O(1)O(1) 时间内检查：

S1 的左半边==?reverse(¬(S1 的右半边))S1 \text{ 的左半边} \stackrel{?}{==} \text{reverse}(\neg (S1 \text{ 的右半边}))
这完美契合反对称的定义。

(2) 枚举对称中心

由于反对称子串长度必为偶数，对称轴一定在两个字符之间。

  • 代码循环：for(int i = 1; i <= n-1; ++i)。
  • 这里 i 代表对称轴左侧的第一个字符的位置。即对称轴位于 i 和 i+1 之间。

(3) 二分答案 (Binary Search)

对于确定的对称中心（在 ii 和 i+1i+1 之间），我们需要找到最大的“半径” lenlen，使得向左延伸 lenlen 和向右延伸 lenlen 的部分构成反对称串。

  • 单调性：如果半径为 RR 的串是反对称的，那么半径为 R−1R-1 的串一定也是。满足单调性，可以使用二分。
  • 二分过程：
    • l = 1, r = maxlen + 1 (最大可能的半径)。
    • check(pos, mid)：检查以 pos 为左边界结束点，长度为 mid 的左半部分，是否匹配右半部分。
    • 如果 check 成功，说明半径 mid 可行，尝试更大的半径 (l = mid + 1)。
    • 否则，缩小半径。

(4) 统计答案

二分得到的返回值 tval 是以当前间隙为中心的最大反对称半径。

  • 例如，如果最大半径是 3，说明找到了长度为 2, 4, 6 的三个反对称子串。
  • 直接 ans += tval 即可。

3. 复杂度分析

  • 时间复杂度:

    • 预处理哈希：O(N)O(N)。
    • 枚举中心：O(N)O(N)。
    • 二分查找：每一次二分耗时 O(log⁡N)O(\log N)。
    • 总时间复杂度：O(Nlog⁡N)O(N \log N)。
    • 对于 N=500,000N = 500,000，这个复杂度完全可以接受（大约 10710^7 次运算量）。

  • 空间复杂度:

    • 使用了几个长度为 NN 的数组 (pp, s1, s2, h1, h2)，空间复杂度为 O(N)O(N)。

4. 总结与优化建议

你的代码逻辑清晰，写法标准，是解决此类回文/类回文问题的经典解法。

小知识：O(N) 的解法 这就好比回文串问题中，二分+哈希是 O(Nlog⁡N)O(N \log N)，而 Manacher 算法是 O(N)O(N)。 本题也可以使用 Manacher 算法 的变种来解决。

  • 只需修改 Manacher 中的匹配条件：原版是 while(s[i-k] == s[i+k])，改为 while(s[i-k] != s[i+k])（即左边等于右边的反）。
  • 注意 Manacher 通常要在字符间插入 # 处理奇偶长度，但本题只通过 # 作为中心即可，因为只关心偶数长度。

对你代码的一个微小注释：

cpp
copy 
        
1
2
3
4

        // 在计算 h2 时
for(int i = n;i >=1; --i)
    h2[i] = h2[i+1] * p + s2[i];

这段逻辑非常关键。如果不理解这里是“倒着算哈希”（模拟反转字符串），阅读代码的人可能会困惑为什么 check 函数里能直接比较 S1S1 的正向哈希和 S2S2 的这种哈希。这利用了数学上的性质：

Hash(S2[l…r]reversed)=∑k=lrS2[k]⋅Pk−lHash(S2[l \dots r]_{reversed}) = \sum_{k=l}^r S2[k] \cdot P^{k-l}
而你的 hash_range_s2 恰好计算的就是这个值。

一句话总结： 这是一道Manacher/回文串的变种题，你的代码巧妙地利用反串后缀哈希等价于原串反转哈希的性质，结合二分法，高效地（O(Nlog⁡N)O(N \log N)）解决了问题。

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

        #include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

const int maxn = 1e6+5;
ull ans;

int n;
const ull p = 131;
ull pp[maxn];
char s1[maxn]; // 原字符串
char s2[maxn]; // s1的反串
ull h1[maxn]; // s1的 前缀hash
ull h2[maxn]; // s2的 后缀hash

ull hash_range_s1(int l,int r) {
    return h1[r] - h1[l-1]* pp[r-l+1];
}

ull hash_range_s2(int l,int r) {
    return h2[l] - h2[r+1]* pp[r-l+1];
}


void init() {
    scanf("%d",&n);
    scanf("%s",s1+1);
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        s2[i] = (s1[i] == '0' ? '1' : '0');
    }

    // 求前缀hash
    for(int i = 1;i <= n ;++i ) // i: 1->n
        h1[i] = h1[i-1] * p + (s1[i]);

    for(int i = n;i >=1; --i)
        h2[i] = h2[i+1] * p + s2[i];

    pp[0] = 1;
    for(int i = 1;i <= n ;++i ) pp[i] = pp[i-1] * p;
}


bool check(int pos,int len) {
    ull t1 = hash_range_s1(pos-len+1, pos) ;
    ull t2 = hash_range_s2(pos+1, pos+1 + len -1);
    return t1 == t2;
}


int bin_search(int pos) {
    int maxlen = min(pos,n-pos);
    int l = 1 , r = maxlen+1;

    // 查找第一个失败的位置
    while( l < r ) {
        int mid = (l + r ) >> 1;

        if( !check(pos,mid) ) {
            r = mid;
        }
        else l = mid + 1;

    }
    return l - 1;
}



int main (int argc, char *argv[]) {
    init();

    // ull t1 = hash_range_s1(1, 2);
    // ull t2 = hash_range_s2(3, 4);
    // std::cout << t1 << "\n";
    // std::cout << t2 << "\n";

    // 枚举中间位置
    for(int i = 1;i <= n-1 ;++i ) // i: 1->n
    {
        int tval = bin_search(i);
        // printf("pos = %d ,ans = %d\n",i,tval);
        ans += tval;
    }
   
    printf("%lld",ans);
    return 0;
}