COCI20162017 Contest#6 F

COCI20162017 Contest#6 F

其实这个题不是很难的。。。

设值域为(M)

考虑如果没有幸运数的限制，那么从(A)变成(B)，实际上只与(frac{A}{B})有关

不妨令(dp_{i,j})为从(i)走了(j)步变成1，显然这个(j)的最大值为(log M=19)，即(2^{19})最多操作19次

从(i)枚举倍数进行转移，同时也暴力处理每个数的因数个数，复杂度为(O(Mln Mlog M))

[ ]

接下来考虑幸运数的限制

推论: 最多只会在一个幸运数上停留

如果经过多个，显然在代价最小的那个上面停留

因此考虑枚举停留的幸运数(x)

那么转移可以分为两步(frac{A}{x})和(frac{x}{B})，可以暴力合并两个(dp)数组，单次查询复杂度为(O(Tcdot log^2 M))

合并得到的结果，可以描述为:

可以在(x)上用(C(x))的代价停留，并且其他部分的转移花了(j)的时间，(y)的代价

如果考虑停留的时间，那么得到的答案显然是一条直线，斜率就是停留的代价

关于一群直线，一群查询，不难想到可以斜率优化求解，这一部分复杂度为(O(Tlog Mlog (Tlog M)+m))（排序复杂度）

总复杂度可以认为就是(O(Mlog^2 M+Q(Tlog ^2 M+m)))

斜率优化的实现可以参考代码

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
#define reg register
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e6+10,INF=1e9;

int n,m;
int F[N],A[N],B[N];
int L[N];
// A: 因子个数
// B: 将B变成1需要的最大步数
int C[N],D[N];
int dp[N][20];
// 用了j步，将i变为1的最小代价

struct Node{ 
    // 描述一条直线
	ll x,y;
	// 答案为 x*i+y
	ll operator [](const ll i)const {
		return i*x+y;
	} //求直线点值
	bool operator < (const Node __) const {
		if(x!=__.x) return x<__.x;
		return y<__.y; //按照斜率排序
	}
} U[N];

int Uc,T[21],R[21];

int main(){
	rep(i,1,N-1) {
		A[i]++;
		for(reg int j=i+i;j<N;j+=i) A[j]++,cmax(B[j],B[i]+1);
	}
	rep(i,1,rd()) F[i]=rd();
	rep(i,1,m=rd()) L[i]=rd();
	sort(L+1,L+m+1);
	rep(i,1,N-1) rep(j,0,B[i]) dp[i][j]=INF;
	dp[1][0]=0;
	rep(i,1,N-1) rep(j,0,B[i]) if(dp[i][j]<INF) for(reg int k=i+i;k<N;k+=i) cmin(dp[k][j+1],dp[i][j]+F[A[k/i]]);
	rep(i,1,n=rd()) C[i]=rd(),D[i]=rd();

	rep(kase,1,rd()) {
		int x=rd(),y=rd(),d=x/y;
		if(x%y!=0){
			printf("%d
",-m);
			continue;
		}
		memset(R,63,sizeof R);
		Uc=0;
		rep(i,1,n) if(x%C[i]==0 && C[i]%y==0){
			int dx=x/C[i],dy=C[i]/y;
			memset(T,63,sizeof T);
			rep(a,0,B[dx]) if(dp[dx][a]<INF) rep(b,0,B[dy]) cmin(T[a+b],dp[dx][a]+dp[dy][b]);
			rep(j,0,B[dx]+B[dy]) if(T[j]<INF) {
				ll a=D[i],b=T[j]-a*j;
				U[++Uc]=(Node){a,b};
				rep(k,j,B[d]) cmin(R[k],(int)U[Uc][k]);
			}
		}
		rep(i,0,B[d]) cmin(R[i],dp[d][i]);
		ll ans=0;
		ll mi=1e18;
		sort(U+1,U+Uc+1);
		int R=0;
		rep(i,1,Uc) {
			if(mi<U[i].y) continue;
			mi=U[i].y;
			while(R>1 && (U[i].y-U[R].y)*(U[R].x-U[R-1].x)<=(U[R].y-U[R-1].y)*(U[i].x-U[R].x)) R--;
			U[++R]=U[i]; // 单调栈处理凸包，注意加入时满足x递增，y递减
		}
		rep(i,1,m) if(L[i]<=B[d]) ans+=::R[L[i]]<INF?::R[L[i]]:-1;
		else {
			while(R>1 && U[R-1][L[i]]<=U[R][L[i]]) R--;
			if(!R) ans--;
			else ans+=U[R][L[i]];
		}
		printf("%lld
",ans);
	}
}