2020CCPC(威海) - Clock Master(數論+分組背包)-有解無憂

題目大意：給出一個數字 n ，要求分解成：a[ 0 ] + a[ 1 ] + ... + a[ m ] = n，( m 沒有約束 )，使得 lcm( a[ 0 ] , a[ 1 ] , ... a[ m ] ) 最大，輸出這個最大值的對數

題目分析：看到 lcm 就可以去思考如何快速求出 n 個數的 lcm，比較簡單的一種方法就是將每個數進行質因子分解，對于每個質因子 p 來說，取 n 個數中 p^k[ i ] 的最大值，就是質因子 p 的貢獻了，所有質因子的貢獻的乘積就是需要求的 lcm

所以這個題目的模型就比較簡單了，嘗試將 n 分解為 $p_{1}^{e1}+p_{2}^{e2}+p_{3}^{e3}+...+p_{k}^{ek}=n$ 使得 $p_{1}^{e1}*p_{2}^{e2}*p_{3}^{e3}*...*p_{k}^{ek}$ 盡可能大，到此為止，再看一下題面需要求的對數，不難發現對數只是為了保證精度的，因為對數函式是單調遞增的，所以套上對數的公式將目標轉換為：使得 $log(p_{1}^{e1})+log(p_{2}^{e2})+log(p_{3}^{e3})+...+log(p_{k}^{ek})$ 盡可能大

換句話說，花費 $p^i$ 的容量可以獲得 $log(p^i)$ 的價值，且目標容量為 n，且每個質因子 p 只能選擇一種冪次，這就是分組背包的模板題目了，設質數的冪次集合為 $P = \left\{ p^i : p \in Prime, i \in Z^+ \right\}$ ，那么 $|P\cap[1,n]|=O(\frac{n}{log(n)})$ ，可以先預處理一下，時間復雜度為 O( n * n / logn )，然后就可以 O( 1 ) 查詢了

代碼：

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
     
typedef long long LL;
     
typedef unsigned long long ull;
     
const int inf=0x3f3f3f3f;

const int N=3e4+100;

double ans[N],Log[N];

int cnt,pri[N];

bool vis[N];

double dp[N];

void P()
{
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
			pri[cnt++]=i;
		for(int j=0;j<cnt&&pri[j]*i<N;j++)
		{
			vis[pri[j]*i]=true;
			if(i%pri[j]==0)
				break;
		}
	}
}

void init()
{
	for(int i=1;i<N;i++)
		Log[i]=log(i);
	for(int i=0;i<N;i++)
		dp[i]=0;
	dp[0]=0;
	for(int i=0;i<cnt;i++)//列舉質數 
		for(int j=N-1;j>=pri[i];j--)//容量 
			for(int k=pri[i];k<N;k*=pri[i])//當前的冪次 
				if(j>=k)
					dp[j]=max(dp[j],dp[j-k]+Log[k]);
}

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	P();
	init();
	int w;
	cin>>w;
	while(w--)
	{
		int n;
		scanf("%d",&n);
		printf("%.10f\n",dp[n]);
	}














    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/193754.html

標籤：java

上一篇：撲克牌小游戲，尋找 ♠A（來一場和賭王的爭霸）

下一篇：合并果子（經典優先佇列）