CF1287B 题解

题意

给出

n

个仅包含字母 “

\text{S}

”、“

\text{E}

”、“

\text{T}

” 且长度为

k

的字符串，求出有多少种方式可以使这三个字符串的该特征（字母）要么全部相同，要么两两不同。

解答

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

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

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

例如，两个字符串分别为为

\text{SETT}

和

\text{TEST}

。设

i

为字符串的下标，则：

当 $i=0$ ，答案是除 $\text{S}$ 和 $\text{T}$ 的另外一个字符，即 $\text{E}$ ；
当 $i=1$ ，两个字符都是 $\text{E}$ ，因此答案是 $\text{E}$ ；
当 $i=2$ ，答案是除 $\text{S}$ 和 $\text{T}$ 的另外一个字符，即 $\text{E}$ ；
当 $i=3$ ，两个字符都是 $\text{T}$ ，因此答案是 $\text{T}$ 。

故最后一个字符串是

\text{EEET}

，是唯一的。

那么我们用一个

\text{map}

统计每个字符串出现的次数，之后只需要枚举两个字符串

i

，

j

。计算出它们需要组成一个 set 的另一个字符串，查看在

\text{map}

中出现了几次，计入答案。

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

问题1：我们计算出的第三个字符串可能与前两个就是同一个字符串。

解答：不需要计入这个答案，将 ans--。
问题2：假设有三张卡片 A、B、C 能组成一个 set。在双重循环遍历每一张卡牌中，这个 set 会被计数 $3$ 次：
- 当 set 的前两张卡牌为 $(A, B)$ 时，推导出的第三张卡片是 $C$ ；
- 当 set 的前两张卡牌为 $(A, C)$ 时，推导出的第三张卡片是 $B$ ；
- 当 set 的前两张卡牌为 $(B, C)$ 时，推导出的第三张卡片是 $A$ 。
解答：每个合法的 set 都会被计数 $3$ 次，所以最后只需要除以 $3$ 来消除重复计数。

代码

CPP

#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;
}

文章操作

题意

解答

相关推荐

评论

CF1287B 题解