• 欢迎光临~

T4 凹函数 整理

开发技术 开发技术 2022-10-02 次浏览

MD

凹函数

题解

题意是多组数据,给定(n,m),求定义域和值域分别为([0,n],[0,m])的单调凹函数至多经过几个整点
考虑相邻两个经过整点的差,原问题等价于选出k个二维向量 ((x_i,y_i)) ,满足 (sumlimits_k(x_i,y_i)=(n,m)) ,且 (frac{y_i}{x_i}) 两两不同, (x_i,y_iin N^*) ,最大化(k+1)的值

方便起见,同时不改变答案,可以再等价变换为选出(k)个二维向量 ((x_i,y_i)) ,满足 (sum x_ileq n,sum y_i leq m)(gcd(x_i,y_i)=1)(x_i,y_iin N^*) ,最大化k+1$的值

为了回答多组询问,可以取(N=3000),对 (1leq a,bleq N) 算出(f(a,b))表示(n=a,m=b)时的答案

朴素做法是枚举(N)以内满足互质条件的二维向量,更新答案,时间复杂度为 (O(N^4))

可以观察到(f(N,N))(O(N^{2/3})) 数量级,于是可以把状态表示改为(g(a,c))(x)之和为(a),选出(c)个向量,(y)之和的最小值,每选一个向量更新的时间复杂度从 (O(N^2)) 变为 (O(N^frac 53)) ,时间复杂度降至 (O(N^frac {11} 3))

在选择向量时可以加入一个贪心策略而不失最优性:选一个向量,必须先选所有(x,y)同时小于等于它的其它向量。这些向量的和必须不超过((N,N))。加入这一剪枝后,可选的向量变得非常少,在 (O(N^frac 23)) 数量级,每个向量更新的时间复杂度仍为 (O(N^frac 53)) ,因此总的时间复杂度降到 (O(N^frac 73))

这里用到两个观察得出的结论,以下给出证明:

  1. 答案在 (O(N^{2/3})) 数量级,这个可以由剪枝后向量的个数推出
  2. 剪枝后的向量个数在 (O(N^frac 23)) 数量级

为方便证明,使用一个更弱的剪枝:选一个向量,必须先选所有(x,y)同时小于等于它的其它向量,这些向量的(x+y)之和不超过(2N)

(sumlimits_Nsumlimits_N[gcd(X,Y)=1]cdot left [ maxleft ( sumlimits_X sumlimits_Y[gcd(x,y)=1]cdot x , sumlimits_X sumlimits_Y[gcd(x,y)=1]cdot y right ) leq N right ])

$leq sumlimits_{1leq X,Yleq N} left [ maxleft ( sumlimits_{+infty}mu(d)d sumlimits_{X/d} sumlimits_{Y/d}x , sumlimits_{+infty}mu(d)d sumlimits_{X/d} sumlimits_{Y/d}y right ) leq N right ] $

(sumlimits_{1leq X,Yleq N}[XYmax(X,Y)leq Theta(N)]=O(n^frac 23))

标准代码

C++ 11

#include<stdio.h>
#include<bits/stdc++.h>
const int inf=0x3f3f3f3f;
void maxs(int& a,int b){ if(a<b)a=b; }
void mins(int& a,int b){ if(a>b)a=b; }
int gcd(int x,int y){ return y?gcd(y,x%y):x; }
int n;
namespace sol{//n^4
	int vf[307][307];
	void cal(){
		for(int x=1;x<=n;++x){
			for(int y=1;y<=n;++y)if(gcd(x,y)==1){
				for(int i=n;i>=x;--i)
					for(int j=n;j>=y;--j)maxs(vf[i][j],vf[i-x][j-y]+1);
			}
		}
	}
	int get(int x,int y){
		return vf[x][y];
	}
}
namespace sol{//n^(8/3)logn
	int s[4007];
	int f[4007][4007];
	void ins(int x,int y){
		for(int i=n;i>=x;--i){
			for(int j=n;j>=y;--j){
				maxs(f[i][j],f[i-x][j-y]+1);
			}
		}
	}
	void cal(){
		for(int i=1;i<=n;++i){
			int s1=0;
			for(int j=1;j<=n&&s[j]<=n*2;++j){
				if(gcd(i,j)==1){
					s1+=i+j;
					if(s[j]+s1<=n*2)ins(i,j);
				}
				s[j]+=s1;
			}
		}
	}
	int get(int x,int y){
		return f[x][y];
	}
}
namespace sol{//n^(7/3)logn
	int s[4007][2];
	int fs[4007][407],sz[4007],o=0,err=0;
	void ins(int x,int y){
		for(int i=n;i>=x;--i){
			bool st=0;
			for(int j=0;j<=sz[i-x];++j){
				int a=fs[i-x][j]+y;
				if(a>n)break;
				mins(fs[i][j+1],a);
			}
			if(fs[i][sz[i]+1]<inf)fs[i][++sz[i]+1]=inf;
		}
	}
	int get(int x,int y){
		return std::upper_bound(fs[x],fs[x]+sz[x]+1,y)-fs[x]-1;
	}
	void cal(){
		for(int i=0;i<=n;++i)fs[i][1]=inf;
		for(int i=1;i<=n;++i){
			int s0=0,s1=0;
			for(int j=1;j<=n&&std::max(s[j][0],s[j][1])<=n;++j){
				if(gcd(i,j)==1){
					s0+=i;
					s1+=j;
					if(std::max(s[j][0]+s0,s[j][1]+s1)<=n)ins(i,j);
				}
				s[j][0]+=s0;
				s[j][1]+=s1;
			}
		}
	}
}
int q,qs[10007][2];
int main(){
	n=1;
	assert(scanf("%d",&q)==1);
	assert(1<=q&&q<=10000);
	for(int i=0;i<q;++i){
		assert(scanf("%d%d",qs[i],qs[i]+1)==2);
		assert(qs[i][0]>=1&&qs[i][0]<=3000);
		assert(qs[i][1]>=1&&qs[i][1]<=3000);
		n=std::max(n,std::max(qs[i][0],qs[i][1]));
	}
	using namespace sol3;
	cal();
	for(int i=0;i<q;++i)printf("%dn",get(qs[i][0],qs[i][1])+1);
	return 0;
}


程序员灯塔
转载请注明原文链接:T4 凹函数 整理
喜欢 (0)