$\operatorname{谷仓的安保}$

题目链接：$SSL比赛\ 1374$

题目

Farmer John 给谷仓安装了一个新的安全系统，并且要给牛群中的每一个奶牛分配一个有效的密码。一个有效的密码由 $L(3 <= L <= 15)$ 个小写字母 $($ 来自传统的拉丁字母集 $'a'...'z')$ 组成，至少有一个元音 $('a',\ 'e',\ 'i',\ 'o',$ 或 $'u')$ 和两个辅音(除去元音以外的音节)，并且是按字母表顺序出现的(例如， $'abc'$ 是有效的，而 $'bac'$ 不是) 。
给定一个期望长度 $L$ 和 $C$ 个小写字母，写一个程序，打印出所有的长度为 $L$ 、能由这给定的 $C$ 个字母组成的有效密码。密码必须按字母表顺序打印出来，一行一个。
你的程序只需输出前 $25,000$ 个有效密码，即使后面还存在有效密码。

输入

第一行： 两个由空格分开的整数， $L$ 和 $C$ ;
第二行： $C$ 个空格分开的小写字母，密码是由这个字母集中的字母来构建的。

输出

第一至 $?$ 行: 每一个输出行包括一个长度为 $L$ 个字符的密码(没有空格)。输出
行必须按照字母顺序排列。如果存在多于 $25,000$ 个有效密码，你的程序必须在输出 $25,000$ 个有效密码后停止。

样例输入

4 6
a t c i s w

样例输出

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

思路

这道题就爆搜。

把读入的字母排序，然后枚举每一种选法，如果元音数量和辅音数量都足够就输出，如果输出了 $25000$ 次就直接结束程序。

（因为最多只输出 $25000$ 个，所以可以直接爆搜）

代码

#include<cstdio>
#include<algorithm>using namespace std;int n, m, a[27], time, yuan;
char c[27];
bool in[27];char readchar() {char ch = getchar();while (ch < 'a' || ch > 'z') ch = getchar();return ch;
} bool ch() {//判断有没有足够的元音和辅音yuan = 0;for (int i = 1; i <= n; i++)if (c[a[i]] == 'a' || c[a[i]] == 'e' || c[a[i]] == 'i' || c[a[i]] == 'o' || c[a[i]] == 'u')yuan++;if (yuan >= 1 && n - yuan >= 2)return 1;return 0;
}void dfs(int now, int las) {//遍历每一种密码if (now > n) {if (ch()) {for (int i = 1; i <= n; i++)putchar(c[a[i]]);putchar('\n');time++;if (time == 25000) exit(0);//只输出25000个}return ;}for (int i = las + 1; i <= m - (n - now); i++) {in[i] = 1;a[now] = i;dfs(now + 1, i);in[i] = 0;a[now] = 0;}
}int main() {scanf("%d %d", &n, &m);//输入for (int i = 1; i <= m; i++)c[i] = readchar();//读入sort(c + 1, c + m + 1);//从小到大排序dfs(1, 0);//遍历密码return 0;
}