SOJ 1035 DNA matching

题目大意：输入t，代表t组测试样例。每组测试样例先输入n，接着输入n条以'A', 'T' , 'C', 'G'组成的串。'A'能匹配'T','G'能匹配'C'。串匹配是指两条串对应位置满足A/T或者G/C匹配。计算每组输入样例中能匹配成双螺旋结构的DNA链的数目。

解题思路：所有链两两比较，O(n²*串的长度)复杂度算法。小处理：用used数组记录串的状态，判断是否已经被匹配，如果已经被匹配，则不重复匹配。

代码如下：

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

string transform(string strand) {
    for (int i = 0; i < strand.length(); i++) {
        if (strand[i] == 'T') {
            strand[i] = 'A';
        } else if (strand[i] == 'A') {
            strand[i] = 'T';
        } else if (strand[i] == 'G') {
            strand[i] = 'C';
        } else if (strand[i] == 'C') {
            strand[i] = 'G';
        }
    }

    return strand;
}

int main() {
    int t, n;
    const int maxn = 105;
    string strands[maxn];
    bool used[maxn];
    cin >> t;
    while (t--) {
        memset(used, false, sizeof used);

        cin >> n;

        // 读入strand
        for (int i = 0; i < n; i++) {
            cin >> strands[i];
        }

        int ans = 0;
        // 处理数据
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            // cout << strands[i] << endl;
            string strand = transform(strands[i]);
            // cout << strand << endl;
            for (int j = 0; j < n; j++) {
                if (used[j]) continue;
                if (strand == strands[j]) {
                    used[i] = true;
                    used[j] = true;
                    ans++;
                    break;
                }
            }
            //used[i] = true;
        }

        cout << ans << endl;
    }
    return 0;
}