The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

Coderforce ,the first time

A 就是分数化简注意一下就好,gcd
B.暴力,1个trick , 当时间相同时要求的是 到学校距离最小的那个站
#include<iostream>
#include
<cmath>
using namespace std;
struct point
{
    
double x;
    
double y;
}
;

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


double vb,vs;
double s[10000];
int n;
point t;

double GetTime(int i)
{
    
double res=0;
    res
+=(s[i]-0)/vb;
    point ss;
    ss.x
=s[i];
    ss.y
=0;
    res
+=GetDist(ss,t)/vs;
    
return res;

}


int main()
{
    
    
    
int mark=1;
    
int i,j;
    
while(scanf("%d%lf%lf",&n,&vb,&vs)!=EOF)
    
{
        
double um=999999999;
        
double mm=999999999;
        mark
=1;
        
for(i=1;i<=n;i++)
            scanf(
"%lf",&s[i]);
        scanf(
"%lf%lf",&t.x,&t.y);
        
for(i=2;i<=n;i++)
        
{
            
double tim=GetTime(i);
            
if(tim<mm)
            
{
                mm
=tim;
                point tt;
                tt.x
=s[i];
                tt.y
=0;
                um
=GetDist(tt,t);
                mark
=i;
            }

            
else if(fabs(tim-mm)<1e-8)
            
{
                point tt;
                tt.x
=s[i];
                tt.y
=0;
                
if(GetDist(tt,t)<um)
                
{

                    um
=GetDist(tt,t);
                    mark
=i;
                }


                
            }

        }

        printf(
"%d\n",mark);
    }

    
return 0;
}
C.二进制数做个预处理,然后再暴力
#include<iostream>
#include
<cmath>
using namespace std;

int dp[1000000];
int p=0;
int i;
int trans(int n)
{
    
int res=0;
    
int i;
    
for(i=0;i<10;i++)
    
{
        
if(n&(1<<i))
            res
+=pow(10.0,i);
    }

    
return res;
}




void init()
{
    
int maxn=1<<9;
    
int i;
    
for(i=1;i<=maxn;i++)
    
{
        dp[p
++]=trans(i);
    }

}


int main()
{
    
int n;
    scanf(
"%d",&n);
    init();
    
int i;
    
int res=0;
    
for(i=0;i<p;i++)
    
{
        
if(dp[i]>n)
            
break;
        res
++;

    }

    printf(
"%d\n",res);
    
return 0;
}

D.左右子树进行DP,枚举根,也就是左右子树结点数(想想是不是这样?)
#include<iostream>
using namespace std;
long long  dp[100][100];

void init()
{
memset(dp,
0xff,sizeof(dp));
}


long long dfs(int n,int h)
{
    
if(h<0||h>n) return 0;
    
if(n==0&&h>0return 0;
    
if(n>0&&h==0return 0;
    
if(n==0 && h==0return 1;
    
if(n==1 && h==1return 1;
    
if(dp[n][h]!=-1return dp[n][h];
    dp[n][h]
=0;
    
for(int l=0;l<n;l++)
    
{
        
int r=n-l-1;
        
for(int nh=0;nh<h;nh++)
            dp[n][h]
+=dfs(l,h-1* dfs(r,nh);
        
for(int nh=0;nh<h;nh++)
            dp[n][h]
+=dfs(l,nh) * dfs(r,h-1);
        dp[n][h]
-=dfs(l,h-1* dfs(r,h-1);//由于多加了一次,所以要去重
    }

    
return dp[n][h];
}






int main()
{
    
int n,h;
    
int i;
    init();
    
while(scanf("%d%d",&n,&h)!=EOF)
    
{
        
long long res=0;
        
for(i=h;i<=n;i++)
            res
+=dfs(n,i);
        printf(
"%lld\n",res);
    }

    
return 0;


}
E.不会做 :-P

posted on 2010-04-12 00:46 abilitytao 阅读(1277) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理