首先明确可能今晚这CF不适合图论选手,我应该倒着做的这个题没时间了...赛后wa了两发过了。

真是午夜掉分场

首先题意很明确了,两个字符串有相同字母,那么这两个字符串等效,注意!等效是可以传递的。

题目思路:

首先并查集绝对可以想得到,但是并查集怎么维护需要想一想。

想最少的字符串,绝对找根节点,那么枚举根节点建图是不可能的了。

我们可以考虑每个字母的贡献。

即 串:abcd  则a可以控制b,a可以控制c

串:bcd ,则b可以控制c与d.那么连起来 ,a也可以控制d

所以只需要找一下,一个字母可以控制到的最多的字符串就可以,即枚举每个字母作为根,然后我们选一下,假设abcd被a控制,

efg被e控制,hi被h控制,那么我只需要选择三个带有 a,e,h的就可以控制所有字符串。

这时一个疑问:如果 有一个字符串 都有a和e那么是不是就多选了一个?答案是不可能的

如果有一个字符串都有 a,e那么e就被a控制了,fg也会被a控制(并查集的性质),所以根据这个性质,枚举一遍并查集即可。

看有多少个根,但是前提是 这个字母必须要出现过。然后代码:

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#include <queue>
typedef long long ll;
typedef unsigned long long ull;
const int mod=998244353;
const int maxn=1e6+5;
const ll INF=100000000000000005;
const double eps=1e-10;
using namespace std;
ll n,m,p;
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
char str[maxn][55];
vector<int>v[30];
int pre[30];
int Find(int x)
{
    return x==pre[x]?x:pre[x]=Find(pre[x]);
}
int vis[26];
map<int,int>mp;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=26;i++) pre[i]=i;
    for(int i=1;i<=n;i++)
        scanf("%s",str[i]+1);
    for(int i=1;i<=n;i++)
    {
        int len=strlen(str[i]+1);
        int dx=Find(str[i][1]-'a'+1);
        vis[str[i][1]-'a'+1]=1;
        for(int k=2;k<=len;k++)
        {
            int dy=Find(str[i][k]-'a'+1);
            vis[str[i][k]-'a'+1]=1;
            if(dx!=dy)
                pre[dy]=dx;
        }
    }
    int res=0;
    for(int i=1;i<=26;i++) pre[i]=Find(i);
    for(int i=1;i<=26;i++)
        if(vis[i]&&!mp[pre[i]])
        {
            mp[pre[i]]=1;
            res++;
        }
    printf("%d\n",res);
    return 0;
}

这题认真想想能想出来的,可惜只剩5分钟敲代码,被B和C卡自闭...