Codeforces Round #371 (Div. 2) C. Sonya and Queries 压位、二进制来状态压缩

Source

Codeforces Round #371 (Div. 2)

My Solution

压位、二进制来状态压缩

根据 ai的各个digit的奇偶可以把它状态压缩到一个 Ind

比如 Ind = 0；

然后最右边以为是 奇数 则 Ind += pow2[0];

如果是 右边第二位是奇数则 再  Ind += pow2[1]

如果是偶数则先对应的二进制是0，所以不要 更新 Ind

这样 对于 每个 ai 都唯一对应一个 Ind

而且 ai < 1e18， 所以最多18个二进制位就可以存放所有状态， Ind <= 2^18;

1、'+' 的时候， ans[Ind]++;

2、‘-’ 的时候， ans[Ind]--;

3、'?' 的时候， cout << ans[Ind] << endl;

复杂度  O(n + sum_length(ai));

这个题似乎还可以用 01二进制树来做， 这里就不再多言了。

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = (1 << 19) + 8;

LL ans[maxn], pow2[100];

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);
    int T = 2;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    pow2[0] = 1;
    for(int i = 1; i <= 20; i++){ pow2[i] = pow2[i - 1] * 2; } memset(ans, 0, sizeof ans); LL n, sz, Ind; string val; char ch; cin >> n;
    while(n--){
        Ind = 0;
        cin >> ch >> val;
        if(ch == '+'){
            sz = val.size();
            for(int i = sz - 1; i >= 0; i--){
                if((val[i] - '0') % 2 == 1){
                    Ind += pow2[sz - 1 - i];
                }
            }
            ans[Ind]++;
        }
        else if(ch == '-'){
            sz = val.size();
            for(int i = sz - 1; i >= 0; i--){
                if((val[i] - '0') % 2 == 1){
                    Ind += pow2[sz - 1 - i];
                }
            }
            ans[Ind]--;
        }
        else{
            sz = val.size();
            for(int i = sz - 1; i >= 0; i--){
                if(val[i] == '1'){
                    Ind += pow2[sz - 1 - i];
                }
            }
            cout << ans[Ind] << "n";
        }
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx