 /**//*
n<=1024个文件 每个文件有一些tag,以及文件大小
q<=8192个询问 求同时满足这些tag的文件的大小之和

我的写法超时
看了watashi的用bitset,哇,这么好写,而且又快。。。
bitset : set(pos) , retset(pos) , retset() , &
*/
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<bitset>
#include<string>

using namespace std;

long long size[1024];
char str[100000];

int main()
  {

#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif


for(int n , q ; ~scanf("%d",&n) ; )
 {
map<string,bitset<1024> > mp;
bitset<1024> mask;

for(int i = 0 ; i < n ; i++)
 {
scanf("%s%lld",str,&size[i]);
char *beg = str , *end;
while((beg = strchr(beg,'[')) != NULL)
 {
end = strchr(beg , ']');
mp[string(beg+1,end)].set(i);
beg = end;
}
}

scanf("%d",&q);
while(q--)
 {
scanf("%s",str);
for(int i = 0 ; i < n ; i ++)
mask.set(i);
char *beg = str , *end;
while((beg = strchr(beg,'[')) != NULL)
 {
end = strchr(beg , ']');
map<string,bitset<1024> >::iterator it = mp.find(string(beg+1,end));
if(it == mp.end())
 {
mask.reset();
break;
}
else mask &= it->second;
beg = end;
}

long long ans = 0;//会超int
for(int i = 0 ; i < n ; i ++)
 {
if(mask[i])
ans += size[i];
}
printf("%lld\n",ans);
}
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|