bzoj2876 [NOI2012]骑行川藏
求条件极值 min f(x)=∑i si/xi,g(x)=E-∑i ki*(xi-vi)2*si=0
构造拉格朗日函数L(x)=f(x)-λ*g(x),λ为拉格朗日乘数
则有f(x)取极值时,有Lxi(x)=0,g(x)=0
二分λ,解方程Lxi(x)=2*λ*ki*si*(xi-vi)-si/xi2=0再带入g(x)=0中去验证
整理得:2*λ*ki*xi2*(xi-vi)=1
看起来, 这个方程似乎不太好解。。。
题目中还蕴含一个条件:xi>vi且xi>0,我们总不能倒着走对吧。。。
所以,这个函数在满足题意的定义域内单调,就可以二分求解了
#include <stdio.h> #include <string.h> #include <algorithm> #define eps 1e-12 #define inf 1e12 using namespace std; const int MAXN=10005; typedef long double db; int n; db x[MAXN]; double s[MAXN],k[MAXN],v[MAXN],E; db ans; inline db equation(int i){ db l=max(0.,v[i]),r=inf; while(r-l>eps){ db m=(l+r)/2.; if(ans*2.*k[i]*(m-v[i])*m*m-1.>0)r=m; else l=m; } return l; } inline db phi(){ db res=0; for(int i=1;i<=n;++i) res+=k[i]*s[i]*(x[i]-v[i])*(x[i]-v[i]); return res-E; } inline db calc(){ db res=0; for(int i=1;i<=n;++i) res+=s[i]/x[i]; return res; } inline void Init(){ scanf("%d%lf",&n,&E); for(int i=1;i<=n;++i) scanf("%lf%lf%lf",s+i,k+i,v+i); } inline void Solve(){ db l=0,r=inf; while(r-l>eps){ ans=(l+r)/2.; for(int i=1;i<=n;++i) x[i]=equation(i); if(phi()>eps)l=ans; else r=ans; } ans=calc(); printf("%.8f\n",(double)ans); } int main(){ Init(); Solve(); return 0; }
用kd-tree水过的cdq分治
bzoj2253 纸箱堆叠
求三维严格上升子序列长度
sort 一维,然后上kd-tree就好。。。随机数据kd-tree跑得飞快
#include <math.h> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define g() getchar() template<class Q>void Scan(Q&x){ char c;int f=1; while(c=g(),c<48||c>57)if(c=='-')f=-1; for(x=0;c>47&&c<58;c=g())x=10*x+c-48; x*=f; } #define inf 0x7f7f7f7f #define Max(x,y) if(x<y)x=y #define Min(x,y) if(x>y)x=y #define rep(i,a,b) for(int i=a;i<b;++i) typedef long long ll; typedef double db; const int MAXN=50005; int D; struct node{ int d[2],id; inline bool operator<(const node&o)const{ return d[D]<o.d[D]; } }kd[MAXN]; int p[MAXN],ch[MAXN][2],val[MAXN]; int mx[MAXN][2][2],mxv[MAXN]; bool ban[MAXN]; inline void update(int x){ rep(i,0,2){ mx[x][i][0]=ban[x]?inf:kd[x].d[i]; mx[x][i][1]=ban[x]?-inf:kd[x].d[i]; } mxv[x]=ban[x]?-inf:val[x]; int y; rep(d,0,2) if((y=ch[x][d])){ rep(i,0,2){ Max(mx[x][i][1],mx[y][i][1]); Min(mx[x][i][0],mx[y][i][0]); } Max(mxv[x],mxv[y]); } } int build(int l,int r,int d){ if(l>r)return 0; int x=(l+r)>>1; D=d,nth_element(kd+l,kd+x,kd+r+1); ch[x][0]=build(l,x-1,d^1); ch[x][1]=build(x+1,r,d^1); rep(i,0,2)p[ch[x][i]]=x; return update(x),x; } int ans,qy[2][2]; inline bool out(int x){ if(!x)return 1; rep(i,0,2){ if(mx[x][i][1]<qy[i][0])return 1; if(mx[x][i][0]>qy[i][1])return 1; } return 0; } inline bool in(int x){ rep(i,0,2){ if(mx[x][i][1]>qy[i][1])return 0; if(mx[x][i][0]<qy[i][0])return 0; } return 1; } void query(int x){ if(out(x))return; if(mxv[x]<=ans)return; if(in(x)){ ans=mxv[x]; return; } if(!ban[x]&&val[x]>ans){ bool flag=1; rep(i,0,2){ if(kd[x].d[i]<qy[i][0])flag=0; if(kd[x].d[i]>qy[i][1])flag=0; } if(flag)ans=val[x]; } bool d=mxv[ch[x][1]]>mxv[ch[x][0]]; query(ch[x][d]),query(ch[x][d^1]); } int rt,pos[MAXN]; int a,P,n,dp[MAXN]; inline int rand_a(){ static int x=1; return x=1ll*x*a%P; } struct data{ int x,y,z; inline void scan(){ x=rand_a(),y=rand_a(),z=rand_a(); int tx=max(x,max(y,z)); int tz=min(x,min(y,z)); int ty=1ll*x+y+z-tx-tz; x=tx,y=ty,z=tz; } inline bool operator<(const data&o)const{ return x<o.x; } }d[MAXN]; inline void Init(){ Scan(a),Scan(P),Scan(n); rep(i,1,n+1)d[i].scan(); } inline void modify(int x,int y){ x=pos[x],ban[x]=0,val[x]=y; for(int i=x;i;i=p[i])update(i); } inline void Solve(){ sort(d+1,d+1+n); rep(i,1,n+1){ kd[i].d[0]=d[i].y; kd[i].d[1]=d[i].z; kd[i].id=i; ban[i]=1; } rt=build(1,n,0); rep(i,1,n+1)pos[kd[i].id]=i; int res=1,ans1=1; rep(i,1,n+1){ if(d[i].x!=d[res].x){ for(;res<i;++res)modify(res,dp[res]); } ans=0; qy[0][0]=0,qy[0][1]=d[i].y-1; qy[1][0]=0,qy[1][1]=d[i].z-1; query(rt); dp[i]=ans+1; Max(ans1,dp[i]); } printf("%d\n",ans1); } int main(){ Init(); Solve(); return 0; }
bzoj3262 陌上花开
每朵花有3个属性,求每朵花优于(3个属性都大于等于)多少朵花。
还是sort 一维,这题数据不随机,kd-tree只能贴线低飞。。。
#include <math.h> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define g() getchar() template<class Q>void Scan(Q&x){ char c;int f=1; while(c=g(),c<48||c>57)if(c=='-')f=-1; for(x=0;c>47&&c<58;c=g())x=10*x+c-48; x*=f; } #define inf 0x7f7f7f7f #define Max(x,y) if(x<y)x=y #define Min(x,y) if(x>y)x=y #define rep(i,a,b) for(int i=a;i<b;++i) typedef long long ll; typedef double db; const int MAXN=100005; int D; struct node{ int d[2],id; inline bool operator<(const node&o)const{ return d[D]<o.d[D]; } }kd[MAXN]; int p[MAXN],ch[MAXN][2]; int mx[MAXN][2][2],sum[MAXN]; bool ban[MAXN]; inline void update(int x){ rep(i,0,2){ mx[x][i][0]=ban[x]?inf:kd[x].d[i]; mx[x][i][1]=ban[x]?-inf:kd[x].d[i]; } sum[x]=ban[x]?0:1; int y; rep(d,0,2) if((y=ch[x][d])){ rep(i,0,2){ Max(mx[x][i][1],mx[y][i][1]); Min(mx[x][i][0],mx[y][i][0]); } sum[x]+=sum[y]; } } int build(int l,int r,int d){ if(l>r)return 0; int x=(l+r)>>1; D=d,nth_element(kd+l,kd+x,kd+r+1); ch[x][0]=build(l,x-1,d^1); ch[x][1]=build(x+1,r,d^1); rep(i,0,2)p[ch[x][i]]=x; return update(x),x; } int ans,qy[2][2]; inline bool out(int x){ if(!x)return 1; rep(i,0,2){ if(mx[x][i][1]<qy[i][0])return 1; if(mx[x][i][0]>qy[i][1])return 1; } return 0; } inline bool in(int x){ rep(i,0,2){ if(mx[x][i][1]>qy[i][1])return 0; if(mx[x][i][0]<qy[i][0])return 0; } return 1; } void query(int x){ if(out(x))return; if(in(x)){ ans+=sum[x]; return; } if(!ban[x]){ bool flag=1; rep(i,0,2){ if(kd[x].d[i]<qy[i][0])flag=0; if(kd[x].d[i]>qy[i][1])flag=0; } if(flag)++ans; } query(ch[x][0]),query(ch[x][1]); } int n,k,rt,pos[MAXN]; struct data{ int x,y,z; inline void scan(){ Scan(x),Scan(y),Scan(z); } inline bool operator<(const data&o)const{ if(x!=o.x)return x<o.x; return y!=o.y?y<o.y:z<o.z; } inline bool operator==(const data&o)const{ return x==o.x&&y==o.y&&z==o.z; } }d[MAXN]; inline void Init(){ Scan(n),Scan(k); rep(i,1,n+1)d[i].scan(); } inline void modify(int x){ x=pos[x],ban[x]=0; for(int i=x;i;i=p[i])update(i); } int cnt[MAXN]; inline void Solve(){ sort(d+1,d+1+n); rep(i,1,n+1){ kd[i].d[0]=d[i].y; kd[i].d[1]=d[i].z; kd[i].id=i; ban[i]=1; } rt=build(1,n,0); rep(i,1,n+1)pos[kd[i].id]=i; rep(i,1,n+1){ ans=0; qy[0][1]=d[i].y; qy[1][1]=d[i].z; query(rt); rep(j,i+1,n+1) if(d[i]==d[j])++ans; else break; ++cnt[ans+1]; modify(i); } rep(i,1,n+1)printf("%d\n",cnt[i]); } int main(){ Init(); Solve(); return 0; }
bzoj3456 城市规划
求n个点的简单无向连通图(无标号)的个数,对1004535809取模
令fn表示n个点的方案数,则有递推公式: fn=2C(n,2)-∑i(i>1&&i<n) C(n-1,i-1)*fi*2C(n-i,2) (用总方案数减去不连通的方案数)
两边都乘上(n-1)!-1然后再移项整理得:2C(n,2)*(n-1)-1=∑i(i>1&&i<=n)fi*(i-1)!*2C(n-i,2)*(n-i)!
令Ai=fi*(i-1)!,Bi=2C(i,2)*i!,Ci=2C(n,2)*(n-1)!-1,则有A×B=C,A=C*B-1
这样就只用算出B在mod xn+1意义下的逆元,就可以计算A了。
#include <stdio.h> #include <string.h> #include <algorithm> #define G 3 #define DFT(a,n) fft(a,n,0) #define IDFT(a,n) fft(a,n,1) #define INV(x,P) qpow(x,P-2,P) #define rep(i,a,b) for(int i=a,s=b;i<s;++i) using namespace std; const int MAXN=(1<<18)+5; typedef long long ll; const int P=1004535809; inline ll qpow(ll x,int k,int M){ ll ans=1; for(;k;x=x*x%M,k>>=1) if(k&1)ans=ans*x%M; return ans; } int r[MAXN],w[2][MAXN],rn; inline void init_fft(int n,int b){ rn=INV(n,P); int g=qpow(G,(P-1)/n,P); w[0][0]=w[0][n]=1; rep(i,1,n)w[0][i]=1ll*w[0][i-1]*g%P; rep(i,0,n+1)w[1][i]=w[0][n-i]; rep(i,1,n+1){ r[i]=(r[i>>1]>>1)|((i&1)<<(b-1)); } } inline void fft(int*a,int n,int t){ rep(i,1,n)if(i<r[i])swap(a[i],a[r[i]]); for(int i=2;i<=n;i<<=1) for(int j=0;j<n;j+=i) for(int k=0;k<i>>1;++k){ int v=1ll*a[(i>>1)+j+k]*w[t][n/i*k]%P; a[(i>>1)+j+k]=(a[j+k]+P-v)%P; a[j+k]=(a[j+k]+v)%P; } if(t)rep(i,0,n)a[i]=1ll*a[i]*rn%P; } inline void inv(int*a,int*b,int n,int bit){ b[0]=INV(a[0],P),b[1]=0; int l=1; static int c[MAXN]; rep(i,1,bit+1){ l<<=1; rep(j,0,l)c[j]=a[j]; rep(j,l,l<<1)b[j]=c[j]=0; init_fft(l<<1,i+1); DFT(b,l<<1),DFT(c,l<<1); rep(j,0,l<<1) b[j]=1ll*b[j]*(2+P-1ll*b[j]*c[j]%P)%P; IDFT(b,l<<1); rep(j,l,l<<1)b[j]=0; } } int n,l,b; int fac[MAXN],inv_fac[MAXN]; inline void Init(){ scanf("%d",&n); l=n+1,b=1; while(1<<b<l)++b; l=1<<b; fac[0]=1; rep(i,1,l)fac[i]=1ll*fac[i-1]*i%P; inv_fac[0]=inv_fac[1]=1; rep(i,2,l){ int a=P/i,b=P%i; inv_fac[i]=1ll*a*(P-inv_fac[b])%P; } rep(i,2,l) inv_fac[i]=1ll*inv_fac[i]*inv_fac[i-1]%P; } inline ll C(ll n){return n*(n-1)>>1;} int a[MAXN],c[MAXN]; inline void Solve(){ rep(i,0,n+1) c[i]=qpow(2,C(i)%(P-1),P)*inv_fac[i]%P; inv(c,a,l,b); c[0]=0; rep(i,1,n+1) c[i]=qpow(2,C(i)%(P-1),P)*inv_fac[i-1]%P; rep(i,l,l<<1)a[i]=c[i]=0; init_fft(l<<1,b+1); DFT(a,l<<1),DFT(c,l<<1); rep(i,0,l<<1)a[i]=1ll*a[i]*c[i]%P; IDFT(a,l<<1); int ans=1ll*a[n]*fac[n-1]%P; printf("%d\n",ans); } int main(){ Init(); Solve(); return 0; }