题意:有n群人,每个人有喜欢的汉堡配方;有m家店,给出每家店的每个汉堡的配方,如果存在某个汉堡,其配料表包含某个人喜欢的配方,则这个人喜欢这个汉堡所在的店家。问你对每群人,输出被喜欢的人数最多的店面是哪家。
直接把每家店所能满足的口味表全塞到哈希表里面,暴力枚举统计即可。
这里用了双关键字哈希表,比较巧妙,是绝对的O(1)。
#include#include #include using namespace std;struct Man{ int S; bool like[1005]; Man(const int &S){this->S=S;memset(like,0,sizeof(like));}; Man(){};};typedef vector ::iterator ITER;//5000011//4000037vector v[1005];int n,m;int pp,st[2][3200033];int b[1005];struct HashTable{ bool a[5000011],b[4000037]; HashTable(){} void clear(){ for(int i=1;i<=pp;++i){ a[st[0][i]]=b[st[1][i]]=0; } pp=0; } void insert(const int &V){ int U1=V%5000011; a[U1]=1; int U2=V%4000037; b[U2]=1; st[0][++pp]=U1; st[1][pp]=U2; } bool find(const int &V){ return (a[V%5000011] && b[V%4000037]); }}T;char s[105];int len,S;void dfs(int cur,int dep,int Snow){ if(dep!=0){ T.insert(Snow); } for(int i=cur;i S)){ it->like[i]=1; } } } T.clear(); } for(int i=1;i<=n;++i){ memset(b,0,sizeof(b)); for(ITER it=v[i].begin();it!=v[i].end();++it){ for(int j=1;j<=m;++j){ if(it->like[j]){ ++b[j]; } } } int id=1; for(int j=2;j<=m;++j){ if(b[j]>b[id]){ id=j; } } printf("%d\n",id); } return 0;}