zhizhesoft

  • 首页
ZHIZHESOFT
zhizhesoft
  1. 首页
  2. 正文

hackrank subsets

2019年7月2日 29点热度 0人点赞 0条评论

题

1.插入x
2.删除x
3.给s,查询\(a\&s==a\)的个数

插入和删除其实是相同的。
插入删除的时候前八位枚举子集,操作一下就行了。
查询的时候枚举后八位,然后就高维前缀和一下输出即可。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
void cmax(int&x,const int&y){x=x>y?x:y;}
void cmin(int&x,const int&y){x=x<y?x:y;}
const int N=256;
struct Node{
	int cnt[N],f[N];
	int&operator[](int x){return cnt[x];}
	void dp(){
		rep(i,0,N-1)f[i]=cnt[i];
		rep(j,0,7)rep(i,0,N-1)if(i>>j&1)f[i]+=f[i^(1<<j)];
	}
}a[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int q;
	cin>>q;
	while(q--){
		string s;
		cin>>s;
		if(s=="add"){
			int x;
			cin>>x;
			int y=x>>8,z=x&255;
			int u=y^255;
			for(int sub=u;;--sub&=u){
				a[y^sub][z]++;
				if(!sub)break;
			}
		}
		if(s=="del"){
			int x;
			cin>>x;
			int y=x>>8,z=x&255;
			int u=y^255;
			for(int sub=u;;--sub&=u){
				a[y^sub][z]--;
				if(!sub)break;
			}
		}
		if(s=="cnt"){
			int x;
			cin>>x;
			int y=x>>8,z=x&255;
			a[y].dp();
			cout<<a[y].f[z]<<'\n';
		}
	}
	return 0;
}
标签: hackrank subsets
最后更新:2022年6月20日

risingsun

这个人很懒,什么都没留下

点赞
Search

COPYRIGHT © 2022 zhizhesoft. ALL RIGHTS RESERVED.