[SOJ 1107] 牲口棚的安全

了解 C++ STL的全排列函数

首先, 对于全排列算法, C++ STL提供了next_permutation(begin, end)函数, 使用该函数可以按字典序来获得全排列中的下一个排列.
只需要循环调用该函数, 即可获得所有的全排列情况

注意: next_permutation()函数对支持迭代器的容器均使用, 可以直接用于string类, 也可以用于 数组(需传入指针).

读读题目, 了解需求

根据题目要求, 需要我们用一组字母按组成符合条件的密码

可以得出以下信息:

(条件1) 有效的密码 均由 小写字母组成
(条件2) 有效的密码 至少包含1个元音字母 + 至少包含2个辅音字母
(条件3) 有效的密码 必须符合 字典序
(条件4) 一组字母 里的字母不可以被重复使用.
(条件5) 最终的输出结果列表, 也要求按字典序输出.
(条件6) 密码要求L位数

考虑到最终的输出结果也必须要按字典序输出这个条件, 我们不妨直接在 算法阶段 就按字典序来进行密码构造,这样就方便很多了。(其实这个 按字典序输出 有些暗示的意义了, 大概知道这里需要进行全排列.)

放宽条件: 获得”全部的密码列表”

对于条件1,很容易进行满足,我们只需要保证输入和算法处理时,都使用小写字母即可(不要用大写字母和小写字母混杂,否则字典序处理会引入新的麻烦)

对于条件3,我们可以在构造密码阶段就按字典序来构造,也就是使用我们上面所说的next_permutation()函数, 因为这个全排列算法是按字典序来进行排列的。在构造密码时就满足条件3的话,自然条件5也就满足了。

结合条件3条件4,我们将使用一串字母来构造字符串,然后对这个字符串进行按字典序排列得到基础字符串

如: 一串字母"a t c i s w"可以构造字符串"atcisw",然后对该字符串进行按字典序排列可得到基础字符串acistw,接下来,我们只需要对基础字符串运行next_permutation()函数即可得到由这一串字母按字典序排列的所有可能的密码

据此,到这一步,我们获得的密码列表中,并非所有的密码都是有效的密码
但是,我们可以肯定,有效的密码列表全部的密码列表的1个子集,且由于全部的密码列表里的密码是按字典序列出的,所以,我们只需要对全部的密码列表过滤掉一些无效的密码,即可获得有效的密码列表
这个有效的密码列表也就是最终的答案了。

限制条件: 过滤”全部的密码列表”得”有效的密码列表”

根据条件6, 要求密码的长度为指定的L位, 我们只需要对密码进行截短即可得到L位长度的密码

然后再根据条件2,我们可以编写1个简单的 判断函数,在全部的密码列表中剔除掉这些 元音和辅音字母不满足的密码

到这一步,我们已经得到了有效的密码列表了,
只需要按顺序输出该列表里的所有密码即可

注意:在输出有效的密码列表时,要注意重复的字符串的问题,因为我们之前进行截短字符串,导致可能的字符串重复,对于重复字符串,只需要输出1次即可。(需要稍微记录下,哪些字符串重复过,以便在输出时进行判断。)

回顾流程

在整个题目中,虽然要求我们构造 满足多个条件限制的密码。
但是,我们人为地放宽了条件,以此来得到最终答案超集
紧接着,我们再引入条件,来获得最终答案

总体流程:
根据一组字母 -> 构造基础字符串 -> 对基础字符串运行next_permutation()获得全部的密码列表(已按字典序排列) -> 在全部的密码列表截短密码 -> 在全部的密码列表中过滤掉不符合元音辅音字母要求的密码 -> 按顺序输出全部的密码列表里的密码 (去重输出)

CODE

需include stdio.h, stdlib.h, algorithm, vector, set, map, string, iostream
#pragma warning (disable:4996)

using namespace std;

bool limitC(string psw) {
    int vowelCnt = 0;
    int consonantCnt = 0;

    for (int i = 0; i < psw.size(); i++) {

        if (psw[i] == 'a' || psw[i] == 'e' || psw[i] == 'i' || psw[i] == 'o'
            || psw[i] == 'u') {
            vowelCnt++;
        }
        else {
            consonantCnt++;
        }

    }

    return vowelCnt >= 1 && consonantCnt >= 2 ? true : false;
}

int main() {

    int L, C;
    scanf("%d %d", &L, &C);

    /* 构造字母表 */
    set letters;
    for (int i = 0; i < C; ) {
        char ch;
        cin >> ch;
        letters.insert(ch);
        i++;
    }

    /* 构造BasePsw. */
    string basePsw;
    for (set::iterator iter = letters.begin(); iter != letters.end(); iter++) {
        basePsw += *iter;
    }
    sort(basePsw.begin(), basePsw.end());
    //printf("获得基础字符串: %s\n", basePsw.c_str());

    /* 获取按字典序全排列的密码列表. */
    // 去重记录
    map used;
    while (next_permutation(basePsw.begin(), basePsw.end())) {

        // 截取: 将密码截取为指定L位.
        string temp = string(basePsw, 0, L);

        // 过滤: 元音和辅音字母不满足条件的密码.
        if (!limitC(temp)) continue;

        // 字典序: 对密码进行字典序排列.
        sort(temp.begin(), temp.end());

        // 去重记录: 以便输出时进行判断.
        if (used[temp] == false) {
            puts(temp.c_str());
        }
        used[temp] = true;
    }

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

> 表情包