![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
n<=1024个文件 每个文件有一些tag,以及文件大小
q<=8192个询问 求同时满足这些tag的文件的大小之和
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
我的写法超时
看了watashi的用bitset,哇,这么好写,而且又快。。。
bitset : set(pos) , retset(pos) , retset() , &
*/
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<bitset>
#include<string>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
long long size[1024];
char str[100000];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(int n , q ; ~scanf("%d",&n) ; )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
map<string,bitset<1024> > mp;
bitset<1024> mask;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(int i = 0 ; i < n ; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%s%lld",str,&size[i]);
char *beg = str , *end;
while((beg = strchr(beg,'[')) != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
end = strchr(beg , ']');
mp[string(beg+1,end)].set(i);
beg = end;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
scanf("%d",&q);
while(q--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%s",str);
for(int i = 0 ; i < n ; i ++)
mask.set(i);
char *beg = str , *end;
while((beg = strchr(beg,'[')) != NULL)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
end = strchr(beg , ']');
map<string,bitset<1024> >::iterator it = mp.find(string(beg+1,end));
if(it == mp.end())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mask.reset();
break;
}
else mask &= it->second;
beg = end;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
long long ans = 0;//会超int
for(int i = 0 ; i < n ; i ++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(mask[i])
ans += size[i];
}
printf("%lld\n",ans);
}
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论
![](/images/xml.gif)
|
|