ShinriiTin's Blog - 博主是sb

bzoj2876 [NOI2012]骑行川藏

求条件极值 min f(x)=∑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,我们总不能倒着走对吧。。。

所以,这个函数在满足题意的定义域内单调,就可以二分求解了

Portal

#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跑得飞快

Portal

#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只能贴线低飞。。。

Portal

#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了。

Portal

#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;
}