关键词：
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 long 13 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 %s ",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 }
[usaco15feb]censoring
DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情
洛谷p3663[usaco17feb]whydidthecowcrosstheroadiiis
P3663[USACO17FEB]WhyDidtheCowCrosstheRoadIIIS题目描述Whydidthecowcrosstheroad?Well,onereasonisthatFarmerJohn‘sfarmsimplyhasalotofroads,makingitimpossibleforhiscowstotravelaroundwithoutcrossingmanyofthem.为 查看详情
p2894[usaco08feb]酒店hotel
P2894[USACO08FEB]酒店Hotel题目描述ThecowsarejourneyingnorthtoThunderBayinCanadatogainculturalenrichmentandenjoyavacationonthesunnyshoresofLakeSuperior.Bessie,everthecompetenttravelagent,hasnamedtheBullmoose 查看详情
[bzoj2591][usaco2012feb]nearbycows
2591:[Usaco2012Feb]NearbyCowsTimeLimit:4Sec MemoryLimit:128MBSubmit:149 Solved:89[Submit][Status][Discuss]Description FarmerJohnhasnoticedthathiscowsoftenmovebetweennearbyfi 查看详情
bzoj3942:[usaco2015feb]censoring
3942:[Usaco2015Feb]CensoringTimeLimit: 10Sec MemoryLimit: 128MBSubmit: 404 Solved: 221[Submit][Status][Discuss]DescriptionFarmerJohnhaspurchasedasubscriptiont 查看详情
[usaco11feb]cowline
https://www.luogu.org/problem/show?pid=3014题目描述TheN(1<=N<=20)cowsconvenientlynumbered1...NareplayingyetanotheroneoftheircrazygameswithFarmerJohn.ThecowswillarrangethemselvesinalineandaskFarmerJo 查看详情
[usaco2015feb]censoring(代码片段)
A.Censoring题目描述FarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecon 查看详情
洛谷p3048[usaco12feb]牛的idcowids
P3048[USACO12FEB]牛的IDCowIDs题目描述Beingasecretcomputergeek,FarmerJohnlabelsallofhiscowswithbinarynumbers.However,heisabitsuperstitious,andonlylabelscowswithbinarynumbersthathaveexactlyK"1"bits(1<=K< 查看详情
洛谷p1607[usaco09feb]庙会班车fairshuttle
P1607[USACO09FEB]庙会班车FairShuttle题目描述AlthoughFarmerJohnhasnoproblemswalkingaroundthefairtocollectprizesorseetheshows,hiscowsarenotinsuchgoodshape;afulldayofwalkingaroundthefairleavesthemexhausted.Tohel 查看详情
[usaco13feb]出租车taxi(代码片段)
洛谷题目链接:[USACO13FEB]出租车Taxi题目描述Bessieisrunningataxiservicefortheothercowsonthefarm.ThecowshavebeengatheringatdifferentlocationsalongafenceoflengthM(1<=M<=1,000,000,000).Unfortunately,theyhavegrow 查看详情
洛谷p3662[usaco17feb]whydidthecowcrosstheroadiis
P3662[USACO17FEB]WhyDidtheCowCrosstheRoadIIS题目描述ThelongroadthroughFarmerJohn‘sfarmhas NN crosswalksacrossit,convenientlynumbered 1ldotsN1…N (1leqNleq100,0001≤N≤100, 查看详情
[usaco2005feb]feedaccounting饲料计算
DescriptionFarmerJohnistryingtofigureoutwhenhislastshipmentoffeedarrived.Startingwithanemptygrainbin,heorderedandreceivedF1(1<=F1<=1,000,000)kilogramsoffeed.Regrettably,heisnotcertainexactlywhen 查看详情
bzoj3940[usaco2015feb]censoring
DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情
洛谷p2896[usaco08feb]一起吃饭eatingtogether
P2896[USACO08FEB]一起吃饭EatingTogether题目描述Thecowsaresoverysillyabouttheirdinnerpartners.Theyhaveorganizedthemselvesintothreegroups(convenientlynumbered1,2,and3)thatinsistupondiningtogether.Thetroublestar 查看详情
[usaco06feb]数字三角形
题目描述FJandhiscowsenjoyplayingamentalgame.Theywritedownthenumbersfrom1toN(1<=N<=10)inacertainorderandthensumadjacentnumberstoproduceanewlistwithonefewernumber.Theyrepeatthisuntilonlyasinglenumberi 查看详情
bzoj1651:[usaco2006feb]stallreservations专用牛棚
二次联通门: BZOJ1651:[Usaco2006Feb]StallReservations专用牛棚 权限题放题面DescriptionOhthosepickyN(1<=N<=50,000)cows!TheyaresopickythateachonewillonlybemilkedoversomeprecisetimeintervalA.. 查看详情
洛谷p3045[usaco12feb]牛券cowcoupons
P3045[USACO12FEB]牛券CowCoupons71通过248提交题目提供者洛谷OnlineJudge标签USACO2012云端难度提高+/省选-时空限制1s/128MB 提交 讨论 题解 最新讨论更多讨论86分求救题目描述FarmerJohnneedsnewcows!ThereareNcowsforsale(1 查看详情
洛谷p3047[usaco12feb]nearbycows(树形dp)
P3047[USACO12FEB]附近的牛NearbyCows题目描述FarmerJohnhasnoticedthathiscowsoftenmovebetweennearbyfields.Takingthisintoaccount,hewantstoplantenoughgrassineachofhisfieldsnotonlyforthecowssituatedinitiallyi 查看详情