题意分析

农夫FJ不再使用烙印的方式标记奶牛，而是为每头奶牛创建一个长度为 B（1 ≤ B ≤ 16）位的二进制代码，并将其印在金属条上系在奶牛耳朵上。现在奶牛们收留了一头流浪牛，它们有一台机器可以通过异或（XOR）操作，利用现有的 E（1 ≤ E ≤ 100）个二进制代码条来为流浪牛创建一个新的代码条。

目标是根据给定的 E 个现有代码条和一个目标代码条，使用异或操作生成一个新的代码条，使其与目标代码条的差异（不同位的数量）尽可能小。如果有多个代码条与目标代码条的差异相同，则选择生成步骤最少的；若步骤数也相同，则选择数值最小的代码条。

输入包括：

• 第一行：两个整数 B 和 E，分别表示二进制代码的长度和现有代码条的数量。
• 第二行：目标二进制代码条，由 B 个 0 和 1 组成。
• 接下来的 E 行：每行包含一个现有的二进制代码条，同样由 B 个 0 和 1 组成。

输出包括：

• 第一行：生成最佳代码条所需的最少步骤数。
• 第二行：使用 E 个现有代码条生成的最佳代码条。

解题思路

1. 数据预处理：
   • 把输入的二进制字符串转换为对应的十进制整数，便于后续操作。
   • 存储目标代码条和所有现有代码条。
2. 广度优先搜索（BFS）：
   • 运用 BFS 算法，借助现有的代码条进行异或操作，生成所有可能的代码条。
   • 记录每个生成的代码条所需的步骤数。
3. 寻找最优解：
   • 计算每个生成的代码条与目标代码条的差异（不同位的数量）。
   • 挑选差异最小的代码条。若存在多个差异相同的代码条，则选择步骤数最少的；若步骤数也相同，则选择数值最小的代码条。
4. 输出结果：
   • 输出生成最优代码条所需的最少步骤数。
   • 输出最优代码条的二进制表示。

算法标签

• 广度优先搜索（BFS）：用于生成所有可能的代码条，并记录每个代码条的生成步骤数。
• 位运算：使用异或（XOR）操作生成新的代码条，以及计算两个代码条之间的差异。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[20];
int n,m;
int goal;
int dp[70000],turn[111];
int que[70000];
bool text[70000];
void bfs()
{
    memset(text,0,sizeof(text));
    int front=1,end=0;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++)
    {
        que[++end]=(turn[i]^turn[j]);
        text[turn[i]^turn[j]]=1;
        dp[turn[i]^turn[j]]=1;
    }
    while(front<=end)
    {
        int tmp=que[front++];
        for(int i=1;i<=m;i++)
        if(!text[turn[i]^tmp])
        {
            text[turn[i]^tmp]=1;
            dp[turn[i]^tmp]=dp[tmp]+1;
            que[++end]=(turn[i]^tmp);
        }
    }
}
 
int cal(int a,int b)
{
    int tmp=(a^b),ret=0;
    while(tmp)
    {
        ret+=(tmp&1);
        tmp/=2;
    }
    return ret;
}
 
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(dp,50,sizeof(dp));
        scanf("%s",a+1);
        int sum=0;
        for(int i=n,tmp=1;i>=1;i--)
        {
            sum+=(a[i]-'0')*tmp;
            tmp*=2;
        }
        goal=sum;
        for(int i=1;i<=m;i++)
        {
            scanf("%s",a+1);
            sum=0;
            for(int j=n,tmp=1;j>=1;j--)
            {
                sum+=tmp*(a[j]-'0');
                tmp*=2;
            }
            turn[i]=sum;
        }
        bfs();
        int ans=11111111,id;
        for(int i=0;i<70000;i++)
        if(dp[i]<111111111)
        if(cal(i,goal)<ans)
        {
            ans=cal(i,goal);
            id=i;
        }
        else if(cal(i,goal)==ans)
        {
            if(dp[i]<dp[id])
            {
                id=i;
            }
        }
        cout<<dp[id]<<endl;
        int s[20],lon=0;
        while(id)
        {
            s[++lon]=id%2;
            id/=2;
        }
        for(int i=lon+1;i<=n;i++)
        printf("0");
        for(int i=lon;i>=1;i--)
        printf("%d",s[i]);
        printf("\n");
    }
    return 0;
}