Problem A  

题目大意就是说有一根细丝，在受热后会膨胀产生形变，变为一个圆弧，给出圆弧变化前后的长度，求这根细丝在水平上升高了多少

解题过程：由于题目呢给定了说形变不会是细丝变为超过一个半圆的形状，所以我们就可以对形变的高度二分假设升高了x，那么设圆的半径为R，就存在公式

                                R^2 - (R-x)^2 = (L/2)^2       其中L是细丝变化前的长度

解出来                       R = x/2 + (L*L)/(8*x);

然后可以求出圆心角      Sita = 2 * asin((L/2) / R);

在比较R*Sita与L1(形变后的长度)   其实这里我也没有证明它在0~（L/2）之间是严格递增或是严格递减的，反而证明出了在这个区间他是有增有减的，所以我很郁闷，暂且只能放在这里了，代码是直接二分给出的，我三分求最大值后，再在最小到最大值之间二分反而错了，实在是无解了，网大神指点

1 #include 
     
       2 #include 
      
        3  4 const double eps1 = 1e-4; 5 double L,L1,n,C; 6  7 int main() 8 { 9     while(~scanf("%lf%lf%lf", &L, &n, &C) && (L!=-1))10     {11         if(!L || !n || !C) {printf("0.000\n"); continue;}12         L1 = L * (1 + n * C);13         double l = 0, r = L/2,mid,R,Sita;14         while(r-l>eps1)15         {16             mid = (l+r)/2;17             R = mid/2 + L*L/mid/8;18             Sita = 2 * asin(L/2/R);19             if(Sita * R > L1) r = mid;20             else l = mid;21         }22         printf("%.3lf\n", mid);23     }24     return 0;25 }
      
     

 

 

Problem B  

还没有搞出

 

 

Problem C  

题目大意是说给出n个牛棚和m头牛，目标是将m头牛放进n个牛棚中去，且要让他们两两之间的距离尽量大，求这时最小的两个有牛的牛棚之间的距离

目标是要让有牛的牛棚之间的距离尽量大，且那时距离最小的两个牛棚之间的距离，那我们就可以直接二分这个最小距离，如果当前这个最小距离可以满足把所有的牛全部放进去，而且还有多的牛棚，那就二分他与最大值之间的距离，否则二分他与最小值之间的中点

以下是章爷的代码

1         #include 
     
       2         #include 
      
        3         #include 
       
         4         #include 
        
          5         #include 
         
           6         #include 
          
            7 #include 
           
             8 #define LL long long 9 using namespace std;10 const int inf=0x3f3f3f3f;11 const int maxn=100000+10;12 int x[maxn],c,n;13 int judge(int val)14 {15 int i,sum=1,cur=0;16 for(i=1;i
            
             =val)20 {21 sum++;22 cur=0;23 }24 else cur+=x[i];25 }26 if(sum==c) return 1;27 else return 0;28 }29 int main()30 {31 cin>>n>>c;32 int i;33 for(i=0;i
             
              =1;i--) x[i]=x[i]-x[i-1];36 int low=0,high=1000000001,mid;37 while(high>low)38 {39 mid=low+(high-low)/2;40 if(judge(mid)) low=mid+1;41 else high=mid;42 }43 printf("%d\n",low-1);44 return 0;45 }
             
            
           
          
         
        
       
      
     

 

Problem D  

题目是说给出一系列的A，B和C，以及一些和sum，要你对每一个sum从A，B和C数组中分别找出一个使他们的和为当前这个sum，最开始做的时候哦直接枚举A和B，然后用sum减去每一个C，再二分这个数组，居然发现超时了。

