Codeforces Beta Round #14 (Div. 2)

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

晚上 队内训练做的。。。难度适中
A：枚举每一个*,找到横纵坐标的最值
B：标记每一个点，然后再枚举
C：用map记录顶点，每个顶点出现两次，然后对于每一条线段，判断一下是否和坐标轴平行， 然后判断一下和某一个轴平行的是否是两条
D：枚举每一条边，断开，成了两个连通块，然后分别对两个连通块求一次树的直径，乘积最大即解

struct Node{    int u,v;}e[200];int n,a,b,ans,idx;vector<int>v[205];int bfs(int s){    bool flag[205];    int dist[205];    mem(flag,false);    queue<int>que;    mem(dist,0);    que.push(s);    dist[s]=0;    flag[s]=true;    while(!que.empty()){        int u=que.front();        que.pop();        for(int i=0;i<v[u].size();i++){            int m=v[u][i];            if((u==a&&m==b)||(u==b&&m==a)) continue;            if(flag[m]) continue;            dist[m]=dist[u]+1;            que.push(m);            flag[m]=true;        }    }    ans=0;    for(int i=1;i<=n;i++)        if(dist[i]>ans)            ans=dist[i],idx=i;    return ans==0?s:idx;}int main(){    scanf("%d",&n);    for(int i=0;i<n-1;i++){        scanf("%d%d",&e[i].u,&e[i].v);        v[e[i].u].pb(e[i].v);        v[e[i].v].pb(e[i].u);    }    int answer=0;    for(int i=0;i<n-1;i++){        a=e[i].u;b=e[i].v;        bfs(bfs(a));        int ret=ans;        bfs(bfs(b));        ret*=ans;        answer=max(answer,ret);    }    printf("%d\n",answer);    return 0;}

E：预处理出dp[i][j][k]表示对于一个峰，最左边的y值是i，最右边的y值是j，总共用了k个点的有多少种。 然后ans[i][j][k]表示已经用了i个点组成j个峰，然后最后一个峰的最右点的y值是k的有多少种。 很显然的转移，但是我是手打的表，TAT