IAML's Blog

这题主要考的是对题目的理解。简单说说题意：fj有一些牛，那些牛有k个特点中的一个或者几个。现在要求从第i到j头牛中，满足每个属性的牛的数目都一样。

如果粗暴地枚举，肯定会超时。所以需要对问题进行转化。

题目转化如下：

（转自http://hi.baidu.com/aconly/blog/item/9d1ed1122a29af876538db0b.html）

很郁闷，在这样的水题上耗费了将近3个小时～看来我还是太水了～。这题基本上没什么技术含量，唯一一个难点不是算法，而是读入（主要是判断空行……）。之后把读入的两个数组放在hash中。这里用的hash函数是常用的ELFhash，虽然说这个函数能极大地避免重复映射，但是还是存在冲突的可能性，所以要注意写上冲突后的处理方法。之后就是读入要查找的字符串，然后在hash中查找（我就是这部分写得不够好，导致调试了n久……）

经过无数WA，TLE和一个诡异的CE之后，我终于把poj2002的时间由3300+MS刷到了735MS，虽然离最牛B的100+MS还有一段距离，不过能达到这个时间，我还是很高兴。这题其实思路不难，就是枚举两个点，然后把这两个点的连线作为正方形的一边，然后找能与这两个点构成正方形的另外两个点是否存在在给出的点集里面。在一个集合里面找点的方法有很多，比如二分搜索和hash都可以。当然，用hash肯定会快很多（前提是能很好的解决冲突问题）。

我提交的所有WA和一半的TLE，都是归功于基础不扎实，导致连个二分搜索都写不好……。PS：另一半TLE归功于hash写不好……

注：本解题报告里的有些思路不是由本人想出，是通过百度搜出来的。所以在此膜拜一下做出来的大牛们。

（个人认为）这是BFS的进阶题，以前做过的BFS都是按照操作一步步来，最终找出目标状态。这题巧妙的地方在于可以无视一些操作和把操作分类。比如说：光标左移是可以 无视的。因为光标移动是连续的，而且开始光标在最左边。也就是说，如果光标在第3个数的话，那么它一定经过0，1，2这几个位置。所以这时如果再考虑光标 左移是没有意义的。另外就是操作分类。所谓操作分类就是把操作分为两类（这两类分别对状态做出不同的影响）：一类移动光标，另一类就是直接把数加到目标状 态，要注意的地方是，只有光标经过的地方才能进行加减。

经典的搜索题，可以用BFS，双向BFS，A*算法来写。 用单向BFS写的话，和普通的BFS没什么两样。唯一要注意的就是要压缩状态，可以用康托展开（或者直接用逆序数）+hash来判重。这样一共有9！种状态，比10^9少得多。另外如果是多case的话，可以从目标状态（12345678x）开始，先预处理，这样会快点。