题解：P12314 [蓝桥杯 2024 国 C] 集合的数量

很水的一道题，思路较为直接。考察对 set 的使用方法是否明晰及 set 去重和自动排序的特性。

题目大意：给出

n

个由一些符号和小写字母构成的子串组成的未去重集合，求将它们中的所有元素去重后再将它们本身去重还剩下几个集合。

题目思路：看到集合和去重很容易想到 STL 中的 set。先每行输入一个字符串代表一个集合，利用集合中子串只有小写字母的特性遍历字符串去掉中间分隔用的符号以求出子串，因为 set 容器本身有自动去重和排序的特性，拿到每个字符串中的子串后放入一个 set 中自动去重和按照字典序即可，拿到去重后的 set 在放入一个大的 set 中去重和排序，这样大的 set 就去除了所有本质相同的集合，输出大的 set 的长度（即去重后剩余集合数）即可。

Code:

CPP

#include<bits/stdc++.h>
using namespace std;
set<set<string>>st;//用于存储小集合的大集合
set<string> sts;//存储子串的小集合
long long n;
int main(){
    cin>>n;
    while(n--){
        sts.clear();//每次循环前清空用过的集合
        string s;
        cin>>s;
        string s1="";
        for(int i=0;i<s.size();i++){//遍历出每个子串拿到小集合 
            if(97<=s[i]&&s[i]<=122) s1+=s[i];//如果不是分隔符号而是小写字母就是一个子串中的内容
            else{
                sts.insert(s1);//当前不是小写字母，说明接下来有一个新的子串，将上一个将子串放入小集合中并去重
                s1="";//当前不是小写字母，说明接下来有一个新的子串，清空当前收集子串的字符串，收集下一个子串
            }
        }
        st.insert(sts);//将去重后的小集合放入大集合并去重
    }
    cout<<st.size();//输出大集合去重后的长度
    return 0;
}

题解：P12314 [蓝桥杯 2024 国 C] 集合的数量

文章操作

相关推荐

评论

题解：P12314 [蓝桥杯 2024 国 C] 集合的数量