题解：P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping

· · 题解

E.P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping - 洛谷

题意：有 2^n 条蛇，每条蛇有一个毒性，有多次询问，每次询问一个长度为 n 的串 s，字符串由 0、1、? 组成，你需要把 ? 任意改为 0 或 1，求所有可以修改得到的串对应的蛇毒性的和是多少。

挺搞人的题目，据说当年 AT 机子上会被卡常。。。

考虑类似于根号分治一样的做法，设 0 的个数，1 的个数，? 的个数分别为 a,b,c，那么我们可以知道 \min(a,b,c) \leq 6，那么大力分讨：

复杂度 O(q\times2^{\lfloor\frac{n}{3}\rfloor}+n\times 2^n)。

Code：这是一些成熟稳重的外星大象制定的代码。

#include<bits/stdc++.h>
using namespace std;
namespace IO {
    static const string name = "disinfect", suf_in = "in", suf_out = "out";
    static constexpr int S = (1 << 21), dgt = 2, ir = 1; char b[S], *p1 = b, *p2 = b, pb[S], *p = pb; void Fl() { fwrite(pb, 1, p - pb, stdout), p = pb; }
#define _r return *this
    struct Fr { bool _b(char c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t'; } char gc() { if (p1 == p2) p2 = (p1 = b) + fread(b, 1, S, stdin); return p1 == p2 ? ' ' : *p1++; } template <class T> Fr &operator>>(T &x) { char c = gc(); T f = 1; for (x = 0; !isdigit(c);) { if(c == '-') f = -1; c = gc(); } while (isdigit(c)) x = (x * 10) + (c ^ 48), c = gc(); x *= f; _r; } Fr &operator>>(char *s) { int l = 0; char c; operator>>(c); for (; !_b(c); s[l++] = c, c = gc()) ; s[l] = '\0'; _r; } Fr &operator>>(string &s) { s = ""; char c = gc(); while(_b(c)) c = gc(); while(!_b(c)) s += c, c = gc(); _r; } Fr &operator>>(double &x) { double t = 1, s = 0; char c = gc(); for (x = 0; !isdigit(c); c = gc()) s = (c == '-'); for (; isdigit(c); c = gc()) x = x * 10 + (c - 48); if (c == '.') for (c = gc(); isdigit(c); c = gc()) x += (t /= 10.0) * (c - 48), s && (x = -x); _r; } Fr &operator>>(char &c) { do c = gc(); while (_b(c)); _r; } } cin;
    struct Fw { void pt(char c) { *p++ = c; if (p - pb == S) Fl(); } template <class T> Fw &operator<<(T x) { if (!x) { pt(48); _r; } x < 0 && (pt('-'), x = -x); int s[64], t = 0; while (x) s[++t] = x % 10, x /= 10; while (t) pt(s[t--] + 48); _r; } Fw &operator<<(char c) { pt(c); _r; } Fw &operator<<(const char *s) { operator<<((char *)s); _r; } Fw &operator<<(char *s) { int c = 0; while (s[c]) pt(s[c++]); _r; } Fw &operator<<(double x) { int k = 0; x < 0 && (pt('-'), x = -x), ir && (x += 5 * pow(10, -dgt - 1)), operator<<(int(x)), pt('.'), x -= int(x); while (k++ < dgt) pt(int(x *= 10) + 48), x -= int(x); _r; } Fw &operator<<(string s) { for(int i = 0; s[i] != '\0'; ++i) pt(s[i]); _r; } ~Fw() { Fl(); } } cout;
    struct fileIO { fileIO() { freopen((name + "." + suf_in).c_str(), "r", stdin), freopen((name + "." + suf_out).c_str(), "w", stdout); } } ;
};
#define cin IO::cin
#define cout IO::cout
const int N=21;

int f[1<<N],g[1<<N]; 

int p[1<<N];

int n,q,ans;

string s;

char c;

void fwt(int f[],int n){
    for(int i=1;i<=n;i*=2){
        for(int j=0;j<n;j+=i*2){
            for(int k=j;k<j+i;k++)
            f[k+i]+=f[k];
        }
    }
}

void fwt1(int f[],int n){
    for(int i=1;i<=n;i*=2){
        for(int j=0;j<n;j+=i*2){
            for(int k=j;k<j+i;k++)
            f[k]+=f[k+i];
        }
    }
}

void dfs2(int u,int k){
    if(u==n){
        ans+=p[k];return ;
    }
    if(s[u]=='?'){
        dfs2(u+1,k);
        dfs2(u+1,k+(1<<u));
    }
    if(s[u]=='1')dfs2(u+1,k+(1<<u));
    if(s[u]=='0')dfs2(u+1,k);
}

void dfs0(int u,int k,int o){
    if(u==n){
        ans+=g[k]*o;return ;
    }
    if(s[u]=='0'){
        dfs0(u+1,k,o);
        dfs0(u+1,k+(1<<u),-1*o);
    }
    if(s[u]=='1')dfs0(u+1,k+(1<<u),o);
    if(s[u]=='?')dfs0(u+1,k,o);
}

void dfs1(int u,int k,int o){
    if(u==n){
        ans+=f[k]*o;return ;
    }
    if(s[u]=='1'){
        dfs1(u+1,k,-1*o);
        dfs1(u+1,k+(1<<u),o);
    }
    if(s[u]=='0')dfs1(u+1,k,o);
    if(s[u]=='?')dfs1(u+1,k+(1<<u),o);
}

signed main() {
    cin>>n>>q;
    for(int i=0;i<(1<<n);i++){
        cin>>c; 
        p[i]=c-'0';f[i]=p[i];g[i]=p[i];
    }
    fwt(f,1<<n);fwt1(g,1<<n);
    while(q--){
        cin>>s;ans=0;
        reverse(s.begin(),s.end()); 
        int a=0,b=0,c=0;
        for(char c1:s){
            if(c1=='0')a++;
            else if(c1=='1')b++;
            else c++;
        }int mn=min({a,b,c});
        if(mn==c)dfs2(0,0);
        else if(mn==a)dfs0(0,0,1);
        else if(mn==b)dfs1(0,0,1);
        cout<<ans<<"\n";
    }
    return 0;
}