最近翻译了一个东西，是关于旋转卡壳及其应用的，翻译的不太好，大家将就着看吧，这个东西还是很强大的，很佩服做这个的大牛，思路很新颖啊！

虽然基本上是人家十年前发表的东西，但是还是很实用的

我放到网盘上去了，大家想看的话可以去下，地址是http://acmaker.ys168.com/，在我的资料下面的那个chm就是了。

最近试着写了恶心搜索题之Sudoku，就是数独啦，写了615行，而且包括其拓展

最原始的数独是(3^2)^2的，我参考了一些资料，加了六个剪枝和一个枚举过程，在zju上很轻松过了,然后又到pku上去试了试，把几乎全部名字里带Sudoku的都轻松过了。

然后我进行了Sudoku的拓展，成为了可以计算(n^2)^2的代码，自己试了一下，收获不少。

后来发现zju这个数独题目的数据真是很弱，我有一个回溯上的错误在zoj2580上没有测出来（应该说n=3都测不出来），我用那个n=4的

算法分析：第三种算法的复杂度也是O(nlogn)(其实是他规定的，没办法^_^)，算法的具体思想有点类似，先将这个数组排序，然后利用二分查找来解决（不如第一种算法），枚举每个数组元素，然后查找是否存在一个有序数组中的数和他的和为x（不是本身），二分查找有序数组的时间复杂度为O(nlogn)，乘以枚举的基数n，算法复杂度就是O(nlogn)，加上排序的时间复杂度O(nlogn)，总的分析下时间复杂度还是O(nlogn)（我好废话）。

代码实现：

#include<stdio.h>
#include<algo

算法分析：这个第二个算法是通过归并排序的原理来实现的，首先我们把数组二分成两个部分，我们采用递归判定左右两个部分内部是否有和为x的元素，如果有直接输出就可以了，否则的话我们考虑这样的情况：一个元素在左边，一个元素在右边，他们的和为x！此时就类似一算法的方法了，因为归并他是建立在前面已经操作的计算：分别对左右两个部分排好序，然后进行合并！这样我们类似一算法设置两个指针，一个指向左边的开始，一个指向右边的结尾，我们开始同样的过程：判断两个指针的指点的和，等于x的话表明已经找到

今天课程的第二个题目是判定是否存在两数字和为x，这个题目要求将时间复杂度限定为O（nlogn），我自己想到了三个算法，一个个来说吧，先说第一个：

问题描述：输入n个数，求给定数组中是否存在两个数，他们的和为x

输入数据：元素个数n，和x，数组a

输出数据：如果存在两个数则输出那两个数，否则输出“No Answer！”

算法分析：对于一般情况下，如果用最原始的方法就是枚举那两个数（两重for循环），当然这个算法

这个学期开设了算法导论课程（我很喜欢^_^），觉得应该开始写点什么，就写写吧~~~~

今天讲了关于求逆序对数的O(nlogn)算法，之前接触过，也写过代码，就总结一下吧！

先是逆序对的定义：一个n个互异元素的数组a，求满足i<j时a[i]>a[j]条件的数对个数。

数据输入：n（元素个数），a数组

数据输出：逆序对个数

算法分析：这个题目十分的经典，是归并排序的一个