codeforces 713a Codeforces Problem 713A Sonya and Queries(字典樹)－IT工程師數位筆記本

文章出處

Codeforces Problem 713A Sonya and Queries

Accept: 0 Submit: 0
Time Limit: 1 second Memory Limit : 256 megabytes

Problem Description

Today Sonya learned about long integers and invited all her friends to share the fun. Sonya has an initially empty multiset with integers. Friends give her t queries, each of one of the following type:

+?ai — add non-negative integer ai to the multiset. Note, that she has a multiset, thus there may be many occurrences of the same integer.-? ai — delete a single occurrence of non-negative integer ai from the multiset. It's guaranteed, that there is at least one ai in the multiset.? s — count the number of integers in the multiset (with repetitions) that match some pattern s consisting of 0 and 1. In the pattern, 0 stands for the even digits, while 1 stands for the odd. Integer x matches the pattern s, if the parity of the i-th from the right digit in decimal notation matches the i-th from the right digit of the pattern. If the pattern is shorter than this integer, it's supplemented with 0-s from the left. Similarly, if the integer is shorter than the pattern its decimal notation is supplemented with the 0-s from the left.

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.

Input

The first line of the input contains an integert(1?≤?t?≤?100?000)— the number of operation Sonya has to perform.

Nexttlines provide the descriptions of the queries in order they appear in the input file. Thei-th row starts with a characterci— the type of the corresponding operation. Ifciis equal to '+' or '-' then it's followed by a space and an integerai(0?≤?ai?ciequals '?' then it's followed by a space and a sequence of zeroes and onse, giving the pattern of length no more than18.

It's guaranteed that there will be at least one query of type '?'.

It's guaranteed that any time some integer is removed from the multiset, there will be at least one occurrence of this integer in it.

Output

For each query of the third type print the number of integers matching the given pattern. Each integer is counted as many times, as it appears in the multiset at this moment of time.

Sample Input12
+ 1
+ 241
? 1
+ 361
- 241
? 0101
+ 101
? 101
- 101
? 101
+ 4000
? 0
4
+ 200
+ 200
- 200
? 0Sample Output2
1
2
1
1
1Hint

Consider the integers matching the patterns from the queries of the third type. Queries are numbered in the order they appear in the input.

1. 1 and 241.

2. 361.

3. 101 and 361.

4. 361.

5. 4000.

Problem Idea

解題思路:

【題意】

t次操作,每次操作有下述三種類型:

1. + a 往multiset中增加一個非負整數a,允許相同的數出現

2. - a 從multiset中減去一個非負整數a,執行此操作時保證multiset存在該非負整數a

3. ? s 詢問multiset中有多少個數與模式串s匹配(匹配的定義:模式串中,'0'表示該位為偶數,'1'表示該位為奇數)

即一個數從右往左,每位數的奇偶性與模式串一致時(長度不一致時,在前面補0),稱為二者匹配

輸出與模式串s匹配的數的個數

【類型】
字典樹

【分析】

三種操作中,顯然入手點在第三種操作

如何與模式串s匹配是此題關鍵

因為模式串s只有'0'和'1'兩種情況,可以想到用二叉樹

而這種匹配又可以采用字典樹來解決

對于每個插入的數,因為只有每位數的奇偶性是我們要用的

因此,我們可以在字典樹中只保存其奇偶性

例如樣例1

Codeforces Problem 713A Sonya and Queries(字典樹)

大致過程就是這樣子,希望能有助于大家理解

【時間復雜度&&優化】
O(18t)

題目鏈接→Codeforces Problem 713A Sonya and Queries

Source Code

/*Sherlock and Watson and Adler*/#pragma comment(linker, "/STACK:1024000000,1024000000")#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#define eps 1e-9#define LL long long#define PI acos(-1.0)#define bitnum(a) __builtin_popcount(a)using namespace std;const int N = 2;const int M = 2;const int inf = 1000000007;const int mod = 1000000007;struct tree{    int a[M],t;}s[1000005];char ch[N];int p;void init(int x){    s[x].t=0;    memset(s[x].a,-1,sizeof(s[x].a));}void buildtree(__int64 x){    int i,k=0;    for(i=0;i<18;i++)    {        if(s[k].a[x%2]==-1)        {            s[k].a[x%2]=p;            init(p++);        }        k=s[k].a[x%2];        s[k].t++;        x/=10;    }}void deletetree(__int64 x){    int i,k=0;    for(i=0;i<18;i++)    {        k=s[k].a[x%2];        s[k].t--;        x/=10;    }}void query(__int64 x){    int i,k=0;    for(i=0;i<18;i++)    {        if(s[k].a[x%2]==-1)        {            puts("0");            return ;        }        k=s[k].a[x%2];        x/=10;    }    printf("%d\n",s[k].t);}int main(){    int t;    __int64 x;    p=0;init(p++);    scanf("%d",&t);    while(t--)    {        scanf("%s%I64d",ch,&x);        if(ch[0]=='+')            buildtree(x);        else if(ch[0]=='-')            deletetree(x);        else            query(x);    }    return 0;}

就愛閱讀www.92to.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161206/63588.html

文章列表