kmjp's blog

競技プログラミング参加記です

Codeforces #371 Div1 A. Sonya and Queries

ひどい出来でした。
http://codeforces.com/contest/713/problem/A

問題

初期状態で空のmultisetがある。
これについて以下のクエリに答えよ。

  • multisetに整数A[i]を加える。
  • multisetから整数A[i]を1つ取り除く。
  • 文字列sが与えられる。sは01からなる。multiset中、下|s|桁の偶奇がsの01と一致するものの個数を求めよ。なお、|s|桁以上の数値は上位桁は偶数が指定されているものと見なして数える。

解法

multiset等不要で、整数の追加・削除の際に値の各桁の偶奇を元に|A[i]|桁の2進数表記の数値に置き換えて足し引きするだけ。

int T;
char C;
ll V;
string Q;
int num[1<<18];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		
		cin>>C;
		if(C=='+' || C=='-') {
			cin>>V;
			x = 0;
			FOR(i,18) x = x*2 + V%2, V/=10;
			
			if(C=='+') num[x]++;
			if(C=='-') num[x]--;
		}
		else {
			cin>>Q;
			reverse(ALL(Q));
			x=0;
			FORR(c,Q) x=x*2+(c-'0');
			FOR(i,18-Q.size()) L=L*2;
			cout<<num[L]<<endl;
			
		}
	}
	

}

まとめ

この問題、multiset中|s|より桁数の多い数字は0を充当して答えることになってるけど、0でも1でも可、にした方が面白いんじゃないかな。
まぁBITの数え上げが加わるだけだけど。
…というか自分は最初それで勘違いして1WAした。