読者です 読者をやめる 読者になる 読者になる

Codeforces 371 Div2 C

問題

codeforces.com



 n 個のクエリが与えられます。それぞれのクエリの内容は以下のとおり

 + a_i :  a_i をリストに加える
 - a_i :  a_i をリストから1つ削除する。 この a_i はリストの中に1つ以上存在する。
 ? s : リストの中に  s を満たす a_i の個数を求める。ただし、 s は0と1のみで構成され、0は偶数に、1は奇数に対応する。もし、sa_i の桁数が違うなら、一番左に0を追加することで調整しなければならない。

 s = 010, a_0 = 296
この時は  a_0 は 偶数、奇数、偶数なので  s の 010 と対応しているため個数に加える。

解法

クエリ ? は各桁が、偶数か奇数かしか気にしていないため、クエリ + a_i- a_i の時に  a_i の各桁の数字が奇数なら1に、偶数なら0に変換すると良い。
また、桁数が18桁に満たない場合は左に0を追加することで比較を簡単化することができる。
あとはマップに突っ込めば良い

f:id:Matchald:20160914133317p:plain

コード

#include<iostream>
#include<map>
#include<string>
#include<algorithm>

int main() {
	int query;

	std::cin >> query;

	std::map<std::string, int> m; // 数字 -> 回数
	for (int i = 0; i < query; i++) {
		char op;
		std::string num;

		std::cin >> op >> num;

		for (int j = 0; j < num.length(); j++) {
			if ((num[j] - '0') % 2 == 0) {
				num[j] = '0';
			} else {
				num[j] = '1';
			}
		}

		while (num.length() < 18) {
			num.insert(num.begin(), '0');
		}

		if (op == '+') {
			m[num]++;
		} else if (op == '-') {
			m[num]--;
		} else {
			std::cout << m[num] << std::endl;
		}
	}

	return 0;
}