题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

这道题伤了我很久脑筋

因为是a+b+c=d,数据量是1000,很自然地想到a+b=d-c

这样转化为n^2的算法.

但是我开始枚举d-c的集合二分查找a+b的几何不知道为什么WA掉了

后面就想其他的办法,参考了一下别人的做法,我觉得差不多和我一样,然后重写.我也和他一样无耻的用STL库函数了

//最长单调子序列 复杂度nlog(n)
//参数(原序列,序列长度,生成的序列),传入序列长度必须大于0
//返回值中lengthRecord中前k项表示长度为k的最小字序列
//LIScmp为关系函数,原函数表明lengthRecord为递增(不含等于)
typedef double LISTYPE;
#define LISMAXN 10000
int LIScmp(LISTYPE a,LISTYPE b)
{
    return a < b;
}
long LISLength(LISTYPE list[],long n,LISTYPE lengthRecord[])
{
    long length = 1,lth;
    LISTYPE lR[LISMAXN];
    lR[0] = list[0];

    for(int i = 1 ; i < n ; i ++)
    {
        //二分查找,复杂度 log(n)
        int b,e,m;
        b = 0;
        e = length - 1;
        while(b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if(LIScmp(lR[m],list[i]))
                b = m + 1;
            else
                e = m - 1;
        }
        lR[b] = list[i];
        if(b >= length)
            length ++;
    }
    /*
    *计算序列部分
    *复杂度nlog(n)
    */
    lth = 1;
    for(int i = 1 ; i < n ; i ++)
    {
        //二分查找,复杂度 log(n)
        int b,e,m;
        b = 0;
        e = lth - 1;
        while(b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if(LIScmp(lR[m],list[i]))
                b = m + 1;
            else
                e = m - 1;
        }
        lR[b] = list[i];
        if(b >= lth)
            lth ++;
        if(lth == length)
        {
            for(b = 0 ; b < length ; b ++)
                lengthRecord[b] = lR[b];
            break;
        }
    }
    //计算序列部分代码与之前的类似,可以直接Copy然后修改
    return length;
}

//Prime连通路模块
#define N 1000         //最大数据规模
#define MAXNUM 3000000   //最大路径长度
typedef double PrimeType;//路径类型

PrimeType PrimeRecord[N];
PrimeType dis[N][N];
int isLined[N] = {1,0};

PrimeType GetPrimeLength(const long n)
{
    PrimeType tmpLen = MAXNUM;
    long tmpPos = 0,left = n - 1;
    PrimeType sumLen = 0;

    for(long i = 1 ; i < n ; i ++)
        PrimeRecord[i] = dis[0][i];
    while(left --)
    {
        tmpLen = MAXNUM;
        for(long i = 1 ; i < n ; i ++)
            if(!isLined[i] && PrimeRecord[i] < tmpLen)
                tmpPos = i,tmpLen = PrimeRecord[i];

        sumLen += tmpLen;
        isLined[tmpPos] ++;
        for(long i = 1 ; i < n ; i ++)
            if(dis[tmpPos][i] < PrimeRecord[i])
                PrimeRecord[i] = dis[tmpPos][i];
    }

    return sumLen;
}

//MULDATATYPE为矩阵元素类型,MAXMAT为最大矩阵大小

typedef long MULDATATYPE;
#define MAXMAT 100
#define inf 1000000000

#define fabs(x) ((x)>0?(x):-(x))
#define zero(x) (fabs(x)<1e-10)

struct mat
{
    long n,m;
    MULDATATYPE data[MAXMAT][MAXMAT];
    void operator =(const mat& a);
    mat operator +(const mat& a);
    mat operator -(const mat& a);
    //0-1邻接矩阵
    mat operator &(const mat& a);
    mat operator |(const mat& a);
};

