模考 T5 题解

题目:
screenshotnoscalea9d7e429-e0a7-4b88-85e3-c9114be6f5a2
题目简意:

给定两个包含 n 个的长度为 m 的字符串数组 sp,要从不同的三元组 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)

1 个赞