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\n",h);
        else if(temp<temp2)printf("%.3lf\n",h*D/H);
        else
        {
            double ans=D+H-temp-(H-h)*D/temp;
            printf("%.3lf\n",ans);
        }
    }
    return ;
}

//memory:188KB  time:0ms

NO2.三分~

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

代码：

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 using namespace std; double H,h,D; double shadow(double x)
 {
     return (x+D*(h-x)/(H-x));
 } int main()
 {
     int t;
     scanf("%d",&t);
     while(t--)
     {
         scanf("%lf%lf%lf",&H,&h,&D);
         double l,left=,right=h,mid,midd;
         while(right-left>1e-)
         {
             mid=(left+right)/;
             midd=(mid+right)/;
             if(shadow(mid)>shadow(midd))
                 right=midd;
             else
                 left=mid;
         }
         printf("%.3lf\n",shadow(right));
     }
     return ;
 }

//memory：188KB  time：0ms

B.POJ 3974    Palindrome

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

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

代码：

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <string>
 using namespace std; const int MAX=;
 char a[MAX],str[MAX<<];
 int r[MAX<<],Rmax; void Manancher()
 {
     int i,j,maxx;
     int n=strlen(a);
     memset(str,'#',sizeof(str));
     for(i=;i<n;i++)
         str[(i+)<<]=a[i];
     n=(n+)<<;
     str[n]='$';
     Rmax=j=maxx=;
     for(i=;i<n;i++)
     {
         if(i<maxx)
             r[i]=min(r[*j-i],maxx-i);
         else   r[i]=;
         while(str[i-r[i]]==str[i+r[i]])
         {
             r[i]++;
         }
         if(Rmax<r[i])
             Rmax=r[i];
         if(r[i]+i>maxx)
         {
             j=i;
             maxx=r[i]+i;
         }
     }
 } int main()
 {
     int t=;
     while(~scanf("%s",a)!=EOF && a[]!='E')
     {
         Manancher();
         printf("Case %d: %d\n",t++,Rmax-);
     }
     return ;
 }

//memory:10936KB  time；188ms

C.HDU 1394     Minimum Inversion Number

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

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

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

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 using namespace std; int a[]; int main()
 {
     int n,i,j,re,sum,k;
     while(~scanf("%d",&n))
     {
          for(i=;i<n;i++)
         {
             scanf("%d",&a[i]);
             a[i+n]=a[i];
         }
         sum=;
         for(j=;j<n;j++)
         {
             for(k=j+;k<n;k++)
                 if(a[k]<a[j])
                     sum++;
         }
         re=sum;
         for(i=;i<n;i++)
         {
             sum+=n--*a[i];
             re=min(sum,re);
         }
         printf("%d\n",re);     }
     return ;
 }

//memory：268KB    time：265ms

D.HDU 3400    Line belt

…….

E.HDU 2152    Fruit

水水的题目~

代码：

 #include <iostream>
 #include <cstring>
 #include <cstdio>
 using namespace std; int c1[],c2[]; int main()
 {
     int n,m,i,j,a[],b[],k;
     while(~scanf("%d%d",&n,&m))
     {
         for(i=;i<=n;i++)
             scanf("%d%d",&a[i],&b[i]);
         memset(c1,,sizeof(c1));
         memset(c2,,sizeof(c2));
         c1[]=;
           for(i=;i<=n;i++)
           {
             for(j=;j<=m;j++)
                 for(k=a[i];k+j<=m && k<=b[i];k+=)
                 {
                     c2[k+j]+=c1[j];
                 }
             for(j=;j<=m;j++)
             {
                  c1[j]=c2[j];
                  c2[j]=;
              }
           }
         printf("%d\n",c1[m]);
     }
     return ;
 }

//memory：252KB  time：0ms