IAML's Blog

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

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

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

文章出处：http://hunteagle.javaeye.com

注：最近因为在做和hash有关的题目，感到很纠结。虽然上学期数据结构学过，但是当时觉得hash没什么用，所以没有认真学～后悔啊～～～现在恶补一下～

计算理论中，没有Hash函数的说法，只有单向函数的说法。所谓的单向函数，是一个复杂的定义，大家可以去看计算理论或者密码学方面的数据。用“人 类”的语言描述单向函数就是：如果某个函数在给定输入的时候，很容易计算出其结果来；而当给定结果的时候，很难计算出输入来，这就是单项函数。各种加密函 数都可以被认为是单向函数的逼近。Hash函数（或者成为散列函数）也可以看成是单向函数的一个逼近。即它接近于满足单向函数的定义。

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

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

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