发布于 2014-10-17 07:41:23 | 1015 次阅读 | 评论: 0 | 来源: 网友投递

这里有新鲜出炉的精品教程，程序狗速度看过来！

亚马逊(Amazon)

亚马逊公司（Amazon，简称亚马逊；NASDAQ：AMZN），是美国最大的一家网络电子商务公司，位于华盛顿州的西雅图。是网络上最早开始经营电子商务的公司之一，亚马逊成立于1995年，一开始只经营网络的书籍销售业务，现在则扩及了范围相当广的其他产品，已成为全球商品品种最多的网上零售商和全球第二大互联网企业，在公司名下，也包括了AlexaInternet、a9、lab126、和互联网电影数据库（Internet Movie Database，IMDB）等子公司。

---

原题：

题目意思就是找一棵按上面链接所示的树对应的上面的两个点的最小公共祖先(LCP,Least Common Father)，按照比较大小来依次返回自己的父亲节点就行了。具体看代码：getfather(a)函数是找父亲的代码

    #include <cstdio>  
    #include <cstring>  
    #include <iostream>  
    #include <algorithm>  
    using namespace std;  
    int three[20] , sum[20];  
    //int cnt = 0;  
    void init() {  
        three[0] = 1;  
        sum[0] = 0;  
        for(int i=1;i<20;i++) three[i] = three[i-1] * 3 , sum[i] = sum[i-1] + three[i];  
    }  
    int getfather(int a) {  
        if(a <= 3) return 0;  
        int i;  
        for(i=0;sum[i]<a;i++);  
        i --;  
        int tmp = (2+a-sum[i]) /3;  
        a = sum[i] - tmp + 1;  
    }  
    int LCP(int a,int b) {  
        while(a != b) {  
            if(a > b) a = getfather(a);  
            else b = getfather(b);  
            //printf("%d %d\n" , a , b);  
            //cnt ++;  
            //if(cnt > 5) break;  
        }  
        return a;  
    }  
    int main() {  
        int a , b;  
        init();  
        while(scanf("%d%d" , &a,&b) != EOF) {  
            //cnt = 0;  
            int ans = LCP(a , b);  
            printf("%d\n" , ans);  
        }  
        return 0;  
    }