注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

APIO2010  

2010-05-13 21:48:35|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

感觉这次考试的题目和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}。

APIO2010解题报告 - 天之骄子 - 天之骄子的家

第三题不写了,如果有听懂陈丹琦的思路的可以看一下这个这个,主要是第三题的。

恩,贴代码。

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;

}

 

  评论这张
 
阅读(1427)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018