题目：输入一个整数和一棵二元树。

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

例如 输入整数22和如下二元树

  10  

  / /   

 5  12   

 /   /   

4     7

则打印出两条路径：10, 12和10, 5, 7。

 

二叉树节点的数据结构定义为：

struct BinaryTreeNode // a node in the binary tree

{

    int m_nValue; // value of node

    BinaryTreeNode *m_pLeft; // left child of node

    BinaryTreeNode *m_pRight; // right child of node

};

#include <iostream>
#include <vector>
using namespace std;

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
}n1,n2,n3,n4,n5;

BinaryTreeNode* buildTree()
{
    n1.m_nValue = 10;
    n1.m_pLeft = &n2;
    n1.m_pRight = &n3;
    n2.m_nValue = 5;
    n2.m_pLeft = &n4;
    n2.m_pRight = &n5;
    n3.m_nValue = 12;
    n4.m_nValue = 4;
    n5.m_nValue = 7;
    n3.m_pLeft = n3.m_pRight = n4.m_pLeft = n4.m_pRight = n5.m_pLeft = n5.m_pRight = NULL;
    return &n1;
}

void FindPath(BinaryTreeNode *pCurrent,int sum,int curval,vector<int> &path)
{
    if(pCurrent == NULL)
    {
        return ;
    }
    curval += pCurrent->m_nValue;
    path.push_back(pCurrent->m_nValue);
    if(curval == sum)
    {
        if(pCurrent->m_pLeft == NULL && pCurrent->m_pRight == NULL)
        {
            for(vector<int>::iterator it = path.begin();it != path.end();it++)
            {
                cout<<*it<<" ";
            }
            cout<<endl;
        }
    }
    else 
    {
        if(pCurrent->m_pLeft)
        {
            FindPath(pCurrent->m_pLeft,sum,curval,path);
        }
        if(pCurrent->m_pRight)
        {
            FindPath(pCurrent->m_pRight,sum,curval,path);
        }
    }        
    curval -= pCurrent->m_nValue;
    path.pop_back();
}

int main()
{
    BinaryTreeNode *pRoot;
    vector<int> path;
    
    pRoot = buildTree();
    FindPath(pRoot,22,0,path);
    
    system("pause");
    return 0;
}

题目：

输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，

因此输出为该子数组的和18。

题目只要求连续最大子段和，这很简单，扫描一遍整个数组，将数组元素一个个加起来，如果大于当前最大和，则更新最大和，否则不更新，如果最大和变为负数，则将最大和置零，因为连续最大子段和不可能包含使当前最大和为负的元素。

#include <iostream>
using namespace std;

int getMaxSum(int num[],int n)
{
    int sum,max;
    sum = max = 0;
    for(int i = 0;i < n;i++)
    {
        sum+=num[i];
        if(sum > max)max = sum;
        if(sum < 0)sum = 0;
    }
    return max;
}
int main()
{
    int a[10] = {1,-8,6,3,-1,5,7,-2,0,1};
    
    cout<<getMaxSum(a,10)<<endl;
    
    system("pause");
    return 0;
}

题目：

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。

要求函数min、push以及pop的时间复杂度都是O(1)。

设置一个辅助栈，记录当前栈的最小元素，每当一个元素入栈，就判断该元素是否比当前最小元素小，如果是，则更新最小元素，否则不更新。有些同学可能会说用一个变量记录最小元素不就可以了吗，如果这样的话，万一出栈的正好是最小元素，那更新最小元素的时候就要再次搜索整个栈，时间复杂度就不是O(1)了。

#include <iostream>
using namespace std;

const int STACK_LEN = 100;

struct node
{
    int val;
    int min;
};

struct stack
{
    node data[STACK_LEN];
    int top;
};

void push(stack *stack,int val)
{
    if(stack->top < STACK_LEN)
    {
        stack->data[stack->top].val = val;
        if(stack->top > 0)
        {
            if(val < stack->data[stack->top-1].min)
            {
                stack->data[stack->top].min = val;
            }
            else 
            {
                stack->data[stack->top].min = stack->data[stack->top-1].min;
            }
        }
        else
        {
            stack->data[stack->top].min = val;
        }
        stack->top++;
    }
}

