[ 杂题 ] Codeforces949E Binary Cards

发现答案中每个二进制数最多只会出现一次。然后暴搜，过程中记下还有哪些数要表示,剪个枝就好了。

最多跑 219 2 19 次。

#include<bits/stdc++.h>
using namespace std;
const int M=;
int k,n,m,x;
bool a[M][<<M];
int c[M];
vector<int>cur,Ans;
void Dfs(int x) {
    int l=-c[x],r=c[x],val=c[x];
    bool fl=;
    for(int i=l;i<=r;i++)
        if(i && a[x][i+val]) {
            fl=;
            break;
        }
    if(!fl) {
        if(cur.size()<Ans.size()) Ans=cur;
        return;
    }
    if(x==M-) return;
    fl=;
    for(int i=l;i<=r;i++) 
        if((i&) && a[x][i+val]) {
            fl=;
            break;
        }
    if(!fl) {
        for(int i=l/;i<=r/;i++) a[x+][i+c[x+]]=;
        for(int i=l;i<=r;i++) if(a[x][i+val]) a[x+][i/+c[x+]]=;
        Dfs(x+);
    } else {
        for(int i=l/;i<=r/;i++) a[x+][i+c[x+]]=;
        for(int i=l;i<=r;i++) if(a[x][i+val]) a[x+][(i&?(i-)/:i/)+c[x+]]=;
        cur.push_back(<<x);
        Dfs(x+);
        cur.pop_back();
        for(int i=l/;i<=r/;i++) a[x+][i+c[x+]]=;
        for(int i=l;i<=r;i++) if(a[x][i+val]) a[x+][(i&?(i+)/:i/)+c[x+]]=;
        cur.push_back(-(<<x));
        Dfs(x+);
        cur.pop_back();
    }
}
int main() {
    scanf("%d",&n);
    c[M-]=;
    for(int i=M-;i>=;i--) c[i]=c[i+]<<;
    for(int i=;i<=n;i++) {
        scanf("%d",&x);
        if(x) a[][x+c[]]=;
    }
    for(int i=;i<=;i++)Ans.push_back();
    Dfs();
    cout<<Ans.size()<<endl;
    for(int i=;i<Ans.size();i++) printf("%d ",Ans[i]);
    return ;
}