题目链接:http://codeforces.com/problemset/problem/713/A
题意:
Sonya 有一个可放置重复元素的集合 multiset, 初始状态为空, 现给予三种类型的操作:
+ ai : 把 ai 加入到集合 multiset 中, 可能出现重复元素.
- aj : 把 aj 从集合 multiset 中删除, 保证集合中一定存在这个元素.
? s : 统计集合中现有的元素和模式串 s 匹配的个数.s 是一个 “01” 串, 其中 "0" 代表偶数, "1" 代表奇数.
匹配的定义:假设集合中存在一个数字 num, 如果 num 的长度短于 s 的长度, 则给 num 左边补 “0” 直到两个串的长度相等.如果 num 的长度长于 s 的长度, 则给 s 左边补 “0” , 同样直到两个串的长度相等, 之后如果 num 和 s 匹配, 则 num 串的每位应该满足串 s 的奇偶性要求.假设 s = 010, num = 2212, 则 s 左补 “0”, s = 0010, num 从左到右的奇偶性为 “偶偶奇偶” 满足 s 的要求, 则 num 和 s 匹配.同理 s 和 “92" 也匹配, 和 “110” , “3” 等则不匹配.
思路:
在这里,主要的问题是解决 "统计和 s 匹配的元素的个数" 这个问题.因为这里要求的是输出元素的个数, 并没有要求输出元素本身, 那么不妨对每个元素做一个变化, 把具有相同特征但是值不同的元素都视为同样的一个元素. 因为题目中告诉, 这个串的长度不长于 18 位, 则对于每个元素都可以把它变换为一个统一的 18 位串, 对于一个元素 num, 如果位数小于 18, 则左补 "0", 直至位数为 18 位, 之后对于每一位如果此位的数为奇数则直接把此位设置为 “1”, 否则设置为 “0”.比如元素 “241” ---> "00000,00000,00000,001",这样做处理后, 则由于数字 “241” 和数字 “463” 具有相同特征(奇偶性都为 “001”),则处理之后两个数字所对应的模式串应该相等, 就可以大大简化匹配时所做的重复操作.同样对于查询串 s, 也做同样的处理.之后利用 STL 中的 map, 统计相同模式串出现的次数.就可以比较简单的坚决 “查询” , “增加” 以及 “删除” 操作.
代码:
#include <bits/stdc++.h> using namespace std;
typedef long long LL;
const int MAXN = ; string Format(char s[]) { // 对于字符串 s 进行处理, 奇数位变为 “1” 偶数位变为 “0”, 左补 “0” 至 18 位
char revs[];
int len = strlen(s);
for(int i = ; i <= - len; i++) revs[i] = '';
for(int i = - len; i <= ; i++) revs[i] = (s[i - + len] - '') & ? '' : '';
revs[] = '\0'; string ss = revs;
return ss;
} int main() {
ios_base::sync_with_stdio(); cin.tie();
map<string, int> muset;
int T; cin >> T;
while(T--) {
char ord, num[]; cin >> ord >> num;
string ss = Format(num);
if(ord == '+'){
map<string, int>::iterator it;
it = muset.find(ss);
if(it == muset.end()) muset[ss] = ; //利用 map 对同一个模式的串的个数奇数
else muset[ss]++;
}
else if(ord == '-') muset[ss]--;
else cout << muset[ss] << endl;
}
return ;
}