首页 > 代码库 > hdu 5077 NAND(打表)2014 Asia regional 鞍山站 H题
hdu 5077 NAND(打表)2014 Asia regional 鞍山站 H题
题目链接:点击打开链接
题意:就是一个按位运算的一个函数,问最少经过多少步运算可以得到给定数;
思路:不是我投机取巧想打表,是特么这题只能打表。。。打表思想用可以得到的数的集合表示状态bfs;最后有一个需要11步的需要打将近1h,除去这一个十分钟就够了。
cpp:
#include <cstdio> #include <cstring> #include <queue> #include <vector> #include <map> using namespace std; int mark[300]; struct node{ int deep; vector <int> us; void init(){ deep=0; us.push_back(15); us.push_back(51); us.push_back(85); us.push_back(0); us.push_back(255); } bool find(int n){ for(int i=0;i<us.size();i++) if(us[i]==n) return 1; return 0; } }; int Nand(int a,int b){ return (255^(a&b)); } queue <node> Q; map<vector<int>,bool> Map; //打出全部表版本的check bool check(){ int bj=1; for(int i=0;i<256;i++){ if(mark[i]<0) { bj=0; } } if(bj) for(int i=0;i<256;i++){ printf("%d , ",mark[i]); } return bj; } //留下最后一个数不打的check版本 bool check(){ int cnt=0; for(int i=0;i<256;i++){ if(mark[i]<0) { cnt++; } } if(cnt<2) for(int i=0;i<256;i++){ printf("%d , ",mark[i]); } return (cnt<2); } void bfs(){ node tpe; tpe.init(); Q.push(tpe); for(int i=0;i<5;i++) { mark[tpe.us[i]]=0; } while (!check()){ node tp=Q.front(); Q.pop(); for(int i=0;i<tp.us.size();i++){ for(int j=0;j<tp.us.size();j++){ int temp=Nand(tp.us[i],tp.us[j]); if(mark[temp]<0) mark[temp]=tp.deep+1; if(!tp.find(temp)){ node he=tp; he.deep++; he.us.push_back(temp); sort(he.us.begin(),he.us.end()); if(Map[he.us]==1) continue; Map[he.us]=1; Q.push(he); } } } } } int main(){ for(int i=0;i<256;i++) mark[i]=-1; bfs(); return 0; }
hdu 5077 NAND(打表)2014 Asia regional 鞍山站 H题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。