首页 > 代码库 > [usaco2003feb]impster

[usaco2003feb]impster

2024-08-13 20:30:06   219人阅读

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；

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cstdlib> 6 #include<ctime> 7 #include<vector> 8 #include<algorithm> 9 #include<queue>10 #include<map>11 using namespace std;12 #define LL long long13 const int maxn=102;14 int n,m;15 int a[maxn],A;16 char s[maxn];17 void ch(int &x){18     x=0;19     for(int i=n-1;i>=0;i--){20         x=x<<1;21         if(s[i]==‘1‘)x++;22     }23 }24 int q[1<<20],tail=0,head=0,f[1<<17];25 int v,k=120,u=120;//v记录最优的序列，k记录最优序列与v的差值,u记录步数；26 int col(int x){27     int sum=0;28     for(int i=0;i<n;i++){29         if((x^A)&(1<<i))sum++;30     }31     return sum;32 }33 void bfs(){34     int x=0;35     while(++head<=tail){36         if(q[head]==-1){37             for(int i=1;i<=m;i++)q[++tail]=a[i],f[a[i]]=0;38             continue;39         }40         x=q[head];41         for(int i=1;i<=m;i++){42             if(f[x^a[i]]>f[x]+1)f[x^a[i]]=f[x]+1,q[++tail]=x^a[i];43         }44     }45     int y;46     for(int i=0;i<1<<n;i++){47         if(f[i]==120)continue;48         y=col(i);49         if(y==k&&f[i]<u){50             v=i,k=y,u=f[i];continue;51         }52         if(y<k){53             v=i,k=y,u=f[i];continue;54         }55     }56     string d="";57     for(int i=0;i<n;i++){58         if(v&(1<<i))d+=‘1‘;59         else d+=‘0‘;60     }61     cout<<u<<endl<<d<<endl;62 }63 void init(){64     scanf("%d%d",&n,&m);65     scanf("%s",s);66     ch(A);67     for(int i=1;i<=m;i++){68         scanf("%s",s);69         ch(a[i]);70         if(a[i]==A){71             printf("%d\n%s\n",2,s);//此处有bug，可能出现72             return;//操作一次得到最优编号的序列73         }74     }75     for(int i=0;i<1<<n;i++)f[i]=120;76     q[++tail]=-1;77     bfs();78 }79 int main(){80     freopen("1.in","r",stdin);81     freopen("1.out","w",stdout);82     init();83 }
View Code

 

[usaco2003feb]impster


联系
我们