hdu 4712 Hamming Distance bfs
2024-10-13 01:20:30
我的做法,多次宽搜,因为后面的搜索扩展的节点会比较少,所以复杂度还是不需要太悲观的,然后加上一开始对答案的估计,用估计值来剪枝,就可以ac了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char a[11];
int key[111111];
int hash[1111111];
int que[2111111];
int front,end;
int ans;
void bfs()
{
while(front<=end)
{
int now=que[front++];
if(hash[now]>=ans) continue;
for(int i=0;i<=19;i++)
{
int to=(now^(1<<i));
if(hash[to]>hash[now]+1)
{
hash[to]=hash[now]+1;
que[++end]=to;
}
}
}
} int cal(int t,int s)
{
int sum=0;
for(int i=0;i<=19;i++)
{
int tmp=key[t]&(1<<i);
int txt=key[s]&(1<<i);
if(tmp^txt)
sum++;
}
return sum;
} int main()
{
// freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
memset(hash,1,sizeof(hash));
ans=33;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=5;j++)
{
scanf("%c",&a[j]);
if(a[j]==' '||a[j]=='\n')
j--;
}
int txt=1,sum=0;
for(int j=1;j<=5;j++)
{
if(a[j]>='0'&&a[j]<='9')
sum+=(a[j]-'0')*txt;
else
sum+=(a[j]-'A'+10)*txt;
txt*=16;
}
key[i]=sum;
}
sort(key+1,key+1+n);
for(int i=1;i<n;i++)
ans=min(ans,cal(i,i+1)); for(int i=1;i<=n;i++)
{
ans=min(ans,hash[key[i]]);
front=1,end=0;
que[++end]=key[i];
hash[key[i]]=0;
bfs();
} cout<<ans<<endl;
}
return 0;
}
最新文章
- [Android]listview recycleview的复用问题
- WCF初探-1:认识WCF
- LeetCode Integer to English Words
- python实现删除文件与目录的方法
- 关于Android的onResume的2点体会(程序切换之后恢复状态)
- js上移、下移、置顶、置底功能实现
- Day1_算法分析方法
- UIStepper使用的具体解释的控制
- linux添加到普通用户sudo才干
- iptables惹的祸
- 内Cool超人
- NodeJs的包漏洞扫描与漏洞测试攻击
- 如何生成Azure SAS Token
- 基于DPDK的高效包处理系统
- Unity3D 中 脚本(MonoBehaviour) 生命周期WaitForEndOfFrame需要注意的地方
- python接口自动化测试(二)-requests.get()
- 文件操作_26th,Nov 2018
- CentOS7.1下生产环境Keepalived+Nginx配置
- 解决vue不相关组件之间的数据传递----vuex的学习笔记,解决报错this.$store.commit is not a function
- MapReduce详解和WordCount模拟
热门文章
- 为什么要用BASE64
- php 父类子类构造函数注意事项
- php 解析url 和parse_url使用
- 上海投行需要一大群JAVA,C++,C#,UNIX.走过路过不要错过!过完年想换工作看过来初级资深都有 - V2EX
- Java字符串排序中文+数字
- [产值分析]生产部KPI考核之产值分析
- 数据库迁移 - SQLServer->;MySQL
- 关于页ASP.NET面布局
- iOS 7 - Auto Layout on iOS Versions prior to 6.0
- 高级UIKit-10(UDPSocket)