题解 P4963 【美樱的颜料】

ouuan

2018-11-03 23:09:41

Solution

### 一、朴素做法 先考虑确定了选择的第一个数 $i$。那么必须先选择 $1$ ~ $n$ 中所有 $i$ 的倍数,再选择 $i$ 除自身外最大约数的倍数……依次类推,直到选完 $m$ 个数。 所以需要预处理的是 $1$ ~ $n$ 的除自身外最大约数,可以在线性筛素数的过程中求出。 令 $f_i$ 表示 $i$ 除自身外最大的约数,那么如果一个数是 $f_i$ 的倍数,它在计算 $i$ 的倍数的贡献时和计算 $f_i$ 的倍数的贡献时都会被计算,所以要去重。 (假设 $\lfloor \frac n {f_i}\rfloor< m$,$\lfloor \frac n {f_{f_i}}\rfloor\ge m$) 总贡献$=\lfloor \frac n i\rfloor\times i+\left(\lfloor \frac n {f_i}\rfloor-\lfloor \frac n i\rfloor\right)\times f_i+\left(m-\lfloor \frac n {f_i}\rfloor\right)\times f_{f_i}$ $\quad\quad\ \,=\lfloor \frac n i\rfloor\times (i-f_i)+\lfloor \frac n {f_i}\rfloor\times (f_i-f_{f_i})+m\times f_{f_i}$ 若 $\lfloor \frac n {f_{...f_i}}\rfloor< m$,$\lfloor \frac n {f_{f_{...f_i}}}\rfloor\ge m$(层数与上面的示例不同),计算方式是类似的。 ~~然后只要暴力枚举选的第一个数即可~~ 直接这样做空间会炸.但是在讲正解前还是看一下这个做法的参考代码吧: ``` #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N=10000010; int n,m,p[N],f[N],tot,ans; bool np[N]; int main() { int i,j,temp; cin>>n>>m; for (i=2;i<=n;++i) { if (!np[i]) { p[++tot]=i; f[i]=1; } for (j=1;j<=tot&&i*p[j]<=n;++j) { np[i*p[j]]=true; f[i*p[j]]=i; if (i%p[j]==0) { break; } } } for (i=1;i<=n;++i) { temp=0; for (j=i;;j=f[j]) { if (n/j<m) { temp+=n/j*(j-f[j]); } else { temp+=m*j; break; } } ans=max(ans,temp); } cout<<ans; return 0; } ``` 这个做法的时间复杂度是 $O(nloglogn)$ 的(后面的枚举部分复杂度实际上和埃氏筛一样,都是质因数个数和),空间大约需要50MB。 ### 二、优秀做法 可以发现,$f$ 数组占用了大量的内存($4\times 10^7\mathrm{B}\approx38\mathrm{MB}$),有没有办法不把 $f$ 存下来做这道题呢? 注意计算 $f$ 的这个循环(也就是线性筛的循环): ``` for (i=2;i<=n;++i) { if (!np[i]) { p[++tot]=i; f[i]=1; } for (j=1;j<=tot&&i*p[j]<=n;++j) { np[i*p[j]]=true; f[i*p[j]]=i; if (i%p[j]==0) { break; } } } ``` 事实上我们虽然不能快速地求出任意一个 $f_i$ ,但我们可以快速地求出满足 $f_x=i$ 的所有 $x$。 先考虑 $n=m$ 的情况,把所有数抽象成一棵树,以 $f_u$ 为 $u$ 的父亲, $f_u$ 和 $u$ 之间的边权为 $\lfloor\frac n u\rfloor\times(u-f_u)$,那么以某个数为第一个数的答案就是这个数到树根的距离。可以用dfs解决,用类似线性筛的方式找儿子。 若 $n\ne m$,考虑当前节点 $u$ 以 $ans_u$ 表示以 $u$ 为第一个数的答案,若 $\lfloor\frac n u\rfloor\ge m$,则 $ans_u=\lfloor\frac n u\rfloor\times m$,否则,令 $u$ 的父亲为 $f_u$,$ans_u=ans_{f_u}+\lfloor\frac n u\rfloor\times(u-f_u)$。仔细看看朴素算法的做法就能明白为什么是这样了。 总的时间复杂度是 $O(n)$ 的,空间消耗只有不到 $\rm 14MB$。 参考代码: ``` #include <iostream> #include <cstdio> using namespace std; const int N=10000010; void dfs(int u,int fa,int sum); int n,m,p[N/10],tot,ans; bool np[N]; int main() { int i,j; cin>>n>>m; for (i=2;i<=n;++i) { if (!np[i]) { p[++tot]=i; } for (j=1;j<=tot&&i*p[j]<=n;++j) { np[i*p[j]]=true; if (i%p[j]==0) { break; } } } dfs(1,0,0); cout<<ans; return 0; } void dfs(int u,int fa,int sum) { sum+=min(m,n/u)*(u-fa); ans=max(ans,sum); for (int i=1;i<=tot&&u*p[i]<=n;++i) { int v=u*p[i]; if (n/v>=m) { dfs(v,0,0); } else { dfs(v,u,sum); } if (u%p[i]==0) { break; } } } ``` ### 三、优秀的dp做法和优化的朴素做法 这两种方法的核心思想是:最优的起点一定大于等于 $\lfloor\frac n 2\rfloor+1$,因为对于 $u\le\lfloor\frac n 2\rfloor$,$f_{2u}=u$,以 $2u$ 为起点一定更优。 所以,可以得到下面的两种做法,压缩空间的核心都是只存一半,另一半直接更新答案而不保存,就不详细讲解了: ### 跑的飞快的dp做法: ``` #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N=10000010; int n,m,p[N/10],f[N/2],tot,ans; int main() { int i,j,v; cin>>n>>m; ans=max(m,n+m-1); f[1]=m; for (i=2;i<=n/2;++i) { if (!f[i]) { p[++tot]=i; if (n/i>=m) { f[i]=m*i; } else { f[i]=f[1]+n/i*(i-1); } } for (j=1;j<=tot&&i*p[j]<=n;++j) { v=i*p[j]; if (v<=n/2) { if (n/v>=m) { f[v]=m*v; } else { f[v]=f[i]+n/v*(v-i); } } else { if (n/v>=m) { ans=max(ans,m*v); } else { ans=max(ans,f[i]+n/v*(v-i)); } } if (i%p[j]==0) { break; } } } cout<<ans; return 0; } ``` 这个dp做法也是 $O(n)$ 的,而且常数比dfs小。但是空间消耗略大一些。 ### loglog的做法: ``` #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N=10000010; int n,m,p[N/10],f[N/2],tot,ans; int main() { int i,j,k,temp; cin>>n>>m; ans=max(m,n+m-1); for (i=2;i<=n/2;++i) { if (!f[i]) { p[++tot]=i; f[i]=1; } for (j=1;j<=tot&&i*p[j]<=n;++j) { if (i*p[j]<=n/2) { f[i*p[j]]=i; } else { temp=0; for (k=i*p[j];;k=(k<=n/2?f[k]:i)) { if (n/k<m) { temp+=n/k*(k-(k<=n/2?f[k]:i)); } else { temp+=m*k; break; } } ans=max(ans,temp); } if (i%p[j]==0) { break; } } } cout<<ans; return 0; } ``` P.S. 为什么要加上 > 设现在已经使用了的颜料编号构成的集合为 $A$,若$\ \exists\ i,\ j\notin A,\ i,\ j\in [1,\ n],\ gcd(A,\ i)>gcd(A,\ j)$,那么就不能选择颜料 $j$。 这个限制呢?因为这并不是最优策略,如:`14 7` 按照这个限制,答案是 $27$ :`12 6 3 9 1 2 4` 实际上,若没有这个限制,答案是 $28$ :`12 4 8 2 6 10 14` P.P.S. 造数据的时候没想好..$m$ 都是在 $1$ ~ $n$ 纯随机的,导致最优方案的第一个数大多都是 $2$ 的次幂,以至于@小粉兔 用并不优秀的做法进行数据分治,对于无法通过的点只计算 $2$ 的次幂通过了此题...事实上这题骗分不太好卡...更新了数据也不会太强吧.大家理解上面两种 $O(n)$ 做法就好。 P.P.P.S. 所以说到底为什么要加上上述限制呢?因为没有这个限制的时候出题人不会复杂度正确的做法..然后有一位julao@zhoutb2333 赛时看掉了这个限制想出了一个非常优秀的做法: ``` #include<bits/stdc++.h> #define ll long long #define pii pair<int,int> using namespace std; int n,m; map<pii,ll> f; ll F(int x,int y){ if(x==1) return y; if(f[{x,y}]) return f[{x,y}]; ll ret=0; for(int i=2,pos;i<=x;i=pos+1) pos=x/(x/i),ret=max(ret,F(x/i,min(y,x/i))*pos+y-min(y,x/i)); return f[{x,y}]=ret; } int main(){ cin>>n>>m; cout<<F(n,m)<<endl; return 0; } ```