CF1287B 题解

· · 题解

题意

给出 n 个仅包含字母 “\text{S}”、“\text{E}”、“\text{T}” 且长度为 k 的字符串，求出有多少种方式可以使这三个字符串的该特征（字母）要么全部相同，要么两两不同。

解答

通过观察样例可以发现，如果已知两张卡片那么最后一张卡片有且仅有一张。

证明，两个字符串按照每个字符一一对应，那么第三个字符串中的字符仅有两种情况（要么全部相同，要么两两不同）：

  1. 若两个字符相同，那么第三个字符肯定与前两个字符一样。（全部相同）
  2. 若两个字符不同，那么第三个字符仅可能是“\text{S}”、“\text{E}”、“\text{T}” 中除那两个字符的剩下一个字符。（两两不同）

例如，两个字符串分别为为 \text{SETT} 和 \text{TEST}。 设 i 为字符串的下标，则：

故最后一个字符串是 \text{EEET}，是唯一的。

那么我们用一个 \text{map} 统计每个字符串出现的次数，之后只需要枚举两个字符串 i，j。 计算出它们需要组成一个 set 的另一个字符串，查看在 \text{map} 中出现了几次，计入答案。

这样计算会出现问题，我们会重复计算答案，怎么处理呢？

代码

#include<bits/stdc++.h>
using namespace std;

unordered_map<string, int> mp;
string s[1505];

// 找到除两个字母以外的剩下一个字母
char check(char a, char b)
{
    bool t[10] = {0};
    char x[5] = {'S', 'E', 'T'};
    for(int i=0; i<=2; i++)
        if(a == x[i] || b == x[i]) t[i] = 1;

    for(int i=0; i<=2; i++)
        if(t[i] == 0) return x[i];
}

int main()
{
    int n, k; cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> s[i], mp[s[i]]++;

    int ans = 0;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
        {
            string a = s[i], b = s[j], c = "";
            for(int l=0; l<k; l++)
                if(a[l] == b[l]) c += a[l]; // 全部相同
                else c += check(a[l], b[l]); // 两两不同

            ans += mp[c];
            // 解决重复计算的问题 1
            if(a == c) ans --; 
            if(b == c) ans --;
        }
    // 解决重复计算的问题 2
    cout << ans / 3 << endl;
    return 0;
}