题目描述

小蓝要用七段码数码管来表示一种特殊的文字。

图片描述

上图给出了七段码数码管的一个图示，数码管中一共有 77 段可以发光的二 极管，分别标记为 a, b, c, d, e, f, ga,b,c,d,e,f,g。

小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。

例如：bb 发光，其他二极管不发光可以用来表达一种字符。

例如 cc 发光，其他二极管不发光可以用来表达一种字符。这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。

例如：a, b, c, d, ea,b,c,d,e 发光，f, gf,g 不发光可以用来表达一种字符。

例如：b, fb,f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符？

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

答案 ：80；
dfs或者二进制枚举每一种可能，用并查集判联通

时间复杂度

参考文献

C++ 代码

#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <map>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

const int maxn = 3001;
const int INF = 0x3f3f3f3f;
const int mod=1000000007;

int fa[maxn];
int find(int x) {//查询+路径压缩 找根节点并将沿途每个结点的父节点都设为根节点
    return x == fa[x]? x : (fa[x] = find(fa[x]));
}
inline void merge(int a, int b) {
    fa[find(a)] = find(b);
}
bool use[10];
int sum;
int mp[100][100];

void init()
{
    mp[1][2]=mp[2][1]=1;
    mp[1][6]=mp[6][1]=1;
    mp[2][7]=mp[7][2]=1;
    mp[5][7]=mp[7][5]=1;
    mp[4][5]=mp[5][4]=1;
    mp[3][4]=mp[4][3]=1;
    mp[2][3]=mp[3][2]=1;
    mp[5][6]=mp[6][5]=1;
    mp[3][7]=mp[7][3]=1;
    mp[7][6]=mp[6][7]=1;
//  mp[5][7]=mp[7][5]=1;
}
void dfs(int k)
{
    if(k>7)
    {
        for(int i=1;i<=7;i++)
        {
            fa[i]=i;
        }
        for(int i=1;i<=7;i++)
        {
            for(int j=1;j<=7;j++)
            {
                if(mp[i][j]&&use[i]&&use[j])
                {
                     merge(i,j);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=7;i++)
        {
            if(fa[i]==i&&use[i]) ans++;
        }
        if(ans==1) sum++;
        return ;
    }
    use[k]=1;
    dfs(k+1);
    use[k]=0;
    dfs(k+1);
} 
int main()
{
    init();
    dfs(1);
    cout << sum;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla