这么简单的算法却一直不会，真是不太应该。。

BZOJ2330 一道三分裸题，但因为姿势不太对调了挺久，然后学会了保留有效位数输出小数，只要开<iomanip>库再cout<<setprecision(m)<<f<<endl就行啦，不过这道题似乎仍然不太资磁

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int n,m,i;double ans,eps,a[25],b[25];
double cal2(double nd,double sl){
	double res=0;  
    for(int i=1;i<=n;i++){
        double s=100/(1+exp(nd-sl*a[i]));  
        if(s<1e-12||s>=100)return 1e200;  
        res+=b[i]*log(100/s)+(100-b[i])*log(100/(100-s));  
    }
    return res;
}
double cal(double nd){
	double l=0,r=1,mid1,mid2;
	while(r-l>eps){
		mid1=(l+r)/2;mid2=(mid1+r)/2;
		if(cal2(nd,mid1)>cal2(nd,mid2))l=mid1;else r=mid2;
	}
	return cal2(nd,(l+r)/2);
}
double print(double ans){
    long long a=(long long)ans;  
    int digit=0;  for(int tmp=a;tmp;tmp/=10)digit++;  
    if(m<=digit){
        int bit[100];for(*bit=0;a;a/=10)bit[++*bit]=a%10;  
        for(int i=*bit;i>=1 &&m;i--,digit--,m--)  putchar(bit[i]+'0');  
        while(digit--)putchar('0');  
    }else{
        cout<<a<<'.';m-=digit;
        while(m--)ans-=(int)ans,ans*=10,printf("%d",(int)ans);  
    }  
}
int main(){
	scanf("%d%d",&n,&m);
	eps=1.0;for(i=1;i<=m;i++)eps/=10.0;
	for(i=1;i<=n;i++)scanf("%lf",&a[i]);sort(a+1,a+n+1);
	for(i=1;i<=n;i++)b[i]=(i-1)*100.0/(n-1);
	double l=0.0,r=10.0,mid1,mid2;
	while(r-l>eps){
		 mid1=(l+r)/2;mid2=(mid1+r)/2;
		 if(cal(mid1)>cal(mid2))l=mid1;else r=mid2;
	}
	print(cal((l+r)/2));
}

BZOJ1857 更裸的三分，不过因为R变量用重复了也调了好久。。

#include<cstdio>
#include<cmath>
#define eps 1e-8
double ax,ay,bx,by,cx,cy,dx,dy,ex,ey,P,Q,R;
double dis(double x1,double y1,double x2,double y2){return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}
double cal(double a,double b){
	double l=0,r=1,mid1,mid2,x,y,ret1,ret2;
	while(r-l>eps){
		mid1=(l+r)/2;mid2=(mid1+r)/2;
		x=dx+(cx-dx)*mid1;y=dy+(cy-dy)*mid1;
		ret1=dis(a,b,ax,ay)/P+dis(a,b,x,y)/R+dis(x,y,dx,dy)/Q;
		x=dx+(cx-dx)*mid2;y=dy+(cy-dy)*mid2;
		ret2=dis(a,b,ax,ay)/P+dis(a,b,x,y)/R+dis(x,y,dx,dy)/Q;
		if(ret1>ret2)l=mid1;else r=mid2;
	}
	mid1=(l+r)/2;x=dx+(cx-dx)*mid1;y=dy+(cy-dy)*mid1;
	return dis(a,b,ax,ay)/P+dis(a,b,x,y)/R+dis(x,y,dx,dy)/Q;
}
int main(){
	scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);ex=dis(ax,ay,bx,by);
	scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);ey=dis(cx,cy,dx,dy);
	scanf("%lf%lf%lf",&P,&Q,&R);
	double l=0,r=1,mid1,mid2,x,y,ret1,ret2;
	while(r-l>eps){
		mid1=(l+r)/2;mid2=(mid1+r)/2;
		x=ax+(bx-ax)*mid1;y=ay+(by-ay)*mid1;
		ret1=cal(x,y);
		x=ax+(bx-ax)*mid2;y=ay+(by-ay)*mid2;
		ret2=cal(x,y);
		if(ret1>ret2)l=mid1;else r=mid2;
	}
	mid1=(l+r)/2;x=ax+(bx-ax)*mid1;y=ay+(by-ay)*mid1;
	printf("%.2lf",cal(x,y));
}

BZOJ3874 单调性贪心+三分，因为一个LL没开调了好久。。

