专栏文章

bb

uuntergehen
P13527题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min624g3
此快照首次捕获于
2025/12/01 21:09
3 个月前
此快照最后确认于
2025/12/01 21:09
3 个月前
查看原文
本题解复杂度是 O⁡(nk23log⁡k)\operatorname{O}(nk^{\frac23}\log k) 略优于其他题解。
首先显然最后 ∏bi≤2k\prod{b_i}\le 2k，否则可以取出最大的那个 bib_i，将他减一显然仍 ≥k\geq k。下文中将默认乘积 O(k)O(k)。
我们背包统计出前后缀 ∏bi≤k23\prod {b_i}\le k^{\frac23} 时最大的 ∏⌊aibi⌋\prod{\lfloor \frac{a_i}{b_i}\rfloor}。同时将切割方法分为两类。
  1. ∃i,bi≥k13\exist i, b_i\geq k^{\frac13}
此时枚举 ii，O⁡(k23log⁡k)\operatorname{O}(k^{\frac23}\log k) 合并前后段 dp，整除分块枚举 bib_i 即可。
  1. otherwise
我们断言，直接枚举相邻的前后缀 dp 合并是对的。复杂度O⁡(k23)\operatorname{O}(k^{\frac23})。
若存在 {bi}\{b_i\} 使得不被计算。则考虑 bib_i 前缀积第一个大于等于 k23k^{\frac23} 的位置。
因为要求，蓝色部分乘积小于等于 k23k^{\frac23} ,因为他同时不能被计算，所以红色部分应当大于等于 k23k^{\frac23} 这意味着中间的圆圈应当大于等于 k13k^{\frac13}。这意味着它应当属于第一类，被算过了。
综上该做法以 O⁡(nk23log⁡k)\operatorname{O}(nk^{\frac23}\log k) 时间 O⁡(nk23)\operatorname{O}(nk^{\frac23}) 空间解决了该题。
CPP
#include<bits/stdc++.h>
#define N 105
#define hV 50005
using namespace std;
namespace shan{
	const double inf=1e18;
	int n,k,a[N];
	double pre[N][hV],suf[N][hV];
	double ls[hV];
	signed main(){
		cin>>n>>k;
		const int V=pow(k,0.666666)+1;
		for(int i=0;i<=n+1;i++)
			for(int j=0;j<=V+1;j++)
				pre[i][j]=suf[i][j]=-inf;
		pre[0][1]=suf[n+1][1]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			for(int j=1;j<=min(V,a[i]);j++){
				double me=log(a[i]/j);
				for(int k=1;k*j<=5e4;k++)
					pre[i][j*k]=max(pre[i][j*k],pre[i-1][k]+me);
			}
		}
		for(int i=n;i>=1;i--){
			for(int j=1;j<=min(V,a[i]);j++){
				double me=log(a[i]/j);
				for(int k=1;k*j<=V;k++)
					suf[i][j*k]=max(suf[i][j*k],suf[i+1][k]+me);
			}
		}
		double ans=-inf;
		for(int j=k;j<=V;j++)ans=max(ans,suf[1][j]);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=V+1;j++)ls[j]=-inf;
			for(int j=1;j<=V;j++)
				for(int k=1;k*j<=V;k++)
					ls[j*k]=max(ls[j*k],pre[i-1][j]+suf[i+1][k]);
			for(int j=V;j>=1;j--)
				ls[j]=max(ls[j],ls[j+1]);
			for(int l=1,r=0;l<=a[i];l=r+1){
				int val=a[i]/l;
				r=a[i]/val;
				int need=(k+r-1)/r;
				if(need<=V)
					ans=max(ans,log(val)+ls[need]);
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=V;j>=1;j--)
				suf[i+1][j]=max(suf[i+1][j],suf[i+1][j+1]);
			for(int j=1;j<=V;j++){
				int need=(k+j-1)/j;
				if(need<=V)
					ans=max(ans,pre[i][j]+suf[i+1][need]);
			}
		}
		ans+=log(k);
		for(int i=1;i<=n;i++)ans-=log(a[i]);
		cout<<fixed<<setprecision(20)<<exp(ans);
		return 0;
	}
} 
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	shan::main();
	return 0;
}
有趣的知识：发现答案是乘积形式，可以取 ln⁡\ln 乘改加，最后 exp⁡\exp 回来。精度和速度都可能有所提升。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...