[ARC104B] DNA Sequence 题解

题意

对于一个只含有 A，C，T，G 的字符串 \(s\), 定义其为匹配的当且仅当其中 A 的数量和 T 的数量相等，C 的数量和 G 的数量相等。

给定一个长度为 \(N\) 的字符串 \(S\)，求其有多少个非空子串是匹配的。

\(1 \le N \le 5000\)。

题解

\(\mathcal{O}(N)\) 做法。

首先考虑如果字符集只有 A 和 T 的情况，发现可以维护当前状态下 A 的数量与 T 的数量的差值，发现其值相等的两个端点形成的子串是符合要求的。

那么考虑字符集为 A，C，T，G 的情况，维护维护当前状态下 A 的数量与 T 的数量的差值，以及 C 的数量与 G 的数量的差值即可，将两个数 \(\tt{hash}\) 一下就做完了，使用哈希表存储的话单次修改和查询复杂度均为 \(\mathcal{O}(N)\)，总复杂度为 \(\mathcal{O}(N)\)。

Code

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::unordered_map<valueType, valueType> ValueMap;

ValueVector table;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    table.resize(256);
    table['A'] = 6007;
    table['T'] = -(6007);
    table['C'] = 7001;
    table['G'] = -(7001);

    valueType N;

    std::cin >> N;

    ValueMap count;
    valueType ans = 0, sum = 0;

    count.reserve(N);

    count[0] = 1;
    for (valueType i = 1; i <= N; ++i) {
        char c;

        std::cin >> c;

        sum += table[c];

        ans += count[sum];

        ++count[sum];
    }

    std::cout << ans << std::endl;
}