题目:
题目简意:
给定两个包含 n 个的长度为 m 的字符串数组 s 和 p,要从不同的三元组 pos_1,pos_2,pos_3,使得对于 s 数组中任何一个字符串取第 pos_1,pos_2,pos_3 位均与 p 中的不同。请你求出满足要求的三元组的个数。
分析:
注意到数据范围很小,故在比赛的时候,可以考虑复杂度较高的算法,而不要将大量时间花费在想低复杂度算法。
实现步骤:
既然是求三元组可以考虑三重循环,枚举所有的三元组,并且判断是否满足条件,很简单,最重要的是如何写判断函数。
其实判断函数也很简单,我们先便利 s 求出给定在给定的三个位置能组成的所有三元组,再遍历 p 看看有没有重复即可。
代码:
只放判断函数了。
bool check(int pos1,int pos2,int pos3){
unordered_set<string>sc;//用于记录所有在 s 中的三元组
for(int o=0;o<n;o++){
/*计入所有 s 的三元组*/
string c="";
c+=s[o][pos1];
c+=s[o][pos2];
c+=s[o][pos3];
sc.insert(c);
}
for(int o=0;o<n;o++){
/*计入 p 的三元组,与 s 的方法一致*/
if(/*如果在 s 中出现过*/)return 0;
}
return 1;
}
复杂度:
时间复杂度为 O(n\times m^3)。