10月3日NOIP-模拟T3 subset

    科技2022-07-11  85

    3.1 题目᧿述 一开始你有一个空集,集合可以出现重复元素,然后有Q个操作

    add s 在集合中加入数字s。del s 在集合中删除数字s。保证s存在cnt s 查询满足a&s=a条件的a的个数 3.2 输入Ṭᔿ 第一行一个整数Q接下来Q行,每一行都是3个操作中的一个 3.3 输出Ṭᔿ 对于每个cnt操作输出答案

    恩…这道题首先暴力很好想,就每加入一个数后从0枚举到216更新答案,查询时O(1)查询就可以了(没试过暴力,这样应该没错吧…)然后很明显要T飞的。然后这种做法明显是通法,也就是说无论什么要求都可以这样做,但这道题是要求a&s=a,便去找这个式子有什么特殊的地方。然后发现如果把a,s换为二进制,a&s=a相当于任意对应的几位&后都不变,然后就可以分块来做,直接分为28块,发现时间复杂度瞬间降了下来,,每次把加入(删掉)的数依次看是否丢入(取出)块中。在询问中直接进入询问数a的前八位对应的块,在块里枚举,对应第二维ed。 那这道题就可以偷税的A了

    code871 :

    #include<bits/stdc++.h> using namespace std; int n,f[300][300],x,op,ed; string saber; int Read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return f*x; } int main() { n=Read(); for(int i=1;i<=n;i++) { cin>>saber; x=Read(); op=x>>8; ed=x&255; if(saber[0]=='a') { for(int i=0;i<=255;i++) if((op&i)==op) f[i][ed]+=1; } if(saber[0]=='d') { for(int i=0;i<=255;i++) if((op&i)==op) f[i][ed]-=1; } if(saber[0]=='c') { int ans=0; for(int i=0;i<=255;i++) if((i&ed)==i) ans+=f[op][i]; printf("%d\n",ans); } } return 0; }
    Processed: 0.025, SQL: 8