首页 > 代码库 > 一道题看bitset应用 --ZOJ 3642

一道题看bitset应用 --ZOJ 3642

2024-07-16 08:39:50   222人阅读

题意：给n个文件，包括文件名和文件大小，然后给出k个关键词，查询包含该关键词的文件的大小总和。文件名为一些中括号括起的关键词的合集。

解法：可用bitset记录每一个关键词在哪些文件中出现，然后查询即可。

bitset用法如下：

bitset<SIZE> bs;bool is_set = bs.any();    //是否存在1bool not_set = bs.none();  //是否全0int cnt_one = bs.count();bs[index] = 1;bs.flip(index);    //反转第index位bs[index].flip()   //反转第index位bs.flip()          //反转所有bs.set();          //所有位赋为1bs.reset();        //所有位赋为0bs.set(index);     //第index位赋为1bs.reset(index)    //第index位赋为0string bitval("1010");bitset<32> bs2(bitval);   //初始化

 

用到了指针和strchr函数，strchr(str,ch)函数用来找出str指向的字符串中第一次出现字符ch的位置。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <map>#include <bitset>#include <cstdlib>#define ll long longusing namespace std;#define N 1207bitset<N> mask;ll siz[N];char ss[N];char *a,*b;map<string,bitset<N> > mp;int main(){    int n,k,i,j;    while(scanf("%d",&n)!=EOF)    {        mp.clear();        for(i=1;i<=n;i++)        {            scanf("%s %lld",ss,&siz[i]);            a = ss;            while((a = strchr(a,‘[‘)) != NULL)            {                b = strchr(a,‘]‘);                string tmp = string(a+1,b);                mp[tmp].set(i-1);                a = b;            }        }        scanf("%d",&k);        while(k--)        {            scanf("%s",ss);            for(j=0;j<n;j++)                mask.set(j);            a = ss;            while((a = strchr(a,‘[‘)) != NULL)            {                b = strchr(a,‘]‘);                string tmp = string(a+1,b);                if(!mp.count(tmp))                {                    mask.reset();                    break;                }                else                    mask &= mp.find(tmp)->second;                a = b;            }            ll res = 0;            for(j=0;j<n;j++)            {                if(mask[j])                    res += siz[j+1];            }            printf("%lld\n",res);        }    }    return 0;}
View Code

 


联系
我们