acm位运算应用 搜索

时间:2023-03-08 15:41:24
acm位运算应用 搜索

acm位运算应用 搜索

搜索
 
  此处不讲题目,只讲位运算是怎样在这些题中实现和应用的。由于搜索题往往是基于对状态的操作,位运算往往特别有效,优化之后的效果可以有目共睹。
 
  例1、POJ 1324
 
  根据题目,确定了对状态的表示之后(记录当前状态的蛇头x, y值与剩下部分的运动状态),一般容易想到剩下部分的运动状态用一个数组(比如x[n-1], n为蛇节点数,n[0]为第二个节点的运动趋势)去表示,且一个数组元素的值为0,1,2,3,即四个方向,蛇每次移动,这个方向数组需要更新一次,更新是很简单的,除了n[0]更新之外,剩下的 n等于上一轮的n[i-1](i>1);如果用数组,就必须用一个循环去更新它,这样会导致程序速度不是很理想,所以可以想到用位运算去模拟,简言之,就是把原来的一个数组压缩的一个变量上去存储,原来任何一个数组元素的值范围0~3, 用二进制表示就是 00 ~ 11,最多占用2位,这样,我们就可以通过移位运算,和或运算去实现所以操作。
 
  基本技巧: 如果给你个一个方向序列   a0, a1, a2, a3, .... a(n-1),放到变量b中,且以最低位表示an,可以用如下循环
 
  b = 0;
 
  for(i=0; i<n; i++)
 
       b = (b<<2) | a;
 
  即,每次把已经处理好的位段向上移两位,这样,在低位就会自动补齐两个0,用一个 | 操作,就吧新的值给放进变量中了。
 
  如果要从b中复原,则可使用 >> 的办法
 
  for(i=0; i<n; i++)
 
         a[n-1-i] = (b >> (i*2)) & 3;
 
  移位会将低位元素除掉,而 & 3则是把移到低位的元素取出。
 
  更高效的方法是(两种方法的前提都是不改变b的值)
 
  t = b;
 
  for(i=0; i<n; i++){
 
      a[n-1-i] = t & 3;
 
      t >>= 2;
 
  }
 
  高效的原因如帖子开头所述。
 
  在表示状态的位段操作中,最好将变量设为unsigned int (short)型,因为有符号型(负数的最高位(符号位)为1)的 >>操作加在负数上时会在右边引入1而不是0, 这基本上不会是你想要的操作。
 
  例2、POJ 3460 Booksort
 
  这题可以在对书进行交换的时候应用位运算,也许你认为用数组去模拟更为直观,但是看看下面的实现,也许你就不那么认为了。
 
  书最大编号15,
 
  这样就开一个64位整形,每4位表示一本书
 
  首先预处理,计算出两张表
 
  extract[j] 和 clear[j]分别表示把书架上第i到j本书取出或清空,显然在i到j一段,位上全是1,而其他部分是0,而clear[j]就是extract[j]的取反
 
  计算方法如下:
 
  typedef unsigned long long longint;
 
  const longint base = 15;//这是必须注意的,普通的常数15是整形,在以下的操作中会越界
 
  for (i = 0; i < 15; i++) {
 
     extract = base << (i * 4);
 
     clear = ~extract;
 
     for (j = i + 1; j < 15; j++) {
 
      extract[j] = extract[j-1] | (base << (j * 4));
 
      clear[j] = ~extract[j];
 
     }
 
  }
 
  计算出这些以后,交换书就变得异常简单
 
  inline void transposition(longint &cur, longint &next, int &i,   int &k, int &j) {//i,k段与k+1,c段置换
 
  next = cur & clear[j];
 
  next |= (cur & extract[k]) << ((j - k) << 2);
 
  next |= (cur & extract[k+1][j]) >> ((k - i + 1) << 2);
 
  }
 
  先把i到j全部清空后的值赋给next,把 i, k段的书取出,移到高位(差值为(j - k) * 4),同理,再把k+i到j段的值取出移到低位。
 
  如此清楚明了,而如果用数组的话,10+行的语句是少不了的,而且容易搞错。
 
  例3:HOJ 八数码问题
 
  http://acm.hnu.cn:8080/online/?action=problem&type=show&id=10466
 
  这题用位运算我倒是没有达到更快,空间稍微节省了些。
 
  另外,这题的测试数据很强的说,赞一个。
 
  用64位的整形去表示整个状态,其中每4位表示一个数码(0~8),如果是用char数组,则用9个,用了72位。
 
  取出某一位和清空某一位的掩码事先要计算好
 
  这样做比用一个整形数如 123480567 之类的去表示更有优势,因为显然取出某一位的速度非常快,不需要 % 10, /10之类耗时的操作,如果这样实现的话就不要用stl的map了,我无聊地试了次,相当之慢。还是老老实实康托展开的好。不过和开char数组的速度差不多的说(虽然说赋值时间大了,但毕竟别人是数组,呵呵,要是有每4位做一个单位的数组就好了——不要跟我说用struct里面定义的位段啊,那相当的慢)。
 
  最近还做了一个POJ 2286,可以用位运算,但貌似有些麻烦,没用,结果被一个用pascal的小子超在前面,哪天状态好了要把这题改用位运算去做,就不信刷不到   0ms.