prow2012-A3-0003

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意是求：给出K个N位的数，某个数能否被其中若干个数xor表示，如果不能修改1位或者2位或者3位表示出来，修改的越少越好，修改后的数越小越好，否则输出NA. (zz from zYc)



用类似高斯消元的方法去筛选异或基，对于每个x，用已有基的最高位1消去x的最高位1，如果最后剩余x非0，x加入基。

高效选取最高位1，我用的是二分法。

用dfs枚举C(N,3)，依次判断x是否能用基表达。

{{{
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
int nlz(unsigned x)
{
       int n;
          if (x == 0) return(32);
             n = 1;
                if ((x >> 16) == 0) {n = n +16; x = x <<16;}
                   if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
                      if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
                         if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
                            n = n - (x >> 31);
                               return n;
}
int T,base[100];
void add(int x){
    int i;
    for (i=T-1;x&&i>=0;i--)
        if (nlz(x)==nlz(base[i]))
            x^=base[i];
    if (x){
        base[T++] = x;
        sort(base,base+T);
    }
}
bool test(int x){
    int i;
    for (i=T-1;x&&i>=0;i--)
         if (nlz(x)==nlz(base[i]))
           x^=base[i];
    return x==0;
}
int N,M,K;
int Min,ans;
void dfs(int now,int sum,int num){
    if (now==N&&test(num)){
        //printf("%d %d\n",sum,num);
        if (sum<Min){
            Min = sum,ans = num;
        }else if (sum==Min&&ans>num){
            ans = num;
        }
    }
    if (sum>Min||now==N) return ;
    dfs(now+1,sum,num);
    if (sum+1<=3)
    dfs(now+1,sum+1,num^(1<<now));
}
int main(){
    char str[100];
    int i,j;
    while(scanf("%d%d%d",&N,&M,&K)!=EOF){
        T = 0;
        for (i=0;i<M;i++){
            scanf("%s",str);
            int x = 0;
            for (j=0;j<N;j++)
                x = (x<<1)+(str[j]=='1');
            add(x);
        }
        Min = 4,ans = 0;
        for (i=0;i<K;i++){
            int x = 0;
            scanf("%s",str);
            for (j=0;j<N;j++)
                x = (x<<1)+(str[j]=='1');
             Min = 4,ans = 0;

            dfs(0,0,x);
            if (Min==4) puts("NA");
            else {
                for (j=N-1;j>=0;j--)
                    printf("%d",((1<<j)&ans)>0);
                printf("\n");
            }
        }
    }
}
}}}

题意是求：给出K个N位的数，某个数能否被其中若干个数xor表示，如果不能修改1位或者2位或者3位表示出来，修改的越少越好，修改后的数越小越好，否则输出NA. (zz from zYc)

用类似高斯消元的方法去筛选异或基，对于每个x，用已有基的最高位1消去x的最高位1，如果最后剩余x非0，x加入基。

高效选取最高位1，我用的是二分法。

用dfs枚举C(N,3)，依次判断x是否能用基表达。

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
int nlz(unsigned x)
{
       int n;
          if (x == 0) return(32);
             n = 1;
                if ((x >> 16) == 0) {n = n +16; x = x <<16;}
                   if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
                      if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
                         if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
                            n = n - (x >> 31);
                               return n;
}
int T,base[100];
void add(int x){
    int i;
    for (i=T-1;x&&i>=0;i--)
        if (nlz(x)==nlz(base[i]))
            x^=base[i];
    if (x){
        base[T++] = x;
        sort(base,base+T);
    }
}
bool test(int x){
    int i;
    for (i=T-1;x&&i>=0;i--)
         if (nlz(x)==nlz(base[i]))
           x^=base[i];
    return x==0;
}
int N,M,K;
int Min,ans;
void dfs(int now,int sum,int num){
    if (now==N&&test(num)){
        //printf("%d %d\n",sum,num);
        if (sum<Min){
            Min = sum,ans = num;
        }else if (sum==Min&&ans>num){
            ans = num;
        }
    }
    if (sum>Min||now==N) return ;
    dfs(now+1,sum,num);
    if (sum+1<=3)
    dfs(now+1,sum+1,num^(1<<now));
}
int main(){
    char str[100];
    int i,j;
    while(scanf("%d%d%d",&N,&M,&K)!=EOF){
        T = 0;
        for (i=0;i<M;i++){
            scanf("%s",str);
            int x = 0;
            for (j=0;j<N;j++)
                x = (x<<1)+(str[j]=='1');
            add(x);
        }
        Min = 4,ans = 0;
        for (i=0;i<K;i++){
            int x = 0;
            scanf("%s",str);
            for (j=0;j<N;j++)
                x = (x<<1)+(str[j]=='1');
             Min = 4,ans = 0;
            dfs(0,0,x);
            if (Min==4) puts("NA");
            else {
                for (j=N-1;j>=0;j--)
                    printf("%d",((1<<j)&ans)>0);
                printf("\n");
            }
        }
    }
}