博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【哈希表】Ural Championship April 30, 2017 Problem H. Hamburgers
阅读量:5812 次
发布时间:2019-06-18

本文共 1352 字,大约阅读时间需要 4 分钟。

题意:有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;}

转载于:https://www.cnblogs.com/autsky-jadek/p/7617749.html

你可能感兴趣的文章