//c=a*b
//注意引用
int Mat_MulMode(mat& c,const mat& a,const mat& b,MULDATATYPE mod)
{
    long i,j,k;
    if (a.m != b.n)
        return 0;
    c.n = a.n , c.m = b.m;
    for (i = 0 ; i < c.n ; i ++)
        for (j = 0 ; j < c.m ; j ++)
            for (c.data[i][j] = k = 0 ; k  < a.m ; k ++)
                c.data[i][j] = (c.data[i][j] + a.data[i][k] * b.data[k][j]) % mod;
    return 1;
}
//c=a^b(其中必须满足b>0)
int Mat_PowMode(mat& c,mat a,long b,MULDATATYPE mod)
{
    c = a;
    b --;
    while(b)
    {
        mat tmp;
        if(b & 1)
        {
            tmp = c;
            Mat_MulMode(c,tmp,a,mod);
        }
        tmp = a;
        Mat_MulMode(a,tmp,tmp,mod);
        b = b>>1;
    }
    return 1;
}
//c=a+b
int Mat_AddMode(mat& c,const mat& a,const mat& b,MULDATATYPE mod)
{
    long i,j;
    if (a.n != b.n || a.m != b.m)
        return 0;
    c.n = a.n , c.m = b.m;
    for (i = 0 ; i < c.n ; i ++)
        for (j = 0 ; j < c.m ; j ++)
            c.data[i][j] = (a.data[i][j] + b.data[i][j]) % mod;
    return 1;
}
//c=a-b
int Mat_SubMode(mat& c,const mat& a,const mat& b,MULDATATYPE mod)
{
    long i,j;
    if (a.n != b.n || a.m != b.m)
        return 0;
    c.n = a.n , c.m = b.m;
    for (i = 0 ; i < c.n ; i ++)
        for (j = 0 ; j < c.m ; j ++)
            c.data[i][j] = (a.data[i][j] - b.data[i][j]) % mod;
    return 1;
}


void mat::operator =(const mat& a)
{
    n = a.n;
    m = a.m;
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < m ; j ++)
            data[i][j] = a.data[i][j];
}
mat mat::operator +(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] + a.data[i][j];
    return tmpMat;
}
mat mat::operator -(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] - a.data[i][j];
    return tmpMat;
}
mat mat::operator &(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] & a.data[i][j];
    return tmpMat;
}
mat mat::operator |(const mat &a)
{
    long i,j;
    mat tmpMat;
    tmpMat.m = m;
    tmpMat.n = n;
    for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
            tmpMat.data[i][j] = data[i][j] | a.data[i][j];
    return tmpMat;
}

今天在湖南的OJ上做题,发现不到两小时,他服务器就挂了,但是发现他和POJ上的一些题一样而且是连号的,就到POJ上继续了，我们队出了6题。

A题是POJ的3507 Judging Olympia这题是队友干掉的,我没看

B题是POJ的3508 Hide That Number同样是队友AC掉,我没看

懒惰了，暂时休息一下

这次我只AC了一题（在结束的那一刻，另一题在题目来源地网站上AC了，我们的OJ上仍然WA，我们OJ的Special Judge真是—_—!）

H题是用木棒拼数字，给出木棒数量，要求算出拼出的最大和最小数字

校赛个人训练赛第五场报告

今天战绩还行，AC了5题，今天总体没有太复杂的算法题，不过测试数据强度比之前有所增加 我的钱四题很早就过了，但是第五题很晚才出主要是代码写得太混乱，思路也错了两次 我过的题有五道，分别是ABCDG

A Coming Near

A题是计算两个多边形的最近距离

点到直线距离

// (x0,y0)到(x1,y1)和(x2,y2)确定的直线的距离

