频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 1830(位运算+双向DFS)
2012-09-01 11:31:48           
收藏   我要投稿

此题也可用GE做,可是我不会矩阵乘法……

[delphi
Program P1830; 
const 
   maxn=28; 
   maxf=100007; 
   none=-2139062144; 
var 
   ans,tt,n,i,j,s,t,mid:longint; 
   b:array[1..29] of longint; 
   h,num:array[0..maxf] of longint; 
 
function hash(x:longint):longint; 
var 
   i,j:longint; 
begin 
   hash:=x mod maxf; 
   while (num[hash]<>x) and (num[hash]<>none) do 
   begin 
      hash:=(hash+1) mod maxf; 
   end; 
   num[hash]:=x; 
   exit(hash); 
end; 
procedure dfs(x,l:longint); 
var 
   i,j:longint; 
begin 
   if l=mid+1 then 
   begin 
      inc(h[hash(x)]); 
      exit; 
   end; 
   for i:=l to mid do 
      dfs(x xor b[i],i+1); 
   dfs(x,mid+1); 
 
end; 
procedure find(x,l:longint); 
var 
   i,j:longint; 
begin 
   if l=n+1 then 
   begin 
      inc(ans,h[hash(x)]); 
      exit; 
   end; 
   for i:=l to n do 
      find(x xor b[i],i+1); 
   find(x,n+1); 
 
end; 
 
begin 
   read(tt); 
   while (tt>0) do 
   begin 
      ans:=0; 
      fillchar(b,sizeof(b),0); 
      fillchar(num,sizeof(num),128); 
      fillchar(h,sizeof(h),0); 
 
      read(n); 
      s:=0; 
      for i:=1 to n do 
      begin 
         read(j); 
         if j=1 then inc(s,1 shl (i-1)); 
      end; 
      t:=0; 
      for i:=1 to n do 
      begin 
         read(j); 
         if j=1 then inc(t,1 shl (i-1)); 
      end; 
      while (true) do 
      begin 
         read(i,j); 
         if (i=0) and (j=0) then break; 
         inc(b[i],1 shl (j-1)); 
      end; 
      for i:=1 to n do inc(b[i],1 shl (i-1)); 
      mid:=n shr 1; 
      dfs(s,1); 
      find(t,mid+1); 
      if ans=0 then writeln('Oh,it''s impossible~!!') else 
      writeln(ans); 
      dec(tt); 
   end; 
end. 

点击复制链接 与好友分享!回本站首页
相关TAG标签 双向
上一篇:出道题大家做做,C++的(含答案)
下一篇:消息队列学习小结
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站