int pop(stack *stack)
{
   return stack->data[--stack->top].val; 
}

int min(stack *stack)
{
    return stack->data[stack->top-1].min;
}

int main()
{
    stack *s = new stack();
    push(s,2);
    push(s,6);
    push(s,4);
    push(s,1);
    push(s,5);
    
    while(s->top > 0)
    {
        cout<<min(s)<<endl;
        pop(s);
    }
    
    system("pause");
    return 0;
} 

题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10

/ \

6 14

/ \ / \

4 8 12 16

转换成双向链表

4=6=8=10=12=14=16。

首先我们定义的二元查找树节点的数据结构如下：

struct BSTreeNode

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

这个题不难，遍历一下即可，需要注意的是指针的链接不要出错。

#include <iostream>
using namespace std;

struct BSTreeNode
{
    int m_nValue;
    BSTreeNode *m_pLeft;
    BSTreeNode *m_pRight;
};

typedef BSTreeNode DeList;
DeList *head;
DeList *index;

//构造二叉树 
void buildBSTree(BSTreeNode *(&pCurrent),int value)
{
    if(pCurrent == NULL)
    {
        pCurrent = new BSTreeNode();
        pCurrent->m_pLeft = NULL;
        pCurrent->m_pRight = NULL;
        pCurrent->m_nValue = value;
    }
    else 
    {
        if(value < pCurrent->m_nValue)
        {
            buildBSTree(pCurrent->m_pLeft,value);
        }
        else if(value > pCurrent->m_nValue)
        {
            buildBSTree(pCurrent->m_pRight,value);
        }
    }
}

//转换成双向链表 
void convertToDeList(BSTreeNode *pCurrent)
{
    pCurrent->m_pLeft = index;
    if(index != NULL)
    {
        index->m_pRight = pCurrent;
    }
    else
    {
        head = pCurrent;
    }
    index = pCurrent;
    cout<<pCurrent->m_nValue<<endl;
}

//中序遍历二叉树 
void inOrder(BSTreeNode *pCurrent)
{
    if(pCurrent != NULL)
    {
        inOrder(pCurrent->m_pLeft);
        convertToDeList(pCurrent);
        inOrder(pCurrent->m_pRight);
    }
}

int main()
{
    BSTreeNode *pRoot = NULL;
    head = index = NULL;
    
    buildBSTree(pRoot,10);
    buildBSTree(pRoot,4);
    buildBSTree(pRoot,6);
    buildBSTree(pRoot,8);
    buildBSTree(pRoot,14);
    buildBSTree(pRoot,15);
    buildBSTree(pRoot,16);
    
    inOrder(pRoot);
    system("pause");
    
    return 0;
}

A

简单模拟题。

游戏的最大值是指游戏结束时各玩家得分的最大值，如果有多人获得最大值，则求游戏过程中最先达到或超过最大值的人。map一遍得到最大值，再map一遍就得到结果。

B

DP。

数字金字塔类型的DP。

给定一个矩阵，矩阵中的元素为非负整数，从左上角走到右下角，每次只能向下或向右走，求走过的格子中的数的乘积末尾的0的个数最少，并输出路径。

dp过程比较简单，dp[i][j][0]和dp[i][j][1]分别记录格子中的数的2、5的因子个数，每次选择小的那个格子走即可。

要注意的一点是，如果矩阵中有0，那么结果至少为1，需要特别判断一下。

dp部分代码如下：

memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    {
        int val=mat[i][j];
        while(val%2==0)
        {
            dp[i][j][0]++;
            val/=2;
        }
        while(val%5==0)
        {
            dp[i][j][1]++;
            val/=5;
        }
        if(i || j)
        {
            dp[i][j][0]+=min(get(i-1,j,0),get(i,j-1,0));
            dp[i][j][1]+=min(get(i-1,j,1),get(i,j-1,1));
        }
    }

