cf1722C

标签：map int 复杂度 cf1722C str 字符串

example：cf1722C

原始思路是用5e5的布尔数组对字符串哈希是否出现进行记录，但每次处理时初始化增加时间复杂度，大型数组增加空间复杂度，且编程时处理细节及判断较为繁琐

考虑使用STL中的map对字符串进行记录，时间及空间复杂度还有编程难度均下降

定义：map<string, int> h;

使用方法：（以统计字符串出现次数为例）

map<string, int> h;
char str[20];
for (int i=1;i<=n;++i) {
  cin>>str; h[str]++;      
}
for (int i=1;i<=m;++i)
{
    cin>>str;
    if (h.find(str)==h.end()) puts("0");
    else cout<<h[str]<<endl;
}

再贴上此题参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 void sol(){
 4     int n;cin>>n;string s[(3*n)+1];map<string,int>m;int c=0;
 5     for(int i=0;i<n*3;i++)cin>>s[i],m[s[i]]++;
 6     for(int i=0;i<n*3;i++){
 7         if(m[s[i]]==1)c+=3;else if(m[s[i]]==2)c+=1;
 8         if((i+1)%n==0){
 9             cout<<c<<" ";c=0;continue;
10         }
11     }
12     cout<<endl;
13 }
14 int main(){
15     int t;cin>>t;while(t--)sol();
16 }

 

标签：map,int,复杂度,cf1722C,str,字符串
From： https://www.cnblogs.com/cptbtptpbcptbtptp/p/16707503.html