8月10号小练

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

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

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

代码： 0MS

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <math.h>
 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<l2)
22                 l=mid;
23             else
24                 r=midd;
25         }
26         printf("%.3lf
",l2);
27     }
28     return 0;
29 }

这道题还有个数学方法，直接求峰值，详情见：http://blog.csdn.net/freezhanacmore/article/details/9887115 （表示膜拜，用数学方法的都膜拜）

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

优化原因见： http://www.2cto.com/kf/201210/164253.html

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

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio> 
 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]!=''; i++)
15         str1[(i+1)<<1]=str[i];    //把字符插入到#####中
16     str1[(i+1)<<1]='';   
17     mx=0;
18     maxx=0;
19     for(i=1; str1[i]!=''; 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！=END
40     {
41         maxx=0;
42         Manacher();
43         printf("Case %d: %d
",++Case,maxx); 
44     }
45 }

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

代码： 265ms

 1 #include <stdio.h>
 2 #include <iostream>
 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<n;i++)
11             scanf("%d",&a[i]);
12         for(i=0;i<n-1;i++)
13             for(j=i+1;j<n;j++)
14                 if(a[i]>a[j])
15                     sum++;   //求出初数列的个数
16         minn=sum;   //初始化最小值
17         for(i=1;i<n;i++)
18         {
19             sum1=sum+n-1-2*a[i];     //sum1=sum(上一个数列的值）+（n-1-a[i])（移到后面的那个数和最大数的差值）-a[i](比a[i]小的数的个数）
20             if(minn>sum1)
21                 minn=sum1;    //更新最小值
22             sum=sum1;   //更新上一个数列的值
23         }
24         printf("%d
",minn);
25     }
26     return 0;
27 }

D Line belt HDU 3400 三分叠三分

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

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<math.h>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<string.h>
 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)//三分CD
18 {
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         else
35             right=midmid;
36     }while(dis(left,right)>1e-5);   
37     return t2;
38 }
39 double find(point a,point b,point c,point d)   //三分AB
40 {
41     point left,right;
42     point mid,midmid;
43     double t1,t2;
44     left=a;
45     right=b;
46     do
47     {
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         else
57             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
",find(a,b,c,d));
72     }
73     return 0;
74 }

E 超级简单，母函数解决 Fruit HDU 2152

代码： 0ms

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 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
",c1[m]);
27     }
28     return 0;
29 }