team2012-F3-sol-0003
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
题意：给定k个长度为n的0-1向量作为码字，对于每个给出的询问，回答是否能用这些码字异或表示，且错误位少于3位
解法：这k个码进行任意的组合，形成一个线性空间，先求出这个空间的一组基，然后对于每个询问的码枚举错误位，再看是否能用基表示出来。
}}}
{{{
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, k, m, code[20005], base[40];
int tr(char* s)
{
int tmp = 0;
for(int j = 0; j < n; j++)
if(s[j] == '1')
tmp += (1<<(n-1-j));
return tmp;
}
void print(int x)
{
if(x==-1)
printf("NA\n");
else
{
for(int i=n-1;i>=0;i--)
if(x&(1<<i))
printf("1");
else
printf("0");
printf("\n");
}
}
void gao_ji()
{
int bs,
bs_ind[40] = {0},
bs_col[40] = {0};
bool sel[20005] = {0};
for(int i=n-1;i>=0;i--)
{
int find = 0;
for(int j=1;j<=k;j++)
if(!sel[j] && (code[j] & (1<<i)))
{
find = 1;
sel[j] = 1;
bs = code[j];
bs_ind[++bs_ind[0]] = j;
bs_col[++bs_col[0]] = i;
break;
}
if(find)
for(int j=1;j<=k;j++)
if((code[j]&(1<<i)) && j!=bs_ind[bs_ind[0]])
code[j] ^= bs;
}
memset(base, -1, sizeof(base));
for(int i=1;i<=bs_ind[0];i++)
base[bs_col[i]] = code[bs_ind[i]];
}
bool test(int x)
{
for(int i=n-1;i>=0;i--)
if(x&(1<<i))
{
if(base[i] == -1)
return 0;
x ^= base[i];
}
return 1;
}
int decode(int x)
{
if(test(x))
return x;
int ans = 0x7FFFFFFF,
err = 4;
for(int i=0;i<n;i++)
{
int t = x^(1<<i);
if(test(t))
if(err>1 || (err==1 && t<ans))
{
ans = t;
err = 1;
}
if(err >= 2)
for(int j=i+1;j<n;j++)
{
t = x^(1<<i)^(1<<j);
if(test(t))
if(err>2 || (err==2 && t<ans))
{
ans = t;
err = 2;
}
if(err >= 3)
for(int k=j+1;k<n;k++)
{
t = x^(1<<i)^(1<<j)^(1<<k);
if(test(t))
if(err>3 || (err==3 && t<ans))
{
ans = t;
err = 3;
}
}
}
}
if(err<=3)
return ans;
else
return -1;
}
int main()
{
while(~scanf("%d %d %d", &n, &k, &m))
{
memset(code, 0, sizeof(code));
for(int i = 1; i <= k; i++)
{
char str[40];
scanf("%s", str);
code[++code[0]] = tr(str);
}
memset(base, 0, sizeof(base));
gao_ji();
for(int i = 1; i <= m; i++)
{
char str[40];
scanf("%s", str);
int rec = tr(str),
ans = decode(rec);
print(ans);
}
}
return 0;
}
}}}题意：给定k个长度为n的0-1向量作为码字，对于每个给出的询问，回答是否能用这些码字异或表示，且错误位少于3位
解法：这k个码进行任意的组合，形成一个线性空间，先求出这个空间的一组基，然后对于每个询问的码枚举错误位，再看是否能用基表示出来。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, k, m, code[20005], base[40];
int tr(char* s)
{
int tmp = 0;
for(int j = 0; j < n; j++)
if(s[j] == '1')
tmp += (1<<(n-1-j));
return tmp;
}
void print(int x)
{
if(x==-1)
printf("NA\n");
else
{
for(int i=n-1;i>=0;i--)
if(x&(1<<i))
printf("1");
else
printf("0");
printf("\n");
}
}
void gao_ji()
{
int bs,
bs_ind[40] = {0},
bs_col[40] = {0};
bool sel[20005] = {0};
for(int i=n-1;i>=0;i--)
{
int find = 0;
for(int j=1;j<=k;j++)
if(!sel[j] && (code[j] & (1<<i)))
{
find = 1;
sel[j] = 1;
bs = code[j];
bs_ind[++bs_ind[0]] = j;
bs_col[++bs_col[0]] = i;
break;
}
if(find)
for(int j=1;j<=k;j++)
if((code[j]&(1<<i)) && j!=bs_ind[bs_ind[0]])
code[j] ^= bs;
}
memset(base, -1, sizeof(base));
for(int i=1;i<=bs_ind[0];i++)
base[bs_col[i]] = code[bs_ind[i]];
}
bool test(int x)
{
for(int i=n-1;i>=0;i--)
if(x&(1<<i))
{
if(base[i] == -1)
return 0;
x ^= base[i];
}
return 1;
}
int decode(int x)
{
if(test(x))
return x;
int ans = 0x7FFFFFFF,
err = 4;
for(int i=0;i<n;i++)
{
int t = x^(1<<i);
if(test(t))
if(err>1 || (err==1 && t<ans))
{
ans = t;
err = 1;
}
if(err >= 2)
for(int j=i+1;j<n;j++)
{
t = x^(1<<i)^(1<<j);
if(test(t))
if(err>2 || (err==2 && t<ans))
{
ans = t;
err = 2;
}
if(err >= 3)
for(int k=j+1;k<n;k++)
{
t = x^(1<<i)^(1<<j)^(1<<k);
if(test(t))
if(err>3 || (err==3 && t<ans))
{
ans = t;
err = 3;
}
}
}
}
if(err<=3)
return ans;
else
return -1;
}
int main()
{
while(~scanf("%d %d %d", &n, &k, &m))
{
memset(code, 0, sizeof(code));
for(int i = 1; i <= k; i++)
{
char str[40];
scanf("%s", str);
code[++code[0]] = tr(str);
}
memset(base, 0, sizeof(base));
gao_ji();
for(int i = 1; i <= m; i++)
{
char str[40];
scanf("%s", str);
int rec = tr(str),
ans = decode(rec);
print(ans);
}
}
return 0;
}