给定一组数，给定给定一个区间，求区间最值，算法大致有以下几种
下面主要介绍ST算法
Continue reading “用于求区间最值(RMQ问题)的O(1)算法–ST(稀疏表)算法”
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。（见下图）
  如图蓝线所示是一种最大二分匹配方案，匹配数=3 |
如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)
（以上除图片均来自百度百科）
自学康托展开（做8数码问题）去网上查资料，无无一明白，又苦于资料太少，讲的太含蓄
然而《周易》云：天行健，君子以自强不息
于是奋战6h作此文
为像我一样的菜扫清前行障碍，故名曰：“详解”
如有不当之处，恳请指正
~_~_~_~_~_~_~_华丽的分割线_~_~_~_~_~
康托展开(x)的实际意义:对于一个长度为n的数列包含元素[0..n-1]
x表示此数列是{0,1,2…n-1}全排列中第几小的。最小的为0
(但是通常应用的康托展开有时是[1..n])
例如当n=3时(默认[1..n]):
{1,2,3}x=0;{1,3,2}x=1;
{2,1,3}x=2;{2,3,1}x=3;
{3,1,2}x=4;{3,2,1}x=5;
(针对0..n-1是连续自然数 )
其计算方法:
\(
X=a[n]\times (n-1)!+a[n-1]\times (n-2)!+…a[i]\times (i-1)!a[2]\times 1!+a[1]\times 0! \\
\)
X=a[n]*(n-1)!+a[n-1]*(n-2)!+…a[i]*(i-1)!+a[2]*1!+a[1]*0!;
或(d对于第一位为a[1],下面代码即是如此):
\(
X=a[1]\times (n-1)!+a[2]\times [n-2]!+…+a[n-1]\times 1!+a[n]\times 0! \\
\)
X=a[1]*(n-1)!+a[2]*[n-2]!+…+a[n-1]*1!+a[n]*0！
其中a[i]表示元素arr[i]在还未出现的数字中排第几,简而言之就是其后面有多少元素比arr[i]小
核心代码：
|
1 2 3 4 5 6 7 |
readln(n); for i:=1 to n do read(arr[i]); for i:=1 to n-1 do begin //循环当前位 t=0;//代表第几大 for j=i+1 to n if arr[j] ans:=ans+t*fac[n-i-1];//fac[i]表示i阶乘 end; writeln(ans) ; |
实际代码（C实现）个人认为比较详细了，如果有不理解，切记看完上面说明
Continue reading “康托展开详解”
本来是个水题，我一交，WA：90，第一点错误，答案1位选手输出20位。
得，骗数据，共1个物体，4*4大小，推断可能是：
1
4 4
1000
0000
0000
0000
这叫什么数据。。
一定要注意可能n*m的方块没有占用n*m的情况，于是乎，我放上来了
MYCODE:
Continue reading “p44 拼图 回溯题解”
题目中说二叉树的中序遍历是顺序的，这说明：对于区间[i,j]其根root满足i<=root<=j
也就是说，对于区间[i,j]其最大加分为选取其中一个作为根R，其左边[i,R-1]的最大加分乘以[R+1,j]区间最大加分+Value[R]，对于所有可能的R取表达式最大值.状态转移方程：
\(f[i][j] = Max\left\{ {f[i,k – 1] \times f[k + 1][j] + v[k] ~|~ k = i~to~j} \right\}\)注意：题目要求若一棵树没有左或者右子树，则其加分为存在的那棵子树
初始值for i=1 to n f[i][i]=v[i];
输出便利的方法是：每次记录取到最大值时的根节点编号，设Node[i][j]=x表示在[i][j]区间取到最大加分的数的根节点为x
Continue reading “P49 加分二叉树 题解”
所谓二分查找,就是在有序的数组中查找某一值的元素,基本方法是分治
例如：最长不下降子序列中的二分查找,当动规到某一位置时,要知道在辅助数组中Key的位置,需要找到Key所在位置或仅比Key小的（\(\)c[i]\leqslant key
CODE:
这样写好像很简单
1234567891011121314inline int bin(int x){ int b=0,e=MAX,k=(b+e+1)>>1; while (b<e) { if (f[k]>x)e=k-1; else if (f[k]<=x)b=k; k=(b+e+1)>>1; } return k;}//关键在于"k=(b+e+1)>>1;"//这条语句能满足一个很好的性质,即b,e如果相邻的话(e-b=1),则k=e而不是b,当然,如果e-b=2的时候,k=(b+e)/2
1234567891011#include <stdio.h> int bins(int key) { static int l,r,y;//l:左界,r,右界 l=0;r=n; while (l<=r){ y=(l+r)>>1;//位运算右移,相当于除2 if (m[y] > key) r=y-1;else if (m[y] < key) {if (m[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便 else return y; } }
MY CODE:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<stdio.h> //nlogn算法 /*把10000搞成1000了，错了一下午*/ int n,max; int b[10001],a[10001],len[10001]; int bins(int key) { static int l,r,y; l=0;r=n; while (l<=r){ y=(l+r)>>1; if (b[y]>key) r=y-1;else if (b[y]<key) {if (b[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便 else return y; } } int main(){ int i,j; scanf("%d\n",&n); for (i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=20000;} b[0]=0;//这个初始化要比所有元素小 for (i=1;i<=n;i++){ len[i]=bins(a[i]-1)+1; if (len[i]>max) max=len[i]; if (b[len[i]]>a[i]) b[len[i]]=a[i]; } printf("%d",max); return 0; } |
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。也有人说SPFA本来就是Bellman-Ford算法，现在广为流传的Bellman-Ford算法实际上是山寨版。
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
Continue reading “SPFA”
{
作者：时光9154
当然底下的C代码是我(Comzyh)写的
http://hi.baidu.com/time9154
}
多关键字的快速排序
解决类似如下的问题：输入n组坐标（xi，yi），要求按xi的升序排序后，对于xi=xj（j>i），yi~j升序排列
即双关键字排序，先保证第一关键字的升序，在第一关键字一样的情况下保证第二关键字的升序
Continue reading “[转]多关键字的快速排序”