仔细一分析，有1000个sum，500个A，500个B，再加上二分sum-C，时间复杂度就是O（1000 * 500 * 500 * log500）,明显超时了，后来章爷突发灵感，吧A+B保存起来，再对每一个sum-C数组，二分A+B这样复杂度就是O（1000 * 500 * log250000）,可以过了，挂拉呱啦敲完了，过了！！！膜拜章爷啊啊啊~~~

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 int a[505],b[505],c[505],ab[250005]; 6 int A,B,C,AB,X,S; 7  8 int find_AB(int sum) 9 {10     int l=0,r=AB-1;11     while(l<=r)12     {13         int x=(l+r)>>1;14         if(sum == ab[x]) return 1;15         else if(sum < ab[x]) r = x-1;16         else l=x+1;17     }18     return 0;19 }20 21 22 int main()23 {24     int Case=1;25     while(~scanf("%d%d%d",&A, &B, &C))26     {27         for(int i=0;i
      
     

 

 

Problem E   简单的二分

1 #include 
     
       2 #include 
      
        3 #define eps 1e-10 4  5 double f(double x) 6 { 7     return 8*pow(x,(double)4) + 7*pow(x,(double)3) + 2*pow(x,(double)2) + 3*x + 6; 8 } 9 10 int main()11 {12     int T;13     while(~scanf("%d", &T))while(T--)14     {15         double l = 0, r = 100, x, y;16         scanf("%lf", &y);17         if(y<6 || f(100)
       
         y)r = x;24             else break;25         }26         printf("%.4lf\n", x);27     }28     return 0;29 }
       
      
     

 

 

Problem F

求函数的最小值，就只需要将方程求导，倒数为0的点就是所求，接下来就是同上了

1 #include 
     
       2 #include 
      
        3 #define eps 1e-10 4  5 double x,y; 6  7 double f(double x) 8 { 9     return 42*pow(x,(double)6) + 48*pow(x,(double)5) + 21*pow(x,(double)2) + 10*x ;10 }11 12 double g(double x)13 {14     return 6 * pow(x,7)+ 8*pow(x,6) + 7*pow(x,3) + 5*pow(x,2) - y*x;15 }16 17 int main()18 {19     int T;20     while(~scanf("%d", &T))while(T--)21     {22         double l = 0, r = 100;23         scanf("%lf", &y);24         if(y<6 || f(100)
       
         y)r = x;31             else break;32         }33         printf("%.4lf\n", g(x));34     }35     return 0;36 }
       
      
     

 

 

Problem G  

这道题要求从0 0 打到x y已知初速度的最小出射角度，我的方法是按照公式

y = Vsin(Sita)*t - G*t^2/2和

x = Vcos(Sita)*t;

对于已知可以达到x求出可以达到最高的y的角度，再在0到这个范围二分

之所以要求出到达x时所能到达的最高高度，是由于将t消去（下面的式子代入上式）后，y不是单调函数而是先增后减，而题目又是要求最小的出射角，那我们必然可以求出最大高度时的角度，那么角度在0到这个范围中一定有一个是原来的解，二分即可

1 #include 
     
       2 #include 
      
        3 const double eps = 1e-10; 4 const double eps1 = 1e-7; 5 const double pi = 4 * atan(1.0); 6 const double G = 9.8; 7 double V, x, y; 8  9 10 double f(double sita)11 {12     return V*sin(sita)*x/(V*cos(sita)) - (G*x*x)  /  ( 2 * V * V * (cos(sita) * cos(sita))  ) ;13 }14 15 int main()16 {17     int T;18     while(~scanf("%d", &T))while(T--)19     {20         scanf("%lf %lf %lf", &x, &y, &V);21 22         if(x==0 && (V*V/(2*G)-y) > eps ){printf("%lf\n",pi/2); continue;}23         else if(x==0 && (y - V*V/(2*G))>eps ){printf("-1\n"); continue;}24 25         double  l = 0, r = pi/2+0.5;26         double mid = 0, midmid = pi/2;27         while(midmid - mid > eps)28         {29             mid = (l+r)/2;30             midmid = (mid+r)/2;31             double mid_val = f(mid);32             double midmid_val = f(midmid);33             if(midmid_val < mid_val)   r = midmid;34             else l = mid;35         }36         if(y > f(mid)){printf("-1\n"); continue;}37         double ans = 0;38         l = 0, r = mid;39         while(1)40         {41             mid = (l+r)/2;42             double temp = f(mid);43             if(fabs(y - temp) < eps1){ans = mid;break;}44             else if(temp < y)  l = mid;45             else r = mid;46         }47         printf("%lf\n", ans);48     }49     return 0;50 }
      
     

 

Problem H  

暂未搞出