月度归档:2016年08月

八数码盲目搜素的两种方法

这段时间。。。一直在训练,天天被大佬虐,也没时间和心情写一点垃圾的东西。

课文资料

八数码问题其实可以A*之类的强力(玄学)搜索方法用估计函数解决。但是蒻还没学会A*,所以就先对应两道八数码问题写两种盲目搜索的方式。

其实八数码问题就相当于一个bfs的最短路问题,只不过现在bfs的时候我们需要把一个九宫格的数字映射成一个结点(而且不会和其他状态相同)。这就需要介绍一个康托展开的东西了:康托展开

其实这个东西就相当于当前排列,在所有的全排列中是第几小,从而完成映射(hash).然后按照这个定义就可以写出hash部分的代码了。

然后来看个题。

hdu 1043 Eight(逆向bfs+康托展开+打表)

这道题目是多组数据,而且需要我们打印路径,而如果我们对于每一个输入都进行一次bfs的话就会发现tle了。这是因为这道题目的目标状态是固定的,其实我们从一个状态到目标状态的过程中是会经历很多重复的状态。也就是对于一个起始状态a我们可以搞出他到终点的最少步数,但是输入b状态的时候你有可能重复经历一次这个状态的查询,所以逆向bfs,找出所有状态到目标状态的最短路(因为我们在这个过程中可以记录状态的前驱状态,然后递归回去就可以了)。

 

其实这道题目太特殊了,因为他给出了目标状态。所以才可以这样搞。

hoj 1868 八数码

如果给出目标状态和起始状态,然后询问的话,就不能逆向搞了。我们可以双向搜索。个人理解就是把起点终点都压入队列。如果一个状态被两个方向都找到过,那么就找到最短路啦。注意标记好两个两个方向的不同标记,另外其实八数码可以快速判断是否有解。

方法就是若两个状态的逆序同奇偶,则有解,否则无解。不考虑空格

证明:把八数码看成一维的话,左右移动空格并不会影响逆序。上下移动空格,这就是一个数向前或者向后跳两格,所以逆序要么增加2要么不变。所以同奇偶是保证有解的充要条件。

 

hdu 5773 The All-purpose Zero(贪心+最长上升子序列)

Problem Description
?? gets an sequence S with n intergers(0 < n <= 100000,0<= S[i] <= 1000000).?? has a magic so that he can change 0 to any interger(He does not need to change all 0 to the same interger).?? wants you to help him to find out the length of the longest increasing (strictly) subsequence he can get.

 

Input
The first line contains an interger T,denoting the number of the test cases.(T <= 10) For each case,the first line contains an interger n,which is the length of the array s. The next line contains n intergers separated by a single space, denote each number in S.

 

Output
For each test case, output one line containing “Case #x: y”(without quotes), where x is the test case number(starting from 1) and y is the length of the longest increasing subsequence he can get.

 

Sample Input
2
7
2 0 2 1 2 0 5
6
1 2 3 3 0 0

 

Sample Output
Case #1: 5
Case #2: 5

Hint

In the first case,you can change the second 0 to 3.So the longest increasing subsequence is 0 1 2 3 5

看了一下数据范围肯定要nlogn计算LIS了,赶快去复习了一下加强了一下理解,其实感觉nlogn的算法也是一种贪心,保证了相同长度下结尾元素尽可能的小,可以使LIS的结果不会更差。
这道题目说0是可以变成任意数字的,那么肯定是要全部使用0的,这样并不会使结果变得更差,所以我们可以最后的答案是0的数字+nlgon求出的LIS长度。
但是这样就有一个问题,假如0被包括在了LIS序列内怎么办?赶快去请教了一下李大爷,被教育了:每个数原来的值减去他之前0的个数再做LIS就可以了。比如如果1前面有2个0就变成-1之类的。这样做的理由是,我们考虑0在加入LIS中肯定是要变成某些数字来保证严格递增的,假设最后得到的序列是这样的:1,0,3,0,0,9(这里非0数字并未减去他之前的0的数目)那么两个之前不是0的数字a,b之间的那些0要保证递增,那么相互之间差1才是最起码的条件。那么这两个数字之间abs(a-b)一定要满足这个条件。所以这么做,有点神啊这个思路。