#include<cstdio>
#include<algorithm>
#define N 333
using namespace std;
typedef long long LL;
LL m,f,n,i,top,midl,midr,l,r,ans,ansl,ansr;
struct EG{LL x,y;}eg[N],q[N];
bool cmp(EG a,EG b){return a.x<b.x;}
LL calc(LL x){
	LL xm,ans=0,days=0,la,i;
	xm=m-x*f;if(xm<0)return 0;
	for(i=1;i<=top;i++){
		if(days<=q[i].y){
			la=min(q[i].y-days+(LL)1,xm/q[i].x/x);
			ans+=la*x;xm-=q[i].x*x*la;
			days+=la;
		}
		if(days<=q[i].y){
			la=min(x,xm/q[i].x);
			ans+=la;xm-=q[i].x*la;days++;
		}
	}
	return ans;
}
int main(){
	scanf("%lld%lld%lld",&m,&f,&n);
	for(i=1;i<=n;i++)scanf("%lld%lld",&eg[i].x,&eg[i].y);
	sort(eg+1,eg+n+1,cmp);
	q[++top]=eg[1];
	for(i=2;i<=n;i++)if(eg[i].y>q[top].y)q[++top]=eg[i];
	l=1;r=m/(f+q[1].x);
	ans=max(calc(l),calc(r));
	while(l<=r){
		midl=l+(r-l)/(LL)3;midr=r-(r-l)/(LL)3;
		ansl=calc(midl);ansr=calc(midr);
		ans=max(ans,max(ansl,ansr));
		if(ansl<ansr)l=midl+1;else r=midr-1;
	}
	printf("%lld\n",ans);
}

BZOJ3203 很明显就是求max{sum[i]/d[i]}，由于sum[i]递增且每次相对位置不变，相当于求1~i中到点(sum[i],d*i+y)的最大斜率。可以维护一个单调队列，然后在上面三分得到答案

#include<bits/stdc++.h>
int n,i,l,r,p,t,m1,m2;double x,y,v,d,w,ans;struct Q{double x,y;}q[100100],o;
Q operator-(Q a,Q b){Q t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
double operator*(Q a,Q b){return a.x*b.y-a.y*b.x;}
double xl(Q a,Q b){return (b.y-a.y)/(b.x-a.x);}
int main(){
	for(scanf("%d%lf",&n,&d),i=1;i<=n;i++){
		for(scanf("%lf%lf",&x,&y),o=Q{d*i,v},v+=x;t>1&&(o-q[t])*(q[t]-q[t-1])>=0;)t--;
		for(w=0,q[++t]=o,o=Q{y+d*i,v},l=1,r=t;r-l>2;){
			p=(r-l+1)/3;m1=l+p;m2=r-p;
			if(xl(q[m1],o)<xl(q[m2],o))l=m1;else r=m2;
		}
		for(p=l;p<=r;p++)w=std::max(w,xl(q[p],o));ans+=w;
	}
	printf("%.0f",ans);
}

BZOJ4311 按时间建立线段树，对询问离线拉链，每个点求出凸壳后每个询问三分找答案即可

#include<bits/stdc++.h>
#define N 200200
using namespace std;typedef long long LL;
int n,m,i,x,y,t,o,tot,fir[N*3],ne[3333333],la[3333333];LL ans[N];
struct P{int x,y;}a[N],b[N],c[N],p[N],q[N];bool cmp(P a,P b){return a.x<b.x||a.x==b.x&&a.y>b.y;}
void ins(int k,int l,int r,int x,int y,int z){
	if(x<=l&&r<=y){la[++tot]=z;ne[tot]=fir[k];fir[k]=tot;return;}
	int mid=l+r>>1;if(x<=mid)ins(k<<1,l,mid,x,y,z);
	if(y>mid)ins(k<<1|1,mid+1,r,x,y,z);
}
void ask(int x){
	int l,r,w,m1,m2;LL s1,s2;
	for(l=1,r=t;l<=r;){
		w=(r-l)/3,m1=l+w,m2=r-w;s1=1ll*c[x].x*q[m1].x+1ll*c[x].y*q[m1].y;s2=1ll*c[x].x*q[m2].x+1ll*c[x].y*q[m2].y;
		if(s1>s2)r=m2-1,ans[x]=max(ans[x],s1);else l=m1+1,ans[x]=max(ans[x],s2);
	}
}
void fz(int k,int l,int r){
	int i,w=0,mid=l+r>>1;if(l<r)fz(k<<1,l,mid),fz(k<<1|1,mid+1,r);
	for(i=fir[k];i;i=ne[i])p[++w]=a[la[i]];if(!w)return;sort(p+1,p+w+1,cmp);
	for(q[t=1]=p[1],i=2;i<=w;q[++t]=p[i++])for(;t>1&&1ll*(q[t].y-q[t-1].y)*(p[i].x-q[t].x)<=1ll*(p[i].y-q[t].y)*(q[t].x-q[t-1].x);t--);
	for(i=l;i<=r;i++)if(c[i].x)ask(i);
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++){
		scanf("%d%d",&o,&x);
		if(o==1)scanf("%d",&y),a[++m]=P{x,y},b[m]=P{i,n};
		if(o==2)b[x].y=i;
		if(o==3)scanf("%d",&y),c[i]=P{x,y};
	}
	for(i=1;i<=m;i++)ins(1,1,n,b[i].x,b[i].y,i);
	for(fz(1,1,n),i=1;i<=n;i++)if(c[i].x)printf("%lld\n",ans[i]);
}

• 相关文章推荐
• 全局相关文章