gym102798 2020CCPC威海L Clock Master

题目：

$T$组数据。
每组数据给定一个数$b$，找出一组数$t$，满足$\sum _{i=1}^{|t|}{t}_i\le b$且$v_k=(k\%t_1,k\%t_2,\cdots k\%t_{|t|})$的种类数最多，其中$k$为非负整数。
$(1\le T,b\le 30000)$

题解：

考虑什么情况下对于不同的$k$，$v_k$相同。设$k_1,k_2,k_1\ne k_2$，
$k_1=a_1{t}_1+b_1,k_1=a_2{t}_2+b_2,\cdots k_1=a_{|t|}{t}_{|t|}+b_{|t|}$，
$k_2=c_1{t}_1+b_1,k_2=c_2{t}_2+b_2,\cdots k_2=c_{|t|}{t}_{|t|}+b_{|t|}$。
那么显然$lcm(t_1,t_2,\cdots ,t_{|t|})\mid |k2-k1|$，所以不同的$v_k$有$lcm(t_1,t_2,\cdots ,t_{|t|})$个。显然我们取的$t$要两两互质，不然我们可以在达到原来的$lcm$的同时使总和更小。那么考虑一个数$n=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$，有$p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}\ge p_1^{a_1}+p_2^{a_2}+\cdots +p_k^{a_k}$，当且仅当$n=4=2\times 2$时，等号成立，所以我们要找的$t$一定是质数的幂次。打出质数的幂次可以发现就3000个左右，所以问题就变成了分组背包问题了，物品$a$的体积为$a$，价值为$\ln a$，直接$dp$即可。
注意由于$T$很大，所以不要每次都求背包，要直接求30000的背包预处理出所有的答案。感觉有些卡常。

复杂度：$O(\frac{b^2}{logb})$

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<sstream>
#include<ctime>
//#include<chrono>
//#include<random>
//#include<unordered_map>
using namespace std;
#define ll long long
#define ls o<<1
#define rs o<<1|1
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
const double pi=acos(-1.0);
const double eps=1e-6;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn=30005;
ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int T,b,tp;
int prim[maxn],vis[maxn];
double dp[maxn],ans[maxn],v[5005][20];
int a[5005][20];
void init(int n){
tp=0;
for(int i=2;i<=n;i++){
if(!vis[i]){
prim[++tp]=i;
}
for(int j=1;i*prim[j]<=n;j++){
vis[i*prim[j]]=1;
if(i%prim[j]==0)break;
}
}
for(int i=1;i<=tp;i++){
for(int j=prim[i],k=1;j<=n;j*=prim[i],k++){
a[i][k]=j;
a[i][0]=k;
v[i][k]=log(j);
}
}
for(int i=0;i<=n;i++)dp[i]=-1e18;
dp[0]=0;
for(int i=1;i<=tp;i++){
for(int j=n;j>=prim[i];j--){
for(int k=1;k<=a[i][0];k++){
if(a[i][k]>j)continue;
if(dp[j-a[i][k]]>=0)dp[j]=max(dp[j],dp[j-a[i][k]]+v[i][k]);
}
}
}
ans[0]=dp[0];
for(int i=1;i<=n;i++)ans[i]=max(ans[i-1],dp[i]);
}
int main(void){
// freopen("in.txt","r",stdin);
init(30000);
scanf("%d",&T);
while(T--){
scanf("%d",&b);
printf("%.9fn",ans[b]);
}
return 0;
}

最后

以上就是火星上水壶为你收集整理的gym102798 2020CCPC威海L Clock Master的全部内容，希望文章能够帮你解决gym102798 2020CCPC威海L Clock Master所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。