牛客多校第七场 C Bit Compression 思维

ゝ一世哀愁。 2021-09-20 13:50 312阅读 0赞

链接：[https://www.nowcoder.com/acm/contest/145/C][https_www.nowcoder.com_acm_contest_145_C]  
来源：牛客网

A binary string s of length N = 2 n is given. You will perform the following operation n times :  
  
\- Choose one of the operators AND (&), OR (|) or XOR (^). Suppose the current string is S = s 1s 2...s k. Then, for all ![305336_1533786712763_equation_tex_1_20_5Cle_20i_20_5Cle_20_5Cfrac_7Bk_7D_7B2_7D][], replace s 2i-1s 2i with the result obtained by applying the operator to s 2i-1 and s 2i. For example, if we apply XOR to \{1101\} we get \{01\}.  
  
After n operations, the string will have length 1.  
  
There are 3 n ways to choose the n operations in total. How many of these ways will give 1 as the only character of the final string.

## 输入描述: ##

The first line of input contains a single integer n (1 ≤ n ≤ 18).
    
    The next line of input contains a single binary string s (|s| = 2

). All characters of s are either 0 or 1.

## 输出描述: ##

Output a single integer, the answer to the problem.

示例1

## 输入 ##

复制

2
    1001

## 输出 ##

复制

## 说明 ##

The sequences (XOR, OR), (XOR, AND), (OR, OR), (OR, AND) works.
    
    
    题意：给你2^n个数，每次可以将前2^(n-1)个数和后2^(n-1)个数进行二进制与、或、异或操作中的一种，问有多少种不同的操作顺序使得最后的结果为一个一？
    分析：考虑直接暴力的时间复杂度是3^18，这个数与题目给出的时间限制已经很接近，所以我们只需要在直接暴力的基础上做一点点优化就可以了
    　　　考虑如果最后要得到一个一，则数列中一定要还存在一，否则无论与、或、异或操作都无法再得到一
    　　　所以我们只需要在暴力的时候判断下剩下的数中是否还有一，没有一就没必要继续操作
    AC代码：

#include <map>
    #include <set>
    #include <stack>
    #include <cmath>
    #include <queue>
    #include <cstdio>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #define ls (r<<1)
    #define rs (r<<1|1)
    #define debug(a) cout << #a << " " << a << endl
    using namespace std;
    typedef long long ll;
    const ll maxn = 1e6 + 10;
    const double eps = 1e-8;
    const ll mod = 1e9 + 7;
    const ll inf = 1e9;
    const double pi = acos(-1.0);
    string s;
    ll t[maxn*2]; //开始将数字存在1<<n后，每次数字合并后产生的1<<(n-1)往前面放，方便合并运算
    ll res = 0;
    void dfs( ll n ) {
        if( n == -1 ) {
            if( t[2] == 1 ) { //只剩一个一
                res ++;
            }
            return ;
        }
        ll k = 1<<n;
        for( ll j = 0; j <= 2; j ++ ) {
            ll cnt = 0;
            for( ll i = 1; i <= k; i ++ ) {
                ll tmp = i+k;
                if( j == 0 ) {
                    t[tmp] = t[tmp*2-1]^t[tmp*2];
                } else if( j == 1 ) {
                    t[tmp] = t[tmp*2-1]|t[tmp*2];
                } else {
                    t[tmp] = t[tmp*2-1]&t[tmp*2];
                }
                if( t[tmp] == 0 ) {
                    cnt ++;
                }
            }
            if( cnt == k ) { //如果都是零就不可能再出现一
                continue;
            }
            dfs(n-1);
        }
    }
    int main() {
        ll n;
        cin >> n;
        cin >> s;
        ll k = 1<<n;
        for( ll i = 1; i <= k; i ++ ) {
            t[i+k] = s[i-1] - '0';
        }
        dfs(n-1);
        cout << res << endl;
        return 0;
    }

转载于:https://www.cnblogs.com/l609929321/p/9550895.html

[https_www.nowcoder.com_acm_contest_145_C]: https://www.nowcoder.com/acm/contest/145/C
[305336_1533786712763_equation_tex_1_20_5Cle_20i_20_5Cle_20_5Cfrac_7Bk_7D_7B2_7D]: /images/20210726/df5070125b414271a27ebe7dcd7f5171.png