AcWing周赛39

写在前面

排名：61/1513
过题数：3/3 AK！

这个周末正好是美赛时间，经过一天美赛的折磨，小摆一下选择花半小时打一下AcWing周赛，是不是太自信了哈哈哈半小时，这几周比赛y总确实出的题目比较简单了（也许是自己变强了呢），已经连续三周AK了，继续努力！希望能一直AK下去，不过排名相比于上周有点靠后，我给自己定一个目标吧，50名左右就好。

A.元素分类（签到）

题意

题目链接：AcWing 4302. 元素分类 - AcWing
题目给出一个序列，可以分成两类B和C,求sumB-sumC的最大值是多少

思路

签到题，B的贡献是正，C的贡献是负，直接把负数给C集合，正数给B集合这样的话最后贡献最大。

代码

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) 
    {
        cin>>x;
        ans+=Abs(x);
    }
    cout<<ans;
}

B.链表（链表+哈希）

题意

题目链接：AcWing 4303. 链表 - AcWing
给出n行，每行两个字符串s1,s2，代表s1指向s2的链表，保证不会成树，最后n行下来是若干个链表，求又多少链表以及这些链表的首和尾

思路

因为给的是字符串，所以我们需要离散化/哈希，就是映射成数字，那么这个是双向的，所以我用了两个map,一个是map<string,int>代表是题目给的对应我代码里面的数字，另一个是map<int,string>代表反向的，这些数字对应原来的哪个字符串...STL YYDS!
然后本来想建边的，后面发现并查集思想就可以，因为保证是链，我们可以用并查集里面的father[x]的思想，后面找回去的时候还需要son[x]，那就都写上吧，记得初始化都为自己！

代码

map<string,int> mp;
map<int,string> to;
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=10000;i++) fa[i]=i,son[i]=i;
    for (int i=1;i<=n;i++)
    {
        cin>>s1>>s2;
        if (mp.find(s1)==mp.end()) mp[s1]=++num,to[num]=s1;//编号
        if (mp.find(s2)==mp.end()) mp[s2]=++num,to[num]=s2;//编号
        fa[mp[s2]]=mp[s1];
        son[mp[s1]]=mp[s2];
    }
    for (int i=1;i<=num;i++)
        if (fa[i]==i)//如果这个父亲节点是自己，说明这里存在一条链，开始是它
        {
            int t=i;
            while (son[t]!=t)//往下找，直到son[t]==t,也就是“儿子”是自己，也就是链的尾巴，找不到下面的了
            {
                t=son[t];
            }
            pair<string,string> tmp;
            tmp.first=to[i];tmp.second=to[t];
            ans.push_back(tmp);//存，我不明白为什么不能是ans.push_back({to[i],to[t]})
        }
    cout<<ans.size()<<endl;
    for (auto i:ans)
        cout<<i.first<<" "<<i.second<<endl;
}

C.字符串归类（并查集）

题意

题目链接：AcWing 4304. 字符串归类 - AcWing

给定 $n$ 个由小写字母构成的字符串。
现在，请你对它们进行归类。
对于两个字符串 $a$ 和 $b$：
如果至少存在一个字母在 $a$ 和 $b$ 中同时出现，则 $a$ 和 $b$ 属于同一类字符串。
如果字符串 $c$ 既与字符串 $a$ 同类，又与字符串 $b$ 同类，则 $a$ 和 $b$ 属于同一类字符串。
请问，最终所有字符串被划分为多少类。

也就是说，给你$n$个字符串，对于任意两个其中如果有相同的字母，那么就是一类的，问最后有多少类

思路

很难不想到并查集，如果判断两个是同类的，那么就进行并查集合并操作，那么怎么判断是否是同一类的呢？
我这里有个思路，首先还是并查集初始化操作，每一个父亲是自己fa[i]=i，然后我们定一个26位的二维数组(or vector)，代表着26个字母，我们来想象，如果对于一个字符串读入，我们扫一遍，对于其中的字母我们就把这个编号往对应后面排，这样的话最后就是一张表，同一位底下的就是代表那个编号有相同字母的，所以我们需要将这一类进行合并。
那么我们来优化一下，照样是读入，然后扫一遍字符串，我们那个26位的数组，就只存第一次出现的编号，比如读入carry,这个是第一个读入的，那么a[3]=a[1]=...=1对应各个字母，存1，这时候如果来cugb，那么对于其中的b来说，a[2]=2，因为这个时候编号是2了，就这样，你看这时候如果发现c出现过了，那么说明是同类的，就与a[3]保留第一次出现的编号进行union操作。
可能会问了，比如上面的carry和cugb来说的话，c不是代表1和2合并了嘛，那么对于b来说a[2]存的是1还是2呢？——存的还是2，不过之后与2合并的时候，会因为并查集的算法与1再合并。
最后再统计有多少father[i]==i即可

代码

inline int find(int x)
{
    return father[x]==x?x:father[x]=find(father[x]);
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) father[i]=i;
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        for (int j=0;j<s.length();j++)
        {
            c=s[j]-'a'+1;//第几个，c对应3，z对应26
            if (a[c]==0) a[c]=i;//如果没存，那么就存第一次出现该字母的编号
            int fx=find(a[c]),fy=find(i);
            if (fx!=fy)
                father[fy]=fx;//union合并操作
        }
    }
    for (int i=1;i<=n;i++) find(i);//习惯，有好处，路径压缩
    for (int i=1;i<=n;i++) if (father[i]==i) cnt++;//统计
    cout<<cnt;
}