C

计算几何。

给定平面上的三个圆，求一点与这三个圆的视角相等，视角即该点与圆的两切线的夹角。如果存在多点，则输出视角最大的点，如不存在，则输出空行。

这题的做法可以用几何的方法硬解，套模板就行了。

我用的方法是参考Qinz大神的模拟退火法。关键在于构造一个评估函数，然后用评估函数来模拟，最终退火到最优值。这里我的评估函数是点到圆的视角的方差，模拟的起始点为三圆圆心的中心点。

#include <iostream>
#include <cmath>
using namespace std;

const double eps=1e-6;

const int dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};

struct circle
{
    double x,y,r;
}c[3];

double dist(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double assess(double x,double y)
{
    double dif,ang[3];
    int i,j;
    for(i=0;i<3;i++)
        ang[i]=dist(x,y,c[i].x,c[i].y)/c[i].r;
    dif=0;
    for(i=0;i<3;i++)
        for(j=i+1;j<3;j++)
            dif+=(ang[i]-ang[j])*(ang[i]-ang[j]);
    return dif;
}

int main()
{
    double x,y;
    int i;
    double delta,curv,newv;
    x=y=0;
    for(i=0;i<3;i++)
    {
        scanf("%lf%lf%lf",&c[i].x,&c[i].y,&c[i].r);
        x+=c[i].x;
        y+=c[i].y;
    }
    x/=3;
    y/=3;
    delta=1;
    while(delta>eps)
    {
        curv=assess(x,y);
        for(i=0;i<4;i++)
        {
            newv=assess(x+delta*dir[i][0],y+delta*dir[i][1]);
            if(curv>newv)
            {
                curv=newv;
                break;
            }
        }
        if(i==4)
            delta*=0.85;
        else
        {
            x+=delta*dir[i][0];
            y+=delta*dir[i][1];
        }
    }
    if(assess(x,y)<eps)
        printf("%.5lf %.5lf\n",x,y);
    return 0;
}

A

水题，不解释。

B

简单模拟题，变种进制转换。

按照规则处理即可，但是要注意的一点是，这道题不是普通的进制转换，1对应A，26对应Z，27对应AA，0是没有字母对应的。

ans[LEN]是存储字符串的数组，col为列数。

while(col)
{
    col--;
    ans[pos++]=col%26+'A';
    col/=26;
}

C

很好的计算几何题。

题意：给定三个点，求包含这三个点的最小的正多边形的面积，边数不超过100。

解题的关键在于平面解析几何的知识。

首先把三个点连接成三角形ABC，然后作这个三角形的外接圆。假设其中一条边为AB，两端点的圆弧间有k个点（即正多边形的端点，P1,P2,...,Pk），由于正多边形的每条边对应圆心角相等，所以AOB=(k+1)AOP1，满足这样的关系的正多边形即为所求。

由于边数不大，所以枚举边数+判断就可以了。

还要注意的一点就是精度。

#include <iostream>
#include <cmath>
using namespace std;

const double pi=acos(-1.0);
const double eps=1e-4;

struct point
{
    double x,y;
};

double dist(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int main()
{
    point p[3];
    double dis[3];
    double angle;
    double pp,s,d;
    int i,j,k;
    while(scanf("%lf%lf%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y)!=EOF)
    {
        for(i=0;i<3;i++)
            dis[i]=dist(p[i],p[(i+1)%3]);
        pp=(dis[0]+dis[1]+dis[2])/2;
        s=sqrt(pp*(pp-dis[0])*(pp-dis[1])*(pp-dis[2]));
        d=dis[0]*dis[1]*dis[2]/s/2;
        for(i=3;i<101;i++)
        {
            angle=2*pi/i;
            for(j=0;j<3;j++)
                if(fmod(2*asin(dis[j]/d)+eps/10,angle)>eps)break;
            if(j==3)
            {
                printf("%.8lf\n",i*d*d*sin(2*pi/i)/8);
                break;
            }
        }
    }
    return 0;
}