codeforces-371-C. Sonya and Queries

    xiaoxiao2022-06-28  24

    题意:

    给出三种操作 + -  ?  

    注意数字有个数区别

    + 在集合中加入一串数字

    - 在集合中减去一个数字

    ?寻问集合中数字的个数。

    思路:

    当时一看以为是个记录字符串,慢慢匹配的过程,但是想了下数据很大,同学突然说按编码可以做,想了下确实可以,结果一发就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; }

    转载请注明原文地址: https://ju.6miu.com/read-1124262.html

    最新回复(0)