AcWing周赛39

2022年2月21日 下午8:58 比赛总结 , , ,

写在前面

排名:61/1513
过题数:3/3 AK!

罚时 A(884) B(427) C(229)
0:48:28 0:01:23 0:18:06 0:28:59

这个周末正好是美赛时间,经过一天美赛的折磨,小摆一下选择花半小时打一下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操作。
可能会问了,比如上面的carrycugb来说的话,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;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注