[Codeforces_713A]Sonya and Queries

题目链接

http://codeforces.com/problemset/problem/713/A

题意

三种操作：

+ ai 集合里加一个整数ai，相同数记为多个。

- ai 集合里减一个该整数ai，若集合中存在多个则减一个，保证减操作时集合中有该数至少一个。

? s 输出集合中匹配模式s的整数有多少个，s是01串，0表示对应位为偶数，1表示对应位为奇数，若模式和整数位数不同则左侧补0补齐。For example, if the pattern is s = 010, than integers 92, 2212, 50 and 414 match the pattern, while integers 3, 110, 25 and 1030 do not.

此外，整数ai不超过10^18，模式s长度不超过18位。

总操作次数n<=10^6。

思路

原思路：是每次？操作时，遍历集合中的数看是否匹配模式。

结果：在n量级大时超时。

正确思路的点：

首先，整数ai和模式s都可以映射到唯一的数pos上，左侧补0无影响。

其次，ai和s映射到数pos的用相同方法处理。

故把串各位依次取奇1偶0，然后得到的数pos结果只有2^18种，开一个数组存每种结果的出现次数即可，？操作时直接输出数组对应pos的值即可，而不用再遍历当时的集合元素计算有多少个元素匹配该模式，降低时间复杂度。

代码

#include <stdio.h>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

#include <string>

#include <string.h>

using namespace std;

int cnt[1<<19];

int trans(char * str){

    int num=0;

    for(size_t i=0;i<strlen(str);i++){

        int x=str[i]-'0';

        num+=x&1;

        num=num<<1;

    }

    return num;

}

int main(int argc, const char * argv[]) {

    memset(cnt,0,sizeof(cnt));

    int n;

    scanf("%d",&n);

    while(n--){

        char op[2];

        char str[20];

        int num;

        scanf("%s%s",op,str);

        num=trans(str);

        if(op[0]=='+'){cnt[num]++;}

        else if(op[0]=='-'){cnt[num]--;}

        else{

            printf("%d\n",cnt[num]);

        }

    }

    return 0;

}

巴特西

[Codeforces_713A]Sonya and Queries

题目链接

题意

思路

相关知识点

代码

最新文章

热门文章