注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ2133Cow Imposters题解  

2014-03-18 14:58:35|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                          制造号码
                                                 BY   LGS
题目大意:给你一个2进制目标串和N个可以操作的同样长度的串,求通过XOR操作串得到最优串(定义为与目标串的差异最小)。

题解:题目中要求相同的差异下步数最小,那么搜索一定选择BFS。因为状态数才2^16=65536,所以数组和时间上都可以容纳。注意,一定不会有答案是0的步数的,即使操作串中有目标串也要2个步数才行。

总结:没有数据A太难了,有一些BUG。
代码:
#include<cstdio>
#include<cstring>
#define maxx 99999999
using namespace std;
int i,j,n,e,d,x,flag,t,h,f[70000],a[200],ans,bu,zhi,anss[20],
 queue[70000];
bool hash[70000];
char c;
int wys(int x)
 {
x=(x&0x55555555)+((x>>1)&0x55555555); 
x=(x&0x33333333)+((x>>2)&0x33333333); 
x=(x&0x0F0F0F0F)+((x>>4)&0x0F0F0F0F); 
x=(x&0x00FF00FF)+((x>>8)&0x00FF00FF); 
x=(x&0x0000FFFF) + ((x>>16)&0x0000FFFF); 
return x;
 }//二进制位运算算X中1的个数。X必须是32为整数。
int main()
{
 scanf("%d%d",&e,&n);flag=0;c=getchar();
 for (i=1;i<=e;i++)
  {c=getchar();flag=(flag<<1)+(c-48);}
  c=getchar();
for (i=1;i<=n;i++){
              t=0;
         for (j=1;j<=e;j++)
                   {c=getchar();t=(t<<1)+(c-48);}
          a[i]=t;c=getchar();
                  }
for (i=1;i<=n;i++) queue[i]=a[i];  //队列初始。
t=0;h=n;
while (t<h){
      int w=queue[++t];
      for (i=1;i<=n;i++)if (!hash[w^a[i]])
                     {
                     hash[w^a[i]]=true;
                     queue[++h]=w^a[i];
                     f[queue[h]]=f[queue[t]]+1;
                      } 
            }//BFS

ans=maxx;bu=maxx;zhi=maxx;
for (i=0;i<=65537;i++)if (f[i]!=maxx&&f[i]!=0)//不能等于0  
                          {
                          x=i^flag;
                          int tem=wys(x);
if ((ans>tem)||((ans==tem)&&(f[i]<bu))||
((ans==tem)&&(f[i]==bu)&&(zhi>i))) {ans=tem;bu=f[i];zhi=i;}
                          }//对题目中的输出判断
printf("%d\n",bu);int t=0;
while (zhi){
           t++;
           anss[t]=zhi%2;zhi=zhi>>1; 
           }
for (int i=e;i;i--) printf("%d",anss[i]);//for(;;);
return 0;        //输出
}
  评论这张
 
阅读(614)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018