team2012-E1-mysol-0003

从 Trac 迁移的文章

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

原文章内容如下：

{{{
/* 解题报告 //

给出 k 个 n 位的编码，对于每次询问，判断是否能组合成所询问的编码
组合意味着选取一些编码（可以重复）进行异或操作，并可产生至多三个错误位

首先，题目要求是『用 k 个码组合成一个码』，这一点可以令人想到线性组合
确切地说，这题本质是在一个模 2 的线性空间上的，判定线性方程是否有解的题

如果能想到上面那点，做法就容易想到了：对 k 个码进行高斯消元
就只会剩下至多 n 个码，每位最多有一个代表元

对于输入的码，枚举错误的位数和错误的位置，对于枚举的每种情况，进行判定
判定方法则是扫一下每一位，如果这一位是 1，则用相应的代表元去异或

扫完后，如果剩下的值非零，那么对于枚举的这种情况，线性方程是无解的
另外，在枚举时注意一下顺序关系（先0后1），就可以找到字典序最小的解了

// By 猛犸也钻地 @ 2012.07.18 */
}}}

{{{
#include <cstdio>
#include <algorithm>
using namespace std;

int getcode(){
    char s[35];
    scanf("%s",s);
    int ret=0;
    for(int i=0;s[i];i++) ret|=(s[i]-'0')<<i;
    return ret;
}

int a[20000],u[30],ans;

int guass(int n, int m){
    int ret=0;
    for(int x=0;x<m;x++){
        int i=ret;
        while(i<n && ~a[i]&1<<x) i++;
        if(i==n) continue;
        u[x]=a[i];
        swap(a[i],a[ret++]);
        for(i=ret;i<n;i++) if(a[i]&1<<x) a[i]^=u[x];
    }
    return ret;
}

bool check(int x, int m, int c, int i = 0){
    if(!c){
        ans=x;
        for(int i=0;i<m;i++) if(x&1<<i) x^=u[i];
        return !x;
    }
    if(i>=m) return false;
    if(x&1<<i){
        if(check(x^(1<<i),m,c-1,i+1)) return true;
        if(check(x,m,c,i+1)) return true;
    }else{
        if(check(x,m,c,i+1)) return true;
        if(check(x^(1<<i),m,c-1,i+1)) return true;
    }
    return false;
}

int main(){
    int n,m,ask;
    while(scanf("%d%d%d",&m,&n,&ask)==3){
        for(int i=0;i<m;i++) u[i]=0;
        for(int i=0;i<n;i++) a[i]=getcode();
        n=guass(n,m);
        while(ask--){
            int x=getcode(),c;
            for(c=0;c<=3;c++) if(check(x,m,c)) break;
            if(c<4){
                for(int i=0;i<m;i++) putchar(ans&1<<i?'1':'0');
                puts("");
            }else{
                puts("NA");
            }
        }
    }
}
}}}

/* 解题报告 //
给出 k 个 n 位的编码，对于每次询问，判断是否能组合成所询问的编码
组合意味着选取一些编码（可以重复）进行异或操作，并可产生至多三个错误位
首先，题目要求是『用 k 个码组合成一个码』，这一点可以令人想到线性组合
确切地说，这题本质是在一个模 2 的线性空间上的，判定线性方程是否有解的题
如果能想到上面那点，做法就容易想到了：对 k 个码进行高斯消元
就只会剩下至多 n 个码，每位最多有一个代表元
对于输入的码，枚举错误的位数和错误的位置，对于枚举的每种情况，进行判定
判定方法则是扫一下每一位，如果这一位是 1，则用相应的代表元去异或
扫完后，如果剩下的值非零，那么对于枚举的这种情况，线性方程是无解的
另外，在枚举时注意一下顺序关系（先0后1），就可以找到字典序最小的解了
// By 猛犸也钻地 @ 2012.07.18 */

#include <cstdio>
#include <algorithm>
using namespace std;
int getcode(){
    char s[35];
    scanf("%s",s);
    int ret=0;
    for(int i=0;s[i];i++) ret|=(s[i]-'0')<<i;
    return ret;
}
int a[20000],u[30],ans;
int guass(int n, int m){
    int ret=0;
    for(int x=0;x<m;x++){
        int i=ret;
        while(i<n && ~a[i]&1<<x) i++;
        if(i==n) continue;
        u[x]=a[i];
        swap(a[i],a[ret++]);
        for(i=ret;i<n;i++) if(a[i]&1<<x) a[i]^=u[x];
    }
    return ret;
}
bool check(int x, int m, int c, int i = 0){
    if(!c){
        ans=x;
        for(int i=0;i<m;i++) if(x&1<<i) x^=u[i];
        return !x;
    }
    if(i>=m) return false;
    if(x&1<<i){
        if(check(x^(1<<i),m,c-1,i+1)) return true;
        if(check(x,m,c,i+1)) return true;
    }else{
        if(check(x,m,c,i+1)) return true;
        if(check(x^(1<<i),m,c-1,i+1)) return true;
    }
    return false;
}
int main(){
    int n,m,ask;
    while(scanf("%d%d%d",&m,&n,&ask)==3){
        for(int i=0;i<m;i++) u[i]=0;
        for(int i=0;i<n;i++) a[i]=getcode();
        n=guass(n,m);
        while(ask--){
            int x=getcode(),c;
            for(c=0;c<=3;c++) if(check(x,m,c)) break;
            if(c<4){
                for(int i=0;i<m;i++) putchar(ans&1<<i?'1':'0');
                puts("");
            }else{
                puts("NA");
            }
        }
    }
}