首页 > 代码库 > Codeforces cf 713A Sonya and Queries
Codeforces cf 713A Sonya and Queries
【题意：】
t次操作,每次操作有下述三种类型:
+ a 往multiset中增加一个非负整数a,允许相同的数出现
- a 从multiset中减去一个非负整数a,执行此操作时保证multiset存在该非负整数a
? s 询问multiset中有多少个数与模式串s匹配(匹配的定义:模式串中,‘0‘表示该位为偶数,‘1‘表示该位为奇数)
即s与a从右往左,相对应的奇偶性一致时(长度不一致时,在较短的前面补0),称为二者匹配
输出与模式串s匹配的数的个数
【分析：】
题目说a，s最多都是18位，而且要从后往前对应匹配，所以把字符串逆转同时还有其对应的01字符，然后利用map快速查找和删除
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <queue>#include <map>using namespace std;typedef long long LL;const LL N=500;struct b { string s1;//01 string s2; bool operator<(const b& other) const//操作符重载，否则报错 { if (this->s1 < other.s1) return true; return false; }};map<b,int >mp;int main(){ int n,i; cin>>n; while(n--) { getchar(); string tmp; char c; cin>>c>>tmp; int len=tmp.length(),j=0; b t; for(i=len-1; j<=18; j++) { if(i>=0) { t.s1+=(tmp[i]-‘0‘)%2+‘0‘; t.s2+=tmp[i]; i--; } else { t.s1+=‘0‘; t.s2+=‘0‘; } } if(c==‘+‘) { mp[t]++; } else if(c==‘-‘) { map<b,int>::iterator it; it=mp.find(t); if(it->second==1) mp.erase(t); else mp[t]--; } else if(c==‘?‘) { int ans=0; ans+=mp[t];//若是遍历的话会TLE cout<<ans<<endl; } } return 0;}/*+ 200+ 200- 200? 0+ 200? 0*/
Codeforces cf 713A Sonya and Queries
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。