8-10-Exercise

A.ZOJ 3203 Light Bulb

这道题............哎~既可以用数学直接推导出来，也可以三分求，还可以二分求~~~~

NO1.数学公式

这种方法搞的不是很清楚..........T T .........什么时候几何这么烂了.................= =心都碎了~

感觉影子的最长的长度会在h,h*D/H,以及另外的某个数中（D+H-sqrt((H-h)*D)-(H-h)*D/sqrt((H-h)*D)）........可是判断条件.......ORZ木有弄清~

代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int T;
    double H,h,D;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf%lf%lf",&H,&h,&D);
        double temp=sqrt((H-h)*D);
        double temp2=(H-h)*D/H;
        if(temp>=D)printf("%.3lf
",h);
        else if(temp<temp2)printf("%.3lf
",h*D/H);
        else
        {
            double ans=D+H-temp-(H-h)*D/temp;
            printf("%.3lf
",ans);
        }
    }
    return 0;
}

//memory:188KB time:0ms

NO2.三分~

对在墙上的影子进行三分~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 double H,h,D;
 7 
 8 double shadow(double x)
 9 {
10     return (x+D*(h-x)/(H-x));
11 }
12 
13 int main()
14 {
15     int t;
16     scanf("%d",&t);
17     while(t--)
18     {
19         scanf("%lf%lf%lf",&H,&h,&D);
20         double l,left=0,right=h,mid,midd;
21         while(right-left>1e-10)
22         {
23             mid=(left+right)/2;
24             midd=(mid+right)/2;
25             if(shadow(mid)>shadow(midd))
26                 right=midd;
27             else
28                 left=mid;
29         }
30         printf("%.3lf
",shadow(right));
31     }
32     return 0;
33 }

//memory：188KB time：0ms

B.POJ 3974 Palindrome

由于数字较大，暴力绝对超时~

具体题解也是看的网上的博客~要用到一个叫Manancher的算法~~~~链接：http://www.cnblogs.com/lv-2012/archive/2012/11/15/2772268.html

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 using namespace std;
 6 
 7 const int MAX=1000009;
 8 char a[MAX],str[MAX<<1];
 9 int r[MAX<<1],Rmax;
10 
11 void Manancher()
12 {
13     int i,j,maxx;
14     int n=strlen(a);
15     memset(str,'#',sizeof(str));
16     for(i=0;i<n;i++)
17         str[(i+1)<<1]=a[i];
18     n=(n+1)<<1;
19     str[n]='$';
20     Rmax=j=maxx=0;
21     for(i=0;i<n;i++)
22     {
23         if(i<maxx)
24             r[i]=min(r[2*j-i],maxx-i);
25         else   r[i]=1;
26         while(str[i-r[i]]==str[i+r[i]])
27         {
28             r[i]++;
29         }
30         if(Rmax<r[i])
31             Rmax=r[i];
32         if(r[i]+i>maxx)
33         {
34             j=i;
35             maxx=r[i]+i;
36         }
37     }
38 }
39 
40 int main()
41 {
42     int t=1;
43     while(~scanf("%s",a)!=EOF && a[0]!='E')
44     {
45         Manancher();
46         printf("Case %d: %d
",t++,Rmax-1);
47     }
48     return 0;
49 }

//memory:10936KB time；188ms

C.HDU 1394 Minimum Inversion Number

肿么说呢........哎~比赛前刚做的这道题........让人淡淡的忧桑啊.......

再另一篇博客写的有这道题.............链接：忧桑啊~

代码（就只发.....暴力.....线段树在链接里有）：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int a[10050];
 7 
 8 int main()
 9 {
10     int n,i,j,re,sum,k;
11     while(~scanf("%d",&n))
12     {
13          for(i=0;i<n;i++)
14         {
15             scanf("%d",&a[i]);
16             a[i+n]=a[i];
17         }
18         sum=0;
19         for(j=0;j<n;j++)
20         {
21             for(k=j+1;k<n;k++)
22                 if(a[k]<a[j])
23                     sum++;
24         }
25         re=sum;
26         for(i=0;i<n;i++)
27         {
28             sum+=n-1-2*a[i];
29             re=min(sum,re);
30         }
31         printf("%d
",re);
32 
33     }
34     return 0;
35 }

View Code

//memory：268KB time：265ms

D.HDU 3400 Line belt

.......

E.HDU 2152 Fruit

水水的题目~

代码：

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

//memory：252KB time：0ms