posts - 2,  comments - 4,  trackbacks - 0
NOI拿块铁牌回家

滚粗了

在WC上也拿张成绩证明的我,在NOI上悲剧了

现在也休息的差不多了



还有300天不到,就要高考了

只有好好加油了



申请新的blog


总之

welcome to my blog
posted @ 2012-08-13 13:25 prime56 阅读(230) | 评论 (1)编辑 收藏
如果想看题目
出门右转
http://wenku.baidu.com/view/6b3f03a6284ac850ad0242fa.html


先吐槽一下
真是后悔啊,说到此题
考场上写出式子死磕1小时无果
决定做前40分,后面的用随机调整
可是,研究半天知道要logn..可是连三分都不会了

后来讲题是说此法有60~100分

常中的投影仪不给力,解题报告也基本没听到啥

正解是二分导数
即拉格朗日乘数法
http://baike.baidu.com/view/1211517.htm
http://zh.wikipedia.org/wiki/拉格朗日乘数
当时在讲题时听到拉格朗日我就已经决定睡觉了

回家休息了
那天复习到函数
有一道用均值不等式求多变量函数极值
我想起这个
一翻书看
后悔了
当时看高数时看完偏导数直接看多重积分去了
中间跳过的,真是拉格朗日乘数
学过导数的话,这个真的很好理解
哭啊


那么接下来将就是
1#include<stdio.h>
2#include<iostream>
3#include<algorithm>
4#include<cmath>
5#include<cstdio>
6#define rep(i,n) for(int i=0;i<n;i++)
7using namespace std;
8#define ll long long
9const int maxn=10010;
10int N;
11double E,s[maxn],v[maxn],k[maxn],maxv[maxn],tem[maxn];
12double solve(double a,double b,double c,double d,double l,double r){
13 double mid;
14 while(l+0.000000000001<r){
15 mid=(l+r)/2.0;
16 double ans=a*mid*mid*mid+b*mid*mid+d;
17 if (ans>0.0)l=mid;
18 else r=mid;
19 }

20 return (l+r)/2.0;
21}

22void file(){
23 freopen("bicycling.in","r",stdin);
24 freopen("bicycling.out","w",stdout);
25}

26int main()
27{
28 //file();
29 scanf("%d%lf",&N,&E);double low=0;
30 rep(i,N){
31 double t;
32 scanf("%lf%lf%lf",&s[i],&k[i],&v[i]);
33 if (s[i]>0)
34 maxv[i]=sqrt(E/(k[i]*s[i]))+v[i],t=-(1.0/(2*k[i]*maxv[i]*maxv[i]*(maxv[i]-v[i])));
35 else maxv[i]=s[i];
36 low=min(low,t);
37 }

38 //rep(i,N)printf("maxv %.8lf\n",maxv[i]);
39 double left=-1000,right=low,mid,sum;
40 rep(zz,60)
41 {
42 mid=(left+right)/2.0;sum=0.0;
43 rep(i,N){
44 double a=2.0*k[i]*mid;
45 tem[i]=solve(a,-a*v[i],0,1.0,max(v[i],0.000001),maxv[i]);
46 sum+=k[i]*s[i]*(tem[i]-v[i])*(tem[i]-v[i]);
47 }

48 if (sum>E)right=mid;
49 else left=mid;
50 //printf("\n ## %.10lf\n",sum);
51 }

52 long double ret;
53 ret=0.0;
54 rep(i,N)ret+=(long double)s[i]/(long double)tem[i]; printf("%.10lf\n",(double)ret);
55 return 0;
56}
程序
如上

经过cena评测
如下图

部分正确是个意外,该点手工测试是正确的


可是2.29s
这和牛顿迭代怎么比
常数优化来了

#include<stdio.h>
#include
<iostream>
#include
<algorithm>
#include
<cmath>
#include
<cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
#define ll long long
const int maxn=10010;
int N;
double E,s[maxn],v[maxn],k[maxn],maxv[maxn],tem[maxn],minv[maxn];
double solve(double a,double b,double c,double d,double l,double r){
 
double mid;
 
while(l+0.0000001<r){
  mid
=(l+r)/2.0;
 
//printf("%.10lf %.10lf\n",l,r);
  double ans=a*mid*mid*mid+b*mid*mid+d;
   
if (ans>0.0)l=mid;
 
 else r=mid;
  }
 
return (l+r)/2.0;
}
void file(){
   freopen(
"bicycling.in","r",stdin);
   freopen(
"bicycling.out","w",stdout);
}
int main()
{
 
 //file();
   scanf("%d%lf",&N,&E);double low=0;
   rep(i,N){
   
double t=0;
   scanf(
"%lf%lf%lf",&s[i],&k[i],&v[i]);
   
if (s[i]>0)
   maxv[i]
=sqrt(E/(k[i]*s[i]))+v[i],t=-(1.0/(2*k[i]*maxv[i]*maxv[i]*(maxv[i]-v[i])));
   
else maxv[i]=v[i];
   minv[i]
=max(0.000001,v[i]);
   low
=min(low,t);
   }
   
double left=-1,right=low,mid,sum;
   rep(zz,
80)
   {
      mid
=(left+right)/2.0;sum=0.0;// 请不要用 while(left+0.0000000001<right) 那个的精度连样例都过不了
     rep(i,N){
     
double a=2.0*k[i]*mid;
     tem[i]
=solve(a,-a*v[i],0,1.0,minv[i],maxv[i]);
     sum
+=k[i]*s[i]*(tem[i]-v[i])*(tem[i]-v[i]);//printf(" $$ %.10lf\n",sum);
     }
 
//rep(i,N)printf("%.6lf ",tem[i]);
     if (sum>E){
         right
=mid;
         rep(i,N)maxv[i]
=tem[i];
        }
        else{
        left
=mid;
        rep(i,N)minv[i]
=tem[i];
       }
   
 if (fabs(sum-E)<0.00000001)break;
   
 //printf("\n ## %.10lf\n",sum);
     
//printf("%.10lf\n",(double)clock()/CLOCKS_PER_SEC);
   }
 
 long double ret;
   ret
=0.0;
   
//printf("\n");
   rep(i,N)if (s[i]>0)ret+=(long double)s[i]/(long double)tem[i];
   printf(
"%.10lf\n",(double)ret);
   
return 0;
}

时间如下:



时间快了很多

当然,你也可以写牛顿迭代




这道题


据说此题与某省选题巨像,我记不起来了

路过的各位有知道的麻烦给我说一下,谢谢

prime56原创....转载请注明




posted @ 2012-08-13 19:45 prime56 阅读(3822) | 评论 (3)编辑 收藏
NOI拿块铁牌回家

滚粗了

在WC上也拿张成绩证明的我,在NOI上悲剧了

现在也休息的差不多了



还有300天不到,就要高考了

只有好好加油了



申请新的blog


总之

welcome to my blog
posted @ 2012-08-13 13:25 prime56 阅读(230) | 评论 (1)编辑 收藏
仅列出标题  
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