/**//* 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
搜索
最新评论
|
|