牛客多校第七场 Problem C Bit Compression

题意

初始长度$2^n$的01序列，要从^&|中选择n个运算符。
• 序列长度:$(2^n)\to (2^{n-1})\to ... \to 16\to 8\to 4\to 2\to 1$。
• 问有多少个可能，使得运算后剩下的一个字符为1。

题解

事实上这道题暴力就是标准做法，但是dfs的过程一定是$3^n$的，会超出题目要求时间。我们必须考虑剪枝或者对小范围数据进行优化。

官方题解解答

• 暴力的复杂度是$3^n$的，只需要再优化一点点!
• 如果剩下了$16$个变量，可能性只有$65536$个。
• 预处理他们，得到一个$3^{n-4}$的做法(事实上官方在这里弄错了，是$3^{n-4} * 2^{n-4}$)。
• 事实上，直接暴力，常数优化即可。

std代码

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

bool B[22][(1<<20)+5];
int ans = 0;
int dp[5][(1<<16)+15];

void gen(int n)
{
    int pow3=1;
    for(int i=0;i<n;i++) pow3*=3;
    for(int i=0;i<(1<<(1<<n));i++)
    {
        for(int k=0;k<(1<<n);k++)
        {
            if(i&(1<<k)) B[n][k] = 1;
            else B[n][k] = 0;
        }
        for(int j=0;j<pow3;j++)
        {
            int cur = j;
            for(int k=n-1;k>=0;k--)
            {
                int z=cur%3;
                for(int l=0;l<(1<<k);l++)
                {
                    if(z==0) B[k][l]=B[k+1][2*l]&B[k+1][2*l+1];
                    else if(z==1) B[k][l]=B[k+1][2*l]^B[k+1][2*l+1];
                    else B[k][l]=B[k+1][2*l]|B[k+1][2*l+1];
                }
                cur/=3;
            }
            dp[n][i] += B[0][0];
        }
    }
}

void solve(int n)
{
    if(n<=4)
    {
        int bit = 0;
        for(int i=0;i<(1<<n);i++)
        {
            if(B[n][i]) bit^=(1<<i);
        }
        ans += dp[n][bit];
        return ;
    }
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < (1<<(n-1)); j++)
        {
            if(i==0) B[n-1][j] = B[n][2*j]&B[n][2*j+1];
            else if(i==1) B[n-1][j] = B[n][2*j]^B[n][2*j+1];
            else B[n-1][j] = B[n][2*j]|B[n][2*j+1];
        }
        solve(n-1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n; string z; cin>>z;
    for(int i=0;i<=4;i++) gen(i);
    for(int i=0;i<(1<<n);i++)
    {
        B[n][i] = z[i] - '0';
    }
    solve(n);
    cout<<ans<<'\n';
}

其他方法

事实上可以考虑剪枝
dfs对每个操作的所有可能计数，如果操作结果等于1，则$cnt+=1$
当$cnt == 2^i$也就是等于下一层的长度，也就是下一层均为1，答案+=cnt,否则才继续往下dfs

这样计算的最坏情况时间复杂度为$3^n * (2^{17} + 2^{16} + ... + 2) = 3^n * 2^{18} - 3$，为$\mathcal O(3^{n} * 2^{n})$

AC代码

#include <iostream>

using namespace std;
const int maxn = (1 << 18) + 5;
char ch[20][maxn];
int ans;

inline char op(char x, char y, int ope) {
    switch (ope) {
        case 1:
            return x ^ y;
        case 2:
            return x & y;
        case 3:
            return x | y;
        default:
            return 0;
    }
}

void dfs(char *s, int n) {
    for (int ope = 1; ope <= 3; ope++) {
        int cnt = 0;
        for (int i = 0; i < (1 << n); i += 2) {
            ch[n - 1][i >> 1] = op(s[i], s[i + 1], ope);
            if (ch[n - 1][i >> 1])
                cnt++;
        }
        if (cnt == (1 << (n - 1))) {
            ans += cnt;
        } else if (cnt) {
            dfs(ch[n - 1], n - 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n;
    cin >> ch[n];
    for (int i = 0; ch[n][i]; ++i) {
        ch[n][i] -= '0';
    }
    dfs(ch[n], n);
    cout << ans << '\n';
}