感觉这次考试的题目和USACO上的Elite 2010 U S Open Competition很像，第一题动规，第二题可以树规，第三题更是惊人的只是加了一个外壳！
不过鉴于本人那次USACO的月赛考挂了，所以这次也考得不理想。恩，总共120分。
恩，这份题解都是依靠大牛们的解题思路来弄的，可能思路写得有点短而代码又写得很长，恩，将就看吧。
第一题是动态规划，加斜率优化（感谢RJ和LJL让我知道世上还有这么神奇的东西）。
恩，动规方程是f[i]=max{f[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c}，关于斜率优化，推荐去百度一下[我写了一篇，所以推荐看一下我写的，呵呵，点这里]。
第二题，当K=1时直接最长链，当K=2时，先求一个最长链，然后分两种情况，一种是在去掉先前的最长链上的边后得到的很多小树上再求最长链，另一种是找两棵小树，最大化它们以在链上的点为根时的深度和减去这两个根的距离。
下图描述的是第二种情况，假设黑色的为第一次找到的最长链，则小树A、B、C、D的深度分别为3、3、4、3。然后最优的是选B和C，因为B和C的距离为1，然后3+4-1得6，是max{height(i)+height(j)-distance(i,j),i,j=A|B|C|D and i!=j}。
第三题不写了，如果有听懂陈丹琦的思路的可以看一下这个这个，主要是第三题的。
恩，贴代码。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-5-13
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
#define MAXN 1000000
int n,a,b,c;
int x[MAXN+2];
long long int sum[MAXN+2];
int head,tail;
int q[MAXN+2];
long long int f[MAXN+2];
long long int answer;
double k(int i,int j)
{
return double(f[i]-f[j]+a*(sum[i]*sum[i]-sum[j]*sum[j])+b*(sum[j]-sum[i]))/double(2*a*(sum[i]-sum[j]));
}
void print_long_long_int(long long int value)
{
if (value>=10) print_long_long_int(value/10),printf(“%d”,value%10);
else printf(“%d”,value);
}
bool isNumber[256];
void read(int& who)
{
char get,flag=’+’;
if ((get=getchar())==’-‘)
{
flag=’-‘;
who=0;
}
else who=get-‘0’;
while (isNumber[get=getchar()]) who=who*10+get-‘0’;
if (flag==’-‘) who=-who;
}
int main()
{
//freopen(“commando.in”,”r”,stdin);
//freopen(“commando.out”,”w”,stdout);
isNumber[‘0’]
=isNumber[‘1’]
=isNumber[‘2’]
=isNumber[‘3’]
=isNumber[‘4’]
=isNumber[‘5’]
=isNumber[‘6’]
=isNumber[‘7’]
=isNumber[‘8’]
=isNumber[‘9’]
=true;
read(n);
read(a);
read(b);
read(c);
//scanf(“%d%d%d%d”,&n,&a,&b,&c);
for (int i=1;i<=n;i++) read(x[i]);//scanf(“%d”,x+i);
for (int i=1;i<=n;i++)
sum[i]=sum[i-1]+x[i];
//f[i]=max{f[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c}
q[tail]=0;
for (int i=1;i<=n;i++)
{
while (head<tail&&k(q[head],q[head+1])<=sum[i]) head++;
long long int x=sum[i]-sum[q[head]];
f[i]=f[q[head]]+(a*x+b)*x+c;
while (head<tail&&k(q[tail-1],q[tail])>=k(q[tail],i)) tail–;
q[++tail]=i;
}
answer=f[n];
print_long_long_int(answer);
printf(“\n”);
//fclose(stdin);
//fclose(stdout);
return 0;
}
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-5-13
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
#include <string.h>
#define MAXN 100000
struct Edge{Edge* next;int to;};
int n,K;
Edge* link[MAXN+2];
void addEdge(int u,int v)
{
static int top;
static Edge pool[(MAXN+2)*2];
pool[top].next=link[u];
pool[top].to=v;
link[u]=pool+top++;
pool[top].next=link[v];
pool[top].to=u;
link[v]=pool+top++;
}
int deepest;
int deepest_node;
bool visited[MAXN+2];
void dfs(int node,int depth=0)
{
if (depth>=deepest)
{
deepest=depth;
deepest_node=node;
}
visited[node]=true;
for (Edge* i=link[node];i;i=i->next)
if (!visited[i->to])
dfs(i->to,depth+1);
}
bool marked[MAXN+2];
int top;
int list[MAXN+2];
bool dfs_mark(int node,int target)
{
visited[node]=true;
if (node==target) marked[node]=true;
for (Edge* i=link[node];i;i=i->next)
if (!visited[i->to])
if (dfs_mark(i->to,target))
marked[node]=true;
if (marked[node]) list[top++]=node;
return marked[node];
}
void dfs_2nd_circle(int node,int depth=0,int father=0)
{
if (depth>=deepest)
{
deepest=depth;
deepest_node=node;
}
for (Edge* i=link[node];i;i=i->next)
if (i->to!=father&&!marked[i->to])
dfs_2nd_circle(i->to,depth+1,node);
}
int main()
{
//freopen(“patrol.in”,”r”,stdin);
//freopen(“patrol.out”,”w”,stdout);
scanf(“%d%d”,&n,&K);
for (int i=1;i<n;i++)
{
int u,v;
scanf(“%d%d”,&u,&v);
addEdge(u,v);
}
if (K==1)
{
memset(visited,0,sizeof(visited));
deepest=0;
dfs(1);
memset(visited,0,sizeof(visited));
deepest=0;
dfs(deepest_node);
printf(“%d\n”,deepest+1+(n-1-deepest)*2);
}
else
{
int answer_1st,answer_2nd;
int u,v;
memset(visited,0,sizeof(visited));
deepest=0;
dfs(1);
u=deepest_node;
memset(visited,0,sizeof(visited));
deepest=0;
dfs(deepest_node);
v=deepest_node;
memset(visited,0,sizeof(visited));
dfs_mark(v,u);
answer_1st=deepest;
//for (int i=1;i<=n;i++)
// if (marked[i]) printf(“marked:%d\n”,i);
answer_2nd=0;
for (int j=0,i;j<top;j++)
if (marked[i=list[j]])
{
marked[i]=false;
deepest=0;
dfs_2nd_circle(i);
deepest=0;
dfs_2nd_circle(deepest_node);
if (deepest>answer_2nd) answer_2nd=deepest;
marked[i]=true;
//printf(“deepest:%d\n”,deepest);
}
int outer;
outer=0;
for (int j=0,i;j<top;j++)
if (marked[i=list[j]])
{
marked[i]=false;
deepest=0;
dfs_2nd_circle(i);
if (deepest+outer>answer_2nd) answer_2nd=deepest+outer;
outer=(deepest>?outer)-1;
marked[i]=true;
//printf(“deepest:%d\n”,deepest);
}
printf(“%d\n”,(answer_1st+1+answer_2nd+1)+(n-1-answer_1st-answer_2nd)*2);
}
return 0;
}
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-5-14
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
#include <math.h>
#include <utility>
#define MAXN 1500
#define x first
#define y second
#define Point pair<int,int>
#define P(a,b) Point(a,b)
using namespace std;
int n;
int x[MAXN+2],y[MAXN+2];
Point p[MAXN+2];
long long int total;
long long int counter;
/*
void get(int a,int b,int c)
{
double xa=x[a],xb=x[b],xc=x[c];
double ya=y[a],yb=y[b],yc=y[c];
double a1=2*(xb-xa),b1=2*(yb-ya),c1=xa*xa+ya*ya-xb*xb-yb*yb;
double a2=2*(xc-xa),b2=2*(yc-ya),c2=xa*xa+ya*ya-xc*xc-yc*yc;
double X=-(c1*b2-c2*b1)/(a1*b2-a2*b1);
double Y=-(c1*a2-c2*a1)/(b1*a2-b2*a1);
double sqr_dis=(x[a]-X)*(x[a]-X)+(y[a]-Y)*(y[a]-Y);
for (int d=0;d<n;d++)
if ((x[d]-X)*(x[d]-X)+(y[d]-Y)*(y[d]-Y)<=sqr_dis+0.01) counter++;
}
*/
struct Compare
{
static
inline
long long int cross(const Point& a,const Point& b)
{
return (long long int)(a.x)*(long long int)(b.y)-(long long int)(b.x)*(long long int)(a.y);
}
static
inline
bool less(const Point& a,const Point& b)
{
return cross(a,b)>0;
}
static
void sort(Point* l,Point* r)
{
Point* i=l;
Point* j=r;
Point mid=*(l+((r-l)>>1));
while (i<=j)
{
while (less(*i,mid)) i++;
while (less(mid,*j)) j–;
if (i<=j)
{
Point s=*i;
*i=*j;
*j=s;
i++;
j–;
}
}
if (l<j) sort(l,j);
if (i<r) sort(i,r);
}
};
long long int C(long long int n,long long int m)
{
if (m>n||m<0) return 0;
long long int c=1;
for (int i=1;i<=m;i++) c=c*(n-i+1)/i;
return c;
}
int count(int O)
{
Point np[MAXN+2];
int nn=0;
for (int i=0;i<n;i++) if (i!=O) np[nn++]=Point(p[i].x-p[O].x,p[i].y-p[O].y);
Compare compare;
compare.sort(np,np+nn-1);
int result=0;
for (int i=0,j=0;i<nn;i++)
{
while (compare.less(np[i],np[(j+1)%nn])) j=(j+1)%nn;
int get=(j-i+nn)%nn;
if (get>=2) result+=((get)*(get-1))>>1;//C(get,2);
}
return result;
}
int main()
{
//freopen(“signaling.in”,”r”,stdin);
//freopen(“signaling.out”,”w”,stdout);
scanf(“%d”,&n);
for (int i=0;i<n;i++)
scanf(“%d%d”,x+i,y+i);
/*
for (int a=0;a<n;a++)
for (int b=a+1;b<n;b++)
for (int c=b+1;c<n;c++)
get(a,b,c),total++;
*/
for (int i=0;i<n;i++)
p[i]=P(x[i],y[i]);
for (int i=0;i<n;i++)
counter+=count(i);
counter+=C(n,4)*2-C(n-1,3)*n;
total=C(n,3);
printf(“%f\n”,double(counter)/double(total)+3);
//fclose(stdin);
//fclose(stdout);
return 0;
}