2012-A3-0003

从 Trac 迁移的文章

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

原文章内容如下：

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

xor空间显然是线性的，于是只要关于这K个数求出任意一组基，任意一组基的张成可以表示K个数的线性张成。

此题中可以规定基的每个分量的优先级，比如高位优先，就可以比较方便的实现求基和张成的操作。

{{{
#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned num;
num k,m,n;
num read(){
    static char buf[32];
    num ret =0;
    for(char* p=gets(buf);*p;++p)
        ret= ret<<1|(*p=='1');
    return ret;
}
void write(num x){
    for(num i=n;i--;)
        putchar(x>>i&1 ?'1':'0');
    putchar('\n');
}
struct{
    num base[32],cnt;
#define hi __builtin_clz
    bool test(num x){
        for(num i=0;i<cnt && x;++i)
            if(hi(x)==hi(base[i]) )x^=base[i];
        return x==0;
    }
    void span(num x){
        for(num i=0;i<cnt && x;++i)
            if(hi(x)==hi(base[i]))x^=base[i];
        if(x){
            base[cnt++]=x;
            for(num i=cnt-1;i;--i)
                if(base[i]>base[i-1])swap(base[i],base[i-1]);
                else break;
        }
    }
}xorbase;
int main(){
    for(;3==scanf("%u%u%u ",&n,&k,&m);){
        for(xorbase.cnt=0;k--;)
            xorbase.span(read());
        for(num x,a;m--;){
            x=read();a=~0;
            bool ok = false;
            if(xorbase.test(x)){
                write(x);continue;
            }
            for(num i=0;i<n;++i)
            if(xorbase.test(x^1<<i)){
                ok =1;
                a= min(a,x^1<<i);
            }
            if(ok){write(a);continue;}
            for(num i=0;i<n;++i)
                for(num j=i+1;j<n;++j)
                    if(xorbase.test(x^1<<i^1<<j)){
                    ok =1;
                    a= min(a,x^1<<i^1<<j);
                }
            if(ok){write(a);continue;}
            for(num i=0;i<n;++i)
                for(num j=i+1;j<n;++j)
                    for(num k=j+1;k<n;++k)
                    if(xorbase.test(x^1<<i^1<<j^1<<k)){
                        ok =1;
                        a= min(a,x^1<<i^1<<j^1<<k);
                    }
            if(ok)write(a);else puts("NA");
        }
    }
    return 0;
}
}}}

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

xor空间显然是线性的，于是只要关于这K个数求出任意一组基，任意一组基的张成可以表示K个数的线性张成。

此题中可以规定基的每个分量的优先级，比如高位优先，就可以比较方便的实现求基和张成的操作。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned num;
num k,m,n;
num read(){
    static char buf[32];
    num ret =0;
    for(char* p=gets(buf);*p;++p)
        ret= ret<<1|(*p=='1');
    return ret;
}
void write(num x){
    for(num i=n;i--;)
        putchar(x>>i&1 ?'1':'0');
    putchar('\n');
}
struct{
    num base[32],cnt;
#define hi __builtin_clz
    bool test(num x){
        for(num i=0;i<cnt && x;++i)
            if(hi(x)==hi(base[i]) )x^=base[i];
        return x==0;
    }
    void span(num x){
        for(num i=0;i<cnt && x;++i)
            if(hi(x)==hi(base[i]))x^=base[i];
        if(x){
            base[cnt++]=x;
            for(num i=cnt-1;i;--i)
                if(base[i]>base[i-1])swap(base[i],base[i-1]);
                else break;
        }
    }
}xorbase;
int main(){
    for(;3==scanf("%u%u%u ",&n,&k,&m);){
        for(xorbase.cnt=0;k--;)
            xorbase.span(read());
        for(num x,a;m--;){
            x=read();a=~0;
            bool ok = false;
            if(xorbase.test(x)){
                write(x);continue;
            }
            for(num i=0;i<n;++i)
            if(xorbase.test(x^1<<i)){
                ok =1;
                a= min(a,x^1<<i);
            }
            if(ok){write(a);continue;}
            for(num i=0;i<n;++i)
                for(num j=i+1;j<n;++j)
                    if(xorbase.test(x^1<<i^1<<j)){
                    ok =1;
                    a= min(a,x^1<<i^1<<j);
                }
            if(ok){write(a);continue;}
            for(num i=0;i<n;++i)
                for(num j=i+1;j<n;++j)
                    for(num k=j+1;k<n;++k)
                    if(xorbase.test(x^1<<i^1<<j^1<<k)){
                        ok =1;
                        a= min(a,x^1<<i^1<<j^1<<k);
                    }
            if(ok)write(a);else puts("NA");
        }
    }
    return 0;
}