P1808 单词分类——set去重、sort统一标准

àì夳堔傛蜴生んèń 2023-01-13 10:20 48阅读 0赞

# [P1808 单词分类][P1808] #

**题目描述**  
Oliver为了学好英语决定苦背单词，但很快他发现要直接记住杂乱无章的单词非常困难，他决定对单词进行分类。

两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。

例如“AABAC”，它和“CBAAA”就可以归为一类，而和“AAABB”就不是一类。

现在Oliver有N个单词，所有单词均由大写字母组成，每个单词的长度不超过100。你要告诉Oliver这些单词会被分成几类。

**输入格式**  
输入文件的第一行为单词个数N，以下N行每行为一个单词。

**输出格式**  
输出文件仅包含一个数，表示这N个单词分成的类数

**输入输出样例**  
输入

3 
    AABAC 
    CBAAA 
    AAABB

输出

2

**说明/提示**  
对于70%的数据满足N≤100。 对于100%的数据满足N≤10000。

--------------------

**题解**

用sort函数排序没一个单词，统一标准；

塞入集合，自动判重并去重。

#include <bits/stdc++.h>
    using namespace std;
    set<string>st;
    string str;
    int main()
    { 
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) { 
    	    cin >> str;
    	    sort(str.begin(), str.end());
    	    st.insert(str);
        }
        cout << st.size() << endl;
        return 0;
    }

**后记**

这道题其实我感觉似曾相识，那道题是[【UVA156 反片语 Ananagrams】][UVA156 _ Ananagrams]，只不过那一道题是用的map和动态数组将字符串来回处理，比这个要难得多。不过重点的核心思路是相同的——用sort重排字符串使其统一标准

[P1808]: https://www.luogu.com.cn/problem/P1808
[UVA156 _ Ananagrams]: https://thomas.blog.csdn.net/article/details/115445790

发表评论取消回复

表情：

评论列表（有 0 条评论，48人围观）

还没有评论，来说两句吧...

相关阅读

相关 python中set函数去重

python中set函数去重 set()函数是python内置函数中比较基础的一个。主要是创建一个无序不重复元素集，可进行关系测试，删除重复数据，还可以计算交集、差集、并

男娘i/ 2024年03月26日 17:40/ 0 赞/ 105 阅读

相关 Set集合去重(详细篇)

一.什么是set集合 1.set集合组成 > Set 集合是 Java 集合框架中的一种实现，它的底层数据结构可以有多种选择，最常见的包括哈希表、红黑树等。 >

心已赠人/ 2024年03月16日 23:18/ 0 赞/ 86 阅读

相关 Java关于Set的相关去重

User类，必须要重写hashCode、equals方法 public class User { private String userId;

我就是我/ 2023年06月12日 04:27/ 0 赞/ 40 阅读

相关洛谷 P1808 单词分类

题目传送门：[https://www.luogu.com.cn/problem/P1808][https_www.luogu.com.cn_problem_P1808] 非常

Myth丶恋晨/ 2023年05月22日 14:29/ 0 赞/ 28 阅读

相关 P1808 单词分类——set去重、sort统一标准

[P1808 单词分类][P1808] 题目描述 Oliver为了学好英语决定苦背单词，但很快他发现要直接记住杂乱无章的单词非常困难，他决定对单词进行分类。两个单

àì夳堔傛蜴生んèń/ 2023年01月13日 10:20/ 0 赞/ 49 阅读

相关 java利用set给数组去重

hashSet无序 treeSet有序（对数据按其默认排序方式，进行排序） @Test public void test() throw

向右看齐/ 2022年07月24日 04:28/ 0 赞/ 165 阅读

相关 java Set 去重处理

package quChong; import java.util.HashSet; import java.util.Set; /\\ \ 编写

绝地灬酷狼/ 2022年06月07日 11:23/ 0 赞/ 250 阅读

相关关于 redis的 set 去重疑问

set 本质是hashmap，去重也就是hashmap的去重，hashcode 和equals方法。那么问题来了，当存储到redis 中的时候 redis是怎么实现去重的呢

谁践踏了优雅/ 2022年04月13日 12:26/ 0 赞/ 384 阅读

相关 set 排序和去重

import java.util.Iterator; import java.util.Scanner; import java.util.Set; import

た入场券/ 2022年04月05日 15:15/ 0 赞/ 292 阅读

相关 set() 去重原理

文章目录起步自定义的数据结构 \_\_eq\_\_函数 \_\_hash\_\_函数去重原理

悠悠/ 2022年01月15日 14:57/ 0 赞/ 308 阅读