double disBetweenPointAndLine(double x0,double y0,double x1,double y1,double x2,double y2)
{
    //化为ax+by+c=0的形式
    double a = y1-y2;
    double b = x2-x1;
    double c = x1*y2-x2*y1;
    double d = (a*x0+b*y0+c)/sqrt(a*a+b*b);
    /*
    如果是线段判断垂足

    double xp = (b*b*x0-a*b*y0-a*c)/(a*a+b*b);
    double yp = (-a*b*x0+a*a*y0-b*c)/(a*a+b*b);
    double xb = (x1>x2)?x1:x2;
    double yb = (y1>y2)?y1:y2;
    double xs = x1+x2-xb;
    double ys = y1+y2-yb;
    if(xp > xb || xp < xs || yp > yb || yp < ys)
    {
        d = sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1));
        if(d > sqrt((x0 - x2) * (x0 - x2) + (y0 - y2) * (y0 - y2)))
            d = sqrt((x0 - x2) * (x0 - x2) + (y0 - y2) * (y0 - y2));
    }
    */
    return fabs(d);
}

线段间最短距离

//n每个用例的点个数
//MAXN为最大点个数
//PTYPE为坐标值类型
#include
#include
using namespace std;

#define MAXN 1005
#define EPS 1e-10
typedef double PTYPE;

struct point
{
    PTYPE x,y;
};
struct node
{
    PTYPE k;
};
int cmp(const void * a, const void * b)
{
    return((*(PTYPE*)a-*(PTYPE*)b>0)?1:-1);
}
node numK[MAXN * MAXN / 2];
point pt[MAXN];
int main()
{

    int n , maxNum = 1 , tmpNum = 0;
    while(scanf("%d",&n),n)
    {
        for(int i = 0 ; i < n ; i ++)
            scanf("%lf %lf",&pt[i].x,&pt[i].y);
        for(int i = 0 ; i <  n ; i ++)
        {
            int pos = 0;
            for(int j = i + 1 ; j < n ; j ++)
                if((pt[i].x - pt[j].x) > EPS)
                    numK[pos ++].k = (pt[j].y - pt[i].y) / (pt[j].x - pt[i].x);
                else
                    numK[pos ++].k = 100000;

            qsort(numK,pos,sizeof(numK[0]),cmp);
            int tmpNum = 2;
            for(int j = 1 ; j < pos ; j ++)
            {
                if(numK[j].k == numK[j - 1].k)
                    tmpNum ++;
                else
                {
                    if(tmpNum > maxNum)
                        maxNum = tmpNum;
                    tmpNum = 2;
                }
            }
            if(tmpNum > maxNum)
                maxNum = tmpNum;
        }


        printf("%d\n",maxNum);
        maxNum = 1;
    }
    return 0;
}

Problem A

我没看题,队友很快AC我就没花时间看

Problem B

DP题,但是我们确实都没想到方法,实在是我们的经验不足

B题补充: B题的DP方法比较诡异(起码我理解了很久) 令fn[i][j]为有i个数j次交换位置的排列数量 很明显,当i+1时,如果把新增的数放在最后一位,那么交换次数不变(新增的数为i+1,最大). 如果把新增的数放在第1到i位之间的话有i种放法, 对于每一种fn[i][j]的排列中我们总能找到一种序列使得{(.)(.)()(.)(.)…(i+1)},["()表示一个元素"] 中(i+1)和()交换位置后前i个元素的排列和其相同 又因为(*)的位置可以有i种放法,以此我们发现,fn[i+1][j]=fn[i][j]+fn[i][j-1]×i 继续贴代码:

根的关系:

牛顿迭代解方程(x0附近的根)

double Newton_Iterative(double a,double b,double c,double d,double x0)
{
    double f0,f0d,x;
    x = x0;
    do
    {
        x0 = x;
        f0 = ((a * x + b) * x + c) * x + d;
        f0d = ( 3 * a * x + 2 * b ) * x + c;
        x = x0 - f0 / f0d;
    }
    while(fabs(f0) >= 1e-12);
    return x;
}

牛顿迭代法

校赛个人赛第三场部分解题报告（A,D,F,I）

这次我完成了四道题分别是A,D,F,I

一大半时间我都花在了A上，我犯了很究级的错误

