算法与acm

const long maxn=1000001;
bool prime[maxn];
//筛选法求素数
//0代表素数，1代表非素数

void primeinit(){
long long i=2,t;
for(i=4;i<maxn;i=i+2)
prime[i]=false;
for(i=3;i<maxn;i=i+2)
{

    if(prime[i])
    {
        t=i*i;
        while(t<maxn)
        {
        prime[t]=false;
        t=t+i;//<<2;//偶数倍不用检测i*i为奇数，故i*i+2i必为奇数
        } read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098283597120/

对于通常的尾递归很容易转换成循环。通过手工模拟我们基本上就可以确定如何进行转换。实际上尾递归的转换也可以看成是下面这种模式的特殊情况，在这种模式下，尾递归只是一个这样的递归树。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200982584340501/

1.求最长回文子串。
[解法]：
将整个字 符串反过来写在原字符串后面，中间用一个特殊的字符隔开。这样就把问题变为了
求这个新的字符串的某两个后缀的最长公共前缀。而某两个后缀的lcs的计算利用后缀数组，可以O(1),这样总的复杂度就可以降为O(n)。
eg：aabebf  —->   aabebf&fbebaa read more

涉及到字符串的问题，无外乎这样一些算法和数据结构：自动机 KMP算法 Extend-KMP 后缀树 后缀数组 trie树 trie图及其应用。当然这些都是比较高级的数据结构和算法，而这里面最常用和最熟悉的大概是kmp，即使如此还是有相当一部分人也不理解kmp，更别说其他的了。当然一般的字符串问题中，我们只要用简单的暴力算法就可以解决了，然后如果暴力效率太低，就用个hash。当然hash也是一个面试中经常被用到的方法。这样看来，这样的一些算法和数据结构实际上很少会被问到，不过如果使用它们一般可以得到很好的线性复杂度的算法。 read more

1.将字符串转换成整数，将整数转换为字符串，浮点数与字符串的转换(atoi itoa)

int atoi(const char *str){
    int res = 0;
    int sign;
    assert(str != NULL);
    if(str[0] == ‘-‘) sign = -1;
    else if(str[0] == ‘+’) sign =1;
    else if(isdigit(str[0])){sign = 1;res=str[0] – ‘0’;} read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098311658625/

RSA加密系统，实际上基于这样一个基本事实。大数的素性测试要比因子分解简单的多，因子分解是一个难问题。

素数测试

如何测试一个数n是不是素数呢？简单的办法就是试一下它能否整除比它小的那些数，当然可以优化只检测小于sqare(n),但是无论如何优化，需要检测的数的个数都将不会小于小于sqare(n)的素数的个数。根据拉格朗日定理，小于n的素数的个数大概=n/ln(n)，也就是说这个数目很大，数量级上很接近n了。所以这个路子实际上很难降低复杂度。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098210128972/

欧几里德算法

用来求两个数的最大公约数的算法。具体如下
int gcd(int a,int b){
   if(b == 0) return a;
   return gcd(b,a%b); 
}

首先看正确性证明，实际上需要证明gcd(a,b)=gcd(b,a%b),我们只要证明gcd(a,b)=gcd(a-b,b)即可，因为可以由此逐步扩展为gcd(a,b) = gcd(a-k*b,b),而 gcd(a-k*b,b)=gcd(a%b,b)。
因为a,b的公约数必然是a-b,b的公约数故 gcd(a,b) <= gcd(a-b,b);另a-b b的公约数也必然是a b的公约数，gcd(a,b) >= gcd(a-b,b).所以gcd(a,b) = gcd(a-b,b)。证明完毕。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200953105952749/

对于字符串处理，常用的有这么几个工具，kmp，trie树，trie图，后缀树，后缀数组，正则表达式，DFA，NFA。下面就这些算法，数据结果及模型进行下简要的说明，并研究下它们之间的联系。 read more

24点，是指给定4个数，和一个值，如何将这4个数通过+-*/得到这个值。
一个算法是这样的：4个数字组成一个表达式还需要3个运算符，这样我们只要把这7个元素的所有排列求出来，然后求值就可以了。
但是这个算法有三个问题：
1.这样的表示出来的序列并非全部是合法的表达式，比如3344+-*
2.实际的表达式可以加括号，但是这个也无法体现出来，而且表达式计算起来还要考虑优先级，转化为后缀表达式，当然这个括号我们可以通过枚举+-*/的优先级别来代替加括号
3.数字是不能重复选择的，而运算符则可以重复 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720094279641210/

有关各种排序问题的稳定性，时间复杂度，比较次数大概是最经常问到的问题了。另外对于某些公司，对于大数据量的排序问题也会涉及，这样就可能牵扯到外排序。所以这里一并将外排序一般归并过程中所使用的败者树和胜者树，以及置换选择排序大概的描述一下。 read more

明朝凌濛初写过初刻拍案惊奇，二科拍案惊奇，书中描写了很多离奇曲折的故事。而算法求解中，往往也会遇到让人拍案惊奇的方法，更有山穷水复疑无路，柳暗花明又一村。姑且用这篇文章，收集那些曾经遇到的那些虽然短小精悍，却拥有惊人解法的算法问题好了。 read more

1.枚举int值，统计二进制bit中1的个数

1.1记忆化统计1的个数，x^(x-1)直接统计

 //enum int comb
int count(unsigned int x){
    int i = 0;
    while(x != 0){
        x = x&(x-1);
        i++;
    }
    return i;
}
void enumComb(int N,int M){
    int one[1<<15];
    for(int i = 0 ; i < (1 << (N+1)/2) ; i++){
        one[i] = count(i);
    }
    int half = N/2;
    for(int i = 1 ; i < (1 << half) ; i++){
        for(int j = 1 ; j < (1 << N-half) ; j++){
            if(one[i] + one[j] == M){
                 cout << i << " " << j << endl;      
            }    
        }
    }
} read more

转载请注明作者：phylps@bmy 

出处：http://duanple.blog.163.com/blog/static/70971767200922110494318/

第一层次

线段树的本质在于将一条线段区间分成一些小的子段，树状数组可以看成一种线段树。对于该区间内的一些线段便可以用这样的一些子段来表示，同时有这样的定理。任何一个长为L的线段都可以用不超过2*logL个子段表示。这样对于插入一个线段便可以在logn时间内解决。而线段树，则是通过这样的使用线段子段的组合，来表示现在出现的线段，而具体的方式则是通过对于一个子段的cout计数来表示的。同时一条线段在树中，只会被真实的表达一次，即只有真正组成它的那些子段会被计数，而当子段已经计数，就可以结束，而子段下的子段不会被重复计数。 read more

近来忙着挑战杯的项目，还有异构编程的，没有多少时间来做题，不过偶尔也会把题目记在心里，走路吃饭睡觉的时候那么想想。有时候也会有了一些新的看法和思考，感觉这样的思考方式倒是挺安静也挺深刻的，不会拘泥于做题中对数量的追求。 read more

线段树就像树状数组一样，通过将一个长为n的段落，划分为O(logn)个子段落，这样就可以通过维护子段落的属性，来求得整个段落的属性。可以证明，任何一个子段在一颗线段树上不会被划分为超过2logn个子段。

一个典型的线段树如下： read more

历史上，Knuth在其<<Sorting and Searching>>一书的第6.2.1节指出：尽管第一个二分搜索算法于1946年就出现，然而第一个完全正确的二分搜索算法直到1962年才出现。

而不经仔细斟酌而写出的一个二分查找经常遭遇off by one或者无限循环的错误。下面将讨论二分查找的理论基础，实现应用，及如何采用何种技术保证写出一个正确的二分程序，让我们免于思考麻烦的边界及结束判断问题。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720081131113145832/

虽然网上有很多介绍了，我还是要写一下吧，尽量从它的起源，如何被发现，以及为什么应该是这样的来写，单纯的使用很简单，也不是学习的目的，理解有助于记忆吧，当然可能还有理解不到的地方。 read more

先看一下匈牙利算法的dfs实现，很简洁

//二分匹配模板
bool g_map[MAX_N][MAX_N];
int r[MAX_N];
int l[MAX_N];
bool used[MAX_N];
int n;
bool path(int u,int n){
    for(int v = 0 ; v < n ; v++){
        if(g_map[u][v] && !used[v]){
            used[v] = true;   
            if(r[v] == -1 || path(r[v],n)){
                l[u] = v;
                r[v] = u;   
                return true;
           }           
        }
    }
    return false;
}
int bin_match(int n){
    int res = 0;
    memset(r,-1,sizeof(r));
    memset(l,-1,sizeof(l));
    for(int i = 0 ; i < n ; i++){
        memset(used,false,sizeof(used));
        if(l[i] == -1){
           if(path(i,n)) res++;   
        }
    }
    return res;
} read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/709717672008111064351431/

很明显，对于算法的证明过程的理解有助于算法本身的理解。

关于二分图，算法的流程在这篇blog里讲的很清楚，很多算法都结合了图形，所以讲讲得很易懂，推荐一下 read more