CF975A 题解

MattL · 2021-09-07 22:03:33 · 题解

洛谷链接 & 原题链接

题意： 输入 n 个字符串，对于每个字符串，你需要完成一下几个操作：

1. 按字典序排序
2. 去除重复字符
3. 统计操作后不同的字符串的个数

按字典序排序：

我们可以使用 STL 模板库中的 sort 函数，实现快排。

sort 的时间复杂度： O(n \log_2 n)

使用方法：

1. 对 C++ 库中自带的数据类型进行排序：

sort(首个数据的地址,最后一个数据的地址+1）

2. 对使用了 struct 的自定义类型进行排序：

sort(首个数据的地址,最后一个数据的地址+1,bool 类型的比较函数名称）

如果你已经重载了 "<" ，那么使用方法就同第一种了。

对于字符串，可以与 begin() 和 end() 函数一起使用，更便捷。

示例：

sort(s.begin(),s.end());

去除重复字符:

我们可以遍历一次字符串，如果当前字符与前一个字符不同，就可以记录加进操作后的字符串啦。

统计操作后不同的字符串的个数：

本文重点： map

map 就是在 STL 模板库中的哈希表，速度比手写哈希表略慢。

使用原理：

比如让模数为 3

现有数组 A=\{14,16,24,19,42\}

我们只需要用一个链表（ vector ）数组 B ，来存数据。

为什么要用链表呢？就是因为避免重复。像 14\mod 13=42\mod 13 这种重复的情况就可以用链表加上。

为什么用哈希表好呢？就是因为数据较为集中，空间浪费较少，还能把下标设为所有数据类型（对于 STL 比较方便而已）。

使用方法：

定义： map<下标类型,数据类型> 名字

使用方法与数组相同

像这题，我们可以开一个 map<string,bool> vis; 来标记某个字符串是否出现过。

上代码：

#include <bits/stdc++.h>
using namespace std;
int n,ans;
string s,t;
map<string,bool> vis;//全局的 bool 变量默认为 false 
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>s;
        sort(s.begin(),s.end());//排序
        t=s[0];
        for(int i=1;i<s.size();i++)//去重
            if(s[i]!=s[i-1])
                t+=s[i];
        if(!vis[t])//没出现过
        {
            ans++;
            vis[t]=true;//标记为出现过
        }
    }
    cout<<ans<<endl;
}