本文记录让人耳目一新的各种算法，会不断补充…

异或性质

数组中只出现一个奇数次的数，其它数都出现偶数次，让找出现奇数次的数

异或性质。$O(n) $

加强版是有两个奇数次的数，找出这两个。

根据异或得到的结果的二进制位中为 $1$ 的的任一位，把数分成两份后分别再做异或操作， $O(2n)$

随机化算法

POJ3318 判断矩阵 $A*B=C$ ，不能用 $O(n^3)$

随机化出一个一维向量，左右都相乘之后判断结果是否相等，$O(n^2)$ 就可以

问数列至少移动几次可以变有序

最长上升子序列问题

问数列至少交换几次可以变有序

求逆序对个数

有向图，有 $k$ 次机会将一条边权值减半，用 $O(n^2)$ 求最短路

分层图问题 $O(n^2k^2)$

POJ3254：题解从1~n中选若干数，要求选了 $x$ 不能选 $2x$ 和 $3x$ ，求选取方案数。

把数字 $1$ 放在方阵最左下角，然后不断在一个数的右边填上它的两倍，在其上方填上它的三倍。问题就等价地转化为：在方阵中选取若干个格子使得任意两个不相邻，求有多少种选取方案。

另外，遇到尚未出现过的数（即除 $2$ 和 $3$ 以外的素数）就再开一张新的表，然后用乘法原理把它们各自对应的方案数乘起来就是了。

例如当 $n=20$ 时，最终答案就等于下面这7张表各自所对应的选取方案数的乘积。

如何完全随机的打乱一个数组，保证每个数出现再每个位置上的概率相等。

乍一看很简单，仔细一想还真有点无从下手。下面给出一份及其精炼的代码

for(int i=n-1; i>=0; i--)
	swap(a[i], a[rand(0, i)]);

就是从后向前遍历，把当前数字与它前面的（包括自己）随机一位数字交换（默认rand()函数满足完全随机）。

举个例子解释原理：12345

第五位，与它前面的数字（包括自己）进行交换，这样五个数字位于第5位的概率都是 1/5
第四位，现在它前面的数字（包括自己）在当前位置的概率是 4/5，被选中的概率是 1/4，所以剩下四位数字每个在第4位的概率是 4/5*1/4 = 1/5
第三位，现在它前面的数字（包括自己）在当前位置的概率是 4/5 * 3/4，被选中的概率是 1/3，所以剩下三位数字每个在第4位的概率是 4/5 * 3/4 * 1/3 = 1/5
……

可见每个数字都能独立等概率的出现在每一个位置，每一个位置都能独立等概率的放置每个元素。

http://www.matrix67.com/blog/archives/1850

https://blog.csdn.net/harrypoirot/article/details/23163485