【UKIEPC 2015 C】【STL set map stringstream】Conversation Logネットワークレビューすべての人に言われた言葉map套set法+人哈希法

#include<stdio.h> 
#include<iostream>
#include<string.h>
#include<vector>
#include<sstream>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
const int N=1e4+5;
const int L=2e6+10;
set<string>name;//      
map<string,set<string> >cnt;//            
map<string,int>freq;//            
map<string,int>::iterator it;
char nm[24];
char s[L];
char w[L];
int n,m;
vector<pair<int,string> >b;
int main()
{
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        //   ，        
        scanf("%s",nm);
		name.insert(nm);

		//   ， stringstream         
        gets(s);
        stringstream cinn(s);
        while(cinn>>w)//w    
        {
            freq[w]++;//          
            cnt[w].insert(nm);//             
        }
    }

	//   ，     ，          ，  （        ，     ）  pair      
	n=name.size();
    for(it=freq.begin();it!=freq.end();it++)
    {
        if(cnt[it->first].size()==n)
        {
            b.push_back(make_pair(-it->second,it->first));
        }
    }
    sort(b.begin(),b.end());
    int g=b.size();
    if(g==0)puts("ALL CLEAR");
    else for(int i=0;i<g;i++)cout<<b[i].second<<endl;
    return 0;
}
/*
【trick&&  】
1，       。             
2，      。    1e4，      1e6

【  】
 m(1e4)	   ，        2e6
      ，
            ，     20。
                。

                 。
  （      ，       ）  。
          ，  ALL CLEAR

【  】
STL

【  】
  ，      。            ，           。
                     ？

   ：
      ，
	    map<string,set<string> >， set             
	    map<string,int>，           
                  （  n），   set.size()     n，                 。
	            ，       hash   int，     int       。

   ：
      ，
	    map<string,int>            
	    map<string,int>  ，           
          ，                  ？
        。          。             ，            +1。

      ：
https://docs.google.com/presentation/d/1V4UHi1pLUhZR32H06SlIMi9egm9acbQe-DNCLpAQmf8/present?slide=id.gc6f83aa91_0_56
【     &&  】
        nlog(n)   。  set/map size      n，

【  】
input
8
Jepson no no no no nobody never
Ashley why ever not
Marcus no not never nobody
Bazza no never know nobody
Hatty why no nobody
Hatty nobody never know why nobody
Jepson never no nobody
Ashley never never nobody no

output
no
nobody
never

input
2
Villain avast
Scoundrel ahoy

output
ALL CLEAR
*/

#include<stdio.h> 
#include<iostream>
#include<string.h>
#include<vector>
#include<sstream>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
const int N=1e4+5;
const int L=2e6+10;
map<string,int>name;//          
set<string>a[N];//          
map<string,int>cnt;//           
map<string,int>freq;//            
map<string,int>::iterator it;
char nm[24];
char s[L];
char w[L];
int n,m;
vector<pair<int,string> >b;
int main()
{
    n=0;scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        //   ，          
        scanf("%s",nm);
        int o;
        if(name.find(nm)==name.end())o=name[nm]=++n;
        else o=name[nm];

		//   ， stringstream         
        gets(s);
        stringstream cinn(s);
        while(cinn>>w)//w    
        {
            freq[w]++;//          
            if(a[o].find(w)==a[o].end())//             
            {
                cnt[w]++;//       ++
				a[o].insert(w);//  insert   
            }
        }
    }

	//        ，          ，  （        ，     ）  pair      
    for(it=cnt.begin();it!=cnt.end();it++)
    {
        if(it->second==n)
        {
            b.push_back(make_pair(-freq[it->first],it->first));
        }
    }
    sort(b.begin(),b.end());
    int g=b.size();
    if(g==0)puts("ALL CLEAR");
    else for(int i=0;i<g;i++)cout<<b[i].second<<endl;
    return 0;
}
/*
【trick&&  】
1，       。             
2，      。    1e4，      1e6

【  】
 m(1e4)	   ，        2e6
      ，
            ，     20。
                。

                 。
  （      ，       ）  。
          ，  ALL CLEAR

【  】
STL

【  】
  ，      。            ，           。
                     ？

   ：
      ，
	    map<string,set<string> >， set             
	    map<string,int>，           
                  （  n），   set.size()     n，                 。
	            ，       hash   int，     int       。

   ：
      ，
	    map<string,int>            
	    map<string,int>  ，           
          ，                  ？
        。          。             ，            +1。

      ：
https://docs.google.com/presentation/d/1V4UHi1pLUhZR32H06SlIMi9egm9acbQe-DNCLpAQmf8/present?slide=id.gc6f83aa91_0_56
【     &&  】
        nlog(n)   。  set/map size      n，

【  】
8
Jepson no no no no nobody never
Ashley why ever not
Marcus no not never nobody
Bazza no never know nobody
Hatty why no nobody
Hatty nobody never know why nobody
Jepson never no nobody
Ashley never never nobody no

8
Jepson no no no no nobody never
Ashley why ever not
Marcus no not never nobody
Bazza no never know nobody nobody nobody nobody nobody nobody
Hatty why no nobody
Hatty nobody never know why nobody
Jepson never no nobody
Ashley never never nobody no

2
Villain avast
Scoundrel ahoy

*/