首先是VC6.0的algorithm里没有min函数，而我用min做变量名导致CE4次，找了半天才找出来

校赛个人赛第六，七场总结

这两场比赛体现了英文水平的重要性

第六场的题目超长，用词还诡异，话了很长时间才看懂

这两场题目都比较有难度，第六场我只出了2题

A Grey Area

A题是很诡异的统计，是一道纯模拟就能过的题，其他的不多说了

先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？

有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但…也只能如此了。

POJ打破传统,以前是做一题送一题,现在是做一题送两题,那么我们就不用客气了

言归正传 题号:2606 Rabbit hunt 2780 Linearity 1118 Lining Up

大致题意是输入N个点.计算能穿过最多的点的直线,并输出最大点的个数

最初的想法很简单

枚举没两个点连成的直线,然后枚举每个点,计算通过这条直线的点的个数,但是这个方法的复杂度为O(n^3)

资料由互联网收集整理，供新手参考学习 这里又生动点的演示：http://www.cnblogs.com/wangfupeng1988/archive/2011/12/26/2302216.html

/*
=============================================================================
相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）：
1、稳定排序和非稳定排序
简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就
说这种排序方法是稳定的。反之，就是非稳定的。
比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，
则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,
a2,a3,a5就不是稳定的了。
2、内排序和外排序
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；
在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。
3、算法的时间复杂度和空间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
================================================================================
*/
/*
================================================
功能：选择排序
输入：数组名称（也就是数组首地址）、数组中元素个数
http://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环
到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。算法复杂度O(n2)--[n的平方]
=====================================================
*/
void select_sort(int *x, int n)
{
    int i, j, min, t;
    for (i=0; i=2] 个数已经是排

好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数

也是排好顺序的。如此反复循环，直到全部排好顺序。

直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]

=====================================================

*/

void insert_sort(int *x, int n)
{
    int i, j, t;
    for (i=1; i=0 && t<*(x+j); j--) /*注意：j=i-1，j--，这里就是下标为i的数，在它前面有序列中找插入位置。*/
        {
            *(x+j+1) = *(x+j); /*如果满足条件就往后挪。最坏的情况就是t比下标为的数都小，它要放在最前面，j==-1，退出循环*/
        }
        *(x+j+1) = t; /*找到下标为i的数的放置位置*/
    }
}
/*

================================================

功能：冒泡排序

输入：数组名称（也就是数组首地址）、数组中元素个数
http://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F

================================================

*/

/*

====================================================

算法思想简单描述：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上

而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较

小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要

求相反时，就将它们互换。

下面是一种改进的冒泡算法，它记录了每一遍扫描后最后下沉数的

位置k，这样可以减少外层循环扫描的次数。

冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]

=====================================================

*/
void bubble_sort(int *x, int n)
{
    int j, k, h, t;
    for (h=n-1; h>0; h=k) /*循环到没有比较范围*/
    {
        for (j=0, k=0; j *(x+j+1)) /*大的放在后面，小的放到前面*/
            {
                t = *(x+j);
                *(x+j) = *(x+j+1);
                *(x+j+1) = t; /*完成交换*/
                k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
            }
        }
    }
}

/*

================================================

功能：希尔排序

输入：数组名称（也就是数组首地址）、数组中元素个数
http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

================================================

*/

/*
====================================================

算法思想简单描述：

在直接插入排序算法中，每次插入一个数，使有序序列只增加个节点，

并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为

增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除

多个元素交换。D.L.shell于年在以他名字命名的排序算法中实现

了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中

记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量

对它进行，在每组中再进行排序。当增量减到时，整个要排序的数被分成

一组，排序完成。

下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，

以后每次减半，直到增量为。

希尔排序是不稳定的。

=====================================================

*/

