网站：

A 三分的题目，给出灯高，人高，以及和墙的距离，求最长的影子长度。            

本来我是三分角度，角度[0,atan(H/D)]，测试数据都是对的，但是WA了，我到现在还是不知道为什么........

后来是三分投在墙上的影子长度，[0,h]，投在墙上的影子最多是h。

代码：     0MS

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 int main() 6 { 7     double H,h,D,l,r,mid,midd,l1,l2; 8     int T; 9     scanf("%d",&T);10     while (T--)11     {12         scanf("%lf%lf%lf",&H,&h,&D);13         r=h;14         l=0;15         while(r-l>1e-9)16         {17             mid=(l+r)/2;18             midd=(mid+r)/2;19             l1=mid+D*(h-mid)/(H-mid);20             l2=midd+D*(h-midd)/(H-midd);21             if(l1
       
      
     

这道题还有个数学方法，直接求峰值，详情见： （表示膜拜，用数学方法的都膜拜）

B   求最长回文子串的长度，如果暴力0(n^2）果断超时，要用Manacher算法。

优化原因见：  

代码： 360 ms/15000ms     10936kb/65536kb     这道题的时间限制真长......从没做过15s的题Orz

1 #include
     
       2 #include
      
        3 #include
       
          4 using namespace std; 5 #define N 1000008 6 char str[N], str1[N<<1]; 7 int p[N<<1]; 8 int maxx; 9 void Manacher()10 {11     int i, j, mx, id;12     memset(str1, '#', sizeof(str1));13     memset(p, 0, sizeof(p));    14     for(i=0; str[i]!='\0'; i++)15         str1[(i+1)<<1]=str[i];    //把字符插入到#####中16     str1[(i+1)<<1]='\0';   17     mx=0;18     maxx=0;19     for(i=1; str1[i]!='\0'; i++)20     {21        if( mx>i ) 22            p[i]=min(mx-i, p[id*2-i]);    //见：http://www.cnblogs.com/lv-2012/archive/2012/11/15/2772268.html    PS:没有这一步会超时23         else 24             p[i]=1; 25         while( str1[i-p[i]]==str1[i+p[i]] )    //拓展半径26             p[i]++;        27         if( i+p[i]>mx )//mx代表当前回文串扩展的最大距离 28         {29             mx=i+p[i];  30             id=i;31         }         32         if( p[i]-1>maxx )    33             maxx=p[i]-1;    //更新最长长度34     }    35 }36 int main()37 {38     int Case=0;39     while( scanf("%s", str) && strcmp(str, "END")!=0 )   //str！=END40     {41         maxx=0;42         Manacher();43         printf("Case %d: %d\n",++Case,maxx); 44     }45 }
       
      
     

C          大意是给n个数，分别是0~n-1，前面的数比后面的数大的数对有多少个，算好之后把第一个数移到最后，又算.......最后求最小的数对是多少个。此题用线段树做，但是我还没看线段树，过一阵再补上，先讲下不用线段树的做法。

代码  ：   265ms

1 #include 
     
       2 #include 
      
        3 using namespcae std; 4 int main() 5 { 6     int n,i,j,sum,minn,sum1 7     while(~scanf("%d",&n)) 8     { 9         sum=0;10         for(i=0;i
       
        a[j])15                     sum++;   //求出初数列的个数16         minn=sum;   //初始化最小值17         for(i=1;i
        
         sum1)21                 minn=sum1;    //更新最小值22             sum=sum1;   //更新上一个数列的值23         }24         printf("%d\n",minn);25     }26     return 0;27 }
        
       
      
     

D           三分叠三分

代码：     0MS ，注意不能用while，用do....while，因为至少要执行一次，算AB,CD 间的距离

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 struct point 9 {10 double x,y;11 };12 double dis(point a,point b)13 {14 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); //求两点间距离15 }16 double p,q,r;17 double find2(point a,point c,point d)//三分CD18 {19 point left,right;20 point mid,midmid;21 double t1,t2;22 left=c;23 right=d;24 do 25 {26 mid.x=(left.x+right.x)/2;27 mid.y=(left.y+right.y)/2;28 midmid.x=(mid.x+right.x)/2;29 midmid.y=(mid.y+right.y)/2;30 t1=dis(a,mid)/r+dis(mid,d)/q;31 t2=dis(a,midmid)/r+dis(midmid,d)/q; //ids(a,mid)是求AB,CD间的距离32 if(t1>t2)33 left=mid;34 else35 right=midmid;36 }while(dis(left,right)>1e-5); 37 return t2;38 }39 double find(point a,point b,point c,point d) //三分AB40 {41 point left,right;42 point mid,midmid;43 double t1,t2;44 left=a;45 right=b;46 do47 {48 mid.x=(left.x+right.x)/2;49 mid.y=(left.y+right.y)/2;50 midmid.x=(mid.x+right.x)/2;51 midmid.y=(mid.y+right.y)/2;52 t1=dis(a,mid)/p+find2(mid,c,d);53 t2=dis(a,midmid)/p+find2(midmid,c,d);54 if(t1>t2)55 left=mid;56 else57 right=midmid;58 }while(dis(left,right)>=1e-5);59 return t2;60 }61 int main()62 {63 int T;64 point a,b,c,d;65 scanf("%d",&T);66 while(T--)67 {68 scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);69 scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);70 scanf("%lf%lf%lf",&p,&q,&r);71 printf("%.2lf\n",find(a,b,c,d));72 }73 return 0;74 }
          
         
        
       
      
     

E   超级简单，母函数解决    

代码：    0ms

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 int a[105],b[105]; 6 int c1[10005],c2[10005]; 7 int main() 8 { 9     int n,m,i,j,k;10     while(~scanf("%d%d",&n,&m))11     {12         for(i=1;i<=n;i++)13             scanf("%d%d",&a[i],&b[i]);14         memset(c1,0,sizeof(c1));15         memset(c2,0,sizeof(c2));16         c1[0]=1;17         for(i=1;i<=n;i++)18         {19             for(j=0;j<=m;j++)20                 for(k=a[i];j+k<=m&&k<=b[i];k++)21                 c2[j+k]+=c1[j];22             for(j=0;j<=m;j++)23                 c1[j]=c2[j];24             memset(c2,0,sizeof(c2));25         }26         printf("%d\n",c1[m]);27     }28     return 0;29 }