[usaco2003feb]impster

FJ再也不用野蛮的方式为自己的奶牛编号了。他用一个B（1<=B<=16）位二进制编码给每头奶牛编号，并刻在奶牛耳朵上的金属条上。
奶牛希望自己给自己选择一个编码。于是，瞒着FJ，他们制造了一台机器。它可以在两个已经存在的ID之间进行XOR运算。
奶牛们希望用这台机器制造一个他们想要的编码，如果做不到的话也要与目标相差最小（不同的二进制位最少的新ID）　　
给你一个已经存在的ID的集合（元素个数为E，1<=E<=100），目标ID。请你计算离目标ID相差最小的新ID。
如果有多个ID满足相差最小的条件，选择步数最少的那一个。如果还有多个，选择最小的那一个（奶牛至少要运行一次机器）。

这道题具有迷惑人心的力量~~ 个人感受

刚拿到题感到很难，因为需要控制的东西太多，然后又想到xor的一堆性质，把自己弄得一团乱麻后，仔细想了想，发现这是一道bfs（QAQ）;

但需要注意的一点是，如果有和最优编号直接相同的，题目上说的是一定会有操作，先要有一些对k，v，u的初始化，再bfs；

代码：（学校数据太水，一个有bug的代码直接过了）

提示：代码有bug；

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cstdlib>

 #include<ctime>

 #include<vector>

 #include<algorithm>

 #include<queue>

 #include<map>

 using namespace std;

 #define LL long long

 const int maxn=;

 int n,m;

 int a[maxn],A;

 char s[maxn];

 void ch(int &x){

     x=;

     for(int i=n-;i>=;i--){

         x=x<<;

         if(s[i]=='')x++;

     }

 }

 int q[<<],tail=,head=,f[<<];

 int v,k=,u=;//v记录最优的序列，k记录最优序列与v的差值,u记录步数；

 int col(int x){

     int sum=;

     for(int i=;i<n;i++){

         if((x^A)&(<<i))sum++;

     }

     return sum;

 }

 void bfs(){

     int x=;

     while(++head<=tail){

         if(q[head]==-){

             for(int i=;i<=m;i++)q[++tail]=a[i],f[a[i]]=;

             continue;

         }

         x=q[head];

         for(int i=;i<=m;i++){

             if(f[x^a[i]]>f[x]+)f[x^a[i]]=f[x]+,q[++tail]=x^a[i];

         }

     }

     int y;

     for(int i=;i<<<n;i++){

         if(f[i]==)continue;

         y=col(i);

         if(y==k&&f[i]<u){

             v=i,k=y,u=f[i];continue;

         }

         if(y<k){

             v=i,k=y,u=f[i];continue;

         }

     }

     string d="";

     for(int i=;i<n;i++){

         if(v&(<<i))d+='';

         else d+='';

     }

     cout<<u<<endl<<d<<endl;

 }

 void init(){

     scanf("%d%d",&n,&m);

     scanf("%s",s);

     ch(A);

     for(int i=;i<=m;i++){

         scanf("%s",s);

         ch(a[i]);

         if(a[i]==A){

             printf("%d\n%s\n",,s);//此处有bug，可能出现

             return;//操作一次得到最优编号的序列

         }

     }

     for(int i=;i<<<n;i++)f[i]=;

     q[++tail]=-;

     bfs();

 }

 int main(){

     freopen("1.in","r",stdin);

     freopen("1.out","w",stdout);

     init();

 }

巴特西

[usaco2003feb]impster

最新文章

热门文章