题意:
给出三种操作 + - ?
注意数字有个数区别
+ 在集合中加入一串数字
- 在集合中减去一个数字
?寻问集合中数字的个数。
思路:
当时一看以为是个记录字符串,慢慢匹配的过程,但是想了下数据很大,同学突然说按编码可以做,想了下确实可以,结果一发就A了。
回头想了下 为什么会想到编码呢? 因为在这道题中,数字的区别是在于奇数偶数,也就是可以用0 1 数字%2 来代表。而且? 给人的第一 反应是二进制表示,并且题目中告诉了他可以判断对应位置的奇数偶数。
那么将+ - 后的数字,先进行二进制编码,然后转换为十进制,存储在数组中 , 2^18完全可以接受,并不大。
而对应的把? 后面的数字进行十进制转化,就可以找到对应哈希映射的数据个数。
第一次题这么想,想法挺有意思。
#include <iostream> #include <stdio.h> #include <cstring> using namespace std; char op[5]; char tep[20]; int a[10000000]; int main() { int n; cin>>n; int len=0; while(n--) { scanf("%s",&op); if(op[0]=='+') { scanf("%s",&tep); int lena=strlen(tep); int k=0; for(int i=0;i<lena;i++) { k*=2; k+=(tep[i]-'0')%2; } a[k]++; //cout<<k<<endl; } else if(op[0]=='-') { scanf("%s",&tep); int lena=strlen(tep); int k=0; for(int i=0;i<lena;i++) { k*=2; k+=(tep[i]-'0')%2; } a[k]--; // cout<<k<<endl; } else if(op[0]=='?') { scanf("%s",&tep); int lena=strlen(tep); int k=0; int tz=1; for(int i=lena-1;i>=0;i--) { if(tep[i]=='1') { k+=tz; } tz*=2; } // cout<<k<<endl; printf("%d\n",a[k]); } } return 0; }