void shell_sort(int *x, int n)
{
    int h, j, k, t;
    for (h=n/2; h>0; h=h/2) /*控制增量*/
    {
        for (j=h; j=0 && t<*(x+k)); k-=h)
            {
                *(x+k+h) = *(x+k);
            }
            *(x+k+h) = t;
        }
    }
}
/*

================================================

功能：快速排序

输入：数组名称（也就是数组首地址）、数组中起止元素的下标
http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

================================================

*/

/*

====================================================

算法思想简单描述：

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟

扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次

扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只

减少。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）

的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理

它左右两边的数，直到基准点的左右只有一个元素为止。它是由

C.A.R.Hoare于年提出的。

显然快速排序可以用递归实现，当然也可以用栈化解递归实现。下面的

函数是用递归实现的，有兴趣的朋友可以改成非递归的。

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)

=====================================================

*/
void quick_sort(int *x, int low, int high)
{
    int i, j, t;
    if (low < high) /*要排序的元素起止下标，保证小的放在左边，大的放在右边。这里以下标为low的元素为基准点*/
    {
        i = low;
        j = high;
        t = *(x+low); /*暂存基准点的数*/
        while (it) /*在右边的只要比基准点大仍放在右边*/
            {
                j--; /*前移一个位置*/
            }
            if (i=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)
时称之为堆。在这里只讨论满足前者条件的堆。
由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以
很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，
使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点
交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点
的堆，并对它们作交换，最后得到有n个节点的有序序列。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素
交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数
实现排序的函数。
堆排序是不稳定的。算法时间复杂度O(nlog2n)。空间复杂度为Θ(1).
*/
/*

功能：渗透建堆

输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始

*/

void sift(int *x, int n, int s)
{
    int t, k, j;
    t = *(x+s); /*暂存开始元素*/
    k = s;  /*开始元素下标*/
    j = 2*k + 1; /*右子树元素下标*/
    while (j=0; i--)
    {
        sift(x,n,i); /*初始建堆*/
    }
    for (k=n-1; k>=1; k--)
    {
        t = *(x+0); /*堆顶放到最后*/
        *(x+0) = *(x+k);
        *(x+k) = t;
        sift(x,k,0); /*剩下的数再建堆*/
    }
}
void main()
{

#define MAX 4

    int *p, i, a[MAX];

    /*录入测试数据*/

    p = a;

    printf("Input %d number for sorting :\n",MAX);

    for (i=0; i> 1);
                merge_sort(array, first, mid);
                merge_sort(array, mid+1,last);
                merge(array,first,mid,last);
        }
}
/*
================================================
功能：基数排序
http://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
================================================
*/
/*
====================================================
算法思想简单描述：
将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
基数排序的时间复杂度是 O(k·n)，其中n是排序元素个数，k是数字位数。
=====================================================
*/
const int base=10;

struct wx
{
        int num;
        wx *next;
        wx()
        {
                next=NULL;
        }
};

wx *headn,*curn,*box[base],*curbox[base];

void basesort(int t)
{
        int i,k=1,r,bn;
        for(i=1;i<=t;i++)
        {
                k*=base;
        }
        r=k*base;
        for(i=0;inext;curn!=NULL;curn=curn->next)
        {
                bn=(curn->num%r)/k;
                curbox[bn]->next=curn;
                curbox[bn]=curbox[bn]->next;
        }
        curn=headn;
        for(i=0;inext=box[i]->next;
                        curn=curbox[i];
                }
        }
        curn->next=NULL;
}

