Codeforces Beta Round #14 (Div. 二)
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