Description

已知有$N(N≤14)$个变量,变量取值0或1。
已知$f(0,0,⋯,0),⋯,f(1,1,⋯,1)$的函数值。
对于每种输入$x=(x_0,x_1,⋯,x_n)$,求最少需要知道几个变量的值即可确定函数值。
举个例子:假设有两个变量,函数$f(a,b)=a\&b$,那么对于$f(x)=0$,我们只要知道其中一个变量为0即可确定函数值为0,否则我们需要知道两个变量是否都为1,才能确定函数值为1。

Solution

可以先$2^N$枚举选出的t个关键问题,再$2^N$判断,复杂度为$4^N$,可以勉强卡过。

上代码:

#include<bits/stdc++.h>
#define maxn 16
using namespace std;
int ans[1<<maxn],check[1<<maxn],n,a[1<<maxn];
char s[1<<maxn];
int calc(int x){
    int cnt=0;
    while(x){
        cnt++;
        x-=x&(-x);
    }
    return cnt;
}
void init(){
    scanf("%d",&n);
    int all=1<<n;
    scanf("%s",s);
    memset(ans,0x3f,sizeof(ans));
    for(int i=0;s[i];i++) a[i]=(s[i]=='0'?0:1);
    for(int i=0;i<all;i++){
        memset(check,-1,sizeof(check));
        for(int j=0;j<all;j++){
            if(check[i&j]==-1) check[i&j]=a[j];
            else if(check[i&j]!=a[j]) check[i&j]=2;
        }
        int len=calc(i);
        for(int j=0;j<all;j++) if(check[i&j]==a[j]) ans[j]=min(ans[j],len);
    } 
    for(int i=0;i<all;i++) printf("%d ",ans[i]);
}
int main(){
    init();
    
    return 0;
}
Last modification:February 15th, 2019 at 09:58 pm