void printwx()
{
        for(curn=headn->next;curn!=NULL;curn=curn->next)
        {
                cout<num<<' ';
        }
        cout<>n;
        for(i=0;inext=new wx;
                cin>>curn->num;
                maxn=max(maxn,curn->num);
        }
        while(maxn/base>0)
        {
                maxn/=base;
                z++;
        }
        for(i=0;i<=z;i++)
        {
                basesort(i);
        }
        printwx();
        return 0;
}
/*
================================================
功能：鸽巢排序
http://zh.wikipedia.org/wiki/%E9%B8%BD%E5%B7%A2%E6%8E%92%E5%BA%8F
================================================
*/
/*
====================================================
算法思想简单描述：
鸽巢排序(Pigeonhole sort), 也被称作基数分类, 是一种时间复杂度为O(n)且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法. 但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用.
当涉及到多个不相等的元素, 且将这些元素放在同一个"鸽巢"的时候, 算法的效率会有所降低.为了简便和保持鸽巢排序在适应不同的情况, 比如两个在同一个存储桶中结束的元素必然相等
我们一般很少使用鸽巢排序, 因为它很少可以在灵活性, 简便性, 尤是速度上超过其他排序算法. 事实上, 桶排序较鸽巢排序更加的实用.
=====================================================
*/
// 还可以优化成先统计最大最小值，或对值离散化
void pigeonholeSort(int a[],int n)
{
    int j = 0;
    int b[256] = {0};
    for(int i = 0;i < n;i ++)
        b[a[i]] ++;

    for(int i = 0;i < 256; i ++)
       for(int k = 0;k < b[i]; k ++)
           a[j ++] = i;
}

POJ 3267 The Cow Lexicon

这题是一道DP问题,我的想法如下:

1.可以令 deleteNum[pos]为输入字符串在pos处需要删除的最少字符数量;

2.如果输入字符串长度为len,则初始化deleteNum[len] = 0;(字符串由0开始计数)

//并查集
//注意类型匹配
const int maxn = 100002;
int DSet[maxn];
void init(int n) {
    for(int i = 0 ; i <= n ; i ++)
        DSet[i] = i;
}
int findP(int id) {
if(DSet[id] != id)
    DSet[id] = findP(DSet[id]);
    return DSet[id];
}
//返回根节点ID
int UnionEle(int a,int b) {
    a = findP(a);
    b = findP(b);
    if(a > b)
        a ^= b ^= a ^= b;
    DSet[b] = a;
    return a;
}

/**
 * KMP模式匹配
 * 算法复杂度O(m+n)
 * ACM 模板 
 *
 * @Author OWenT
 * @link http://www.owent.net
 */

// 最大字符串长度
const int maxLen = 10000;
// 前一个匹配位置,多次匹配注意要重新初始化
// 注：preMatch[i]表示0~preMatch[i-1]能和?~i匹配
int preMatch[maxLen]={0};

/**
 * kmp匹配算法
 * @param char[] source 查找源
 * @param char[] checked 查找目标
 * @return int 根据以下两个分支返回值分别表示不同的含义
 */
int kmp_match(char source[],char checked[]) {
    int i = 0, j = 0;
    memset(preMatch, 0, sizeof(preMatch));

    if(!checked[i]) // 被匹配串为空串，直接返回 0
        return 0;

    ++ i;
    while(checked[i]) {
        for(j = preMatch[i - 1]; checked[i] != checked[j] && j; j = preMatch[j - 1]);
        preMatch[i] = (checked[i] == checked[j])? j + 1 : 0 ;
        ++ i;
    }
    //计算匹配子串个数(子串间无重叠)(与以下一起二选一)
    int num = 0;//计数变量
    for(i = j = 0; source[i]; ++ i) {
        if(checked[j] == source[i])
            ++ j;
        else if(j)
            -- i, j = preMatch[j - 1];

        if(!checked[j])
            ++ num, j = 0;//如果要子串间重叠 则此句中j = 0 改成 j = preMatch[j - 1]
    }
    return num;

    //计算首个匹配子串位置(与以上一起二选一)
    for(i = j = 0; checked[j] && source[i]; ++ i) {
        if(checked[j] == source[i])
            ++ j;
        else if(j)
            -- i, j = preMatch[j - 1];
    }

    //返回匹配的串的第一个字符出现位置(从1开始计数,0表示无匹配)
    if(!checked[j])
        return i - j + 1;
    else
        return 0;

    return 0;
}