题解 P6873 [COCI2013-2014#6] FONT

link

题意

给你 \(N\) 个单词，问最多能组成多少个包含所有小写英文字母的句子。

\(\mathrm{Solution}\)

\(N \le 25\) 显然搜索。

枚举当前选还是不选，搜到头判断是否成功即可。

\(\mathrm{Code}\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 26;

int n;
int ans = 0;
int a[N];

void dfs(int pos, int flg) {
    if (pos == n) {
        if (flg == (1 << 26) - 1) ++ ans;
        return ;
    }
    dfs(pos + 1, flg);
    dfs(pos + 1, flg | a[pos]);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s; cin >> s;
        int len = s.size();
        for (int j = 0; j < len; ++j) a[i] |= (1 << (int)(s[j] - 'a'));
    }
    dfs(0, 0);
    cout << ans;
    return 0;
}