题目链接
题目解法
参考 DeaphetS 的题解
很有意思的题，感觉 \(F1\) 不到 \(*2900\)，\(F2\) 超过 \(*2900\)
F1
简化题目中的操作：把 \(n\) 个数放到 \(n-k\) 组中，求 \(\max(\sum\) 每组 \(a_i\) 的 \(\gcd )\)
首先考虑所有数互不相同的情况
结论1：把 \(k+1\) 个数放在一组中是最优的
证明1：
在所有组中任取两组，包含的集合分别为 \(S,T(|S|>1,|T|>1)\)，且 \(\gcd(S)\ge \gcd(T)\)
当前的价值为：\(\gcd(S)+\gcd(T)-sum(S)-sum(T)\)
合并集合 \(S,T\)，具体来说，找到 \(S\) 集合中最大的元素 \(x\)，因为所有数互不相同，所以 \(x\ge 2\gcd(S)\)，然后合并去掉 \(x\) 的集合 \(S\) 和集合 \(T\)，价值为：\(\gcd(S\cap T)-sum(S)-sum(T)+x\)
做差得到增加的价值为：\(gcd(S\cap T)+x-\gcd(S)-\gcd(T)\ge \gcd(S\cap T)+2\gcd(S)-\gcd(S)-\gcd(T)> 0\)
所以合并是更优的
在考虑有相同数的情况
考虑到 $\gcd $ 具有交换律，所以先执行合并相同数的操作，再执行其他操作是不会影响答案的
所以我们只要求得交换 \(i\) 个相同数的最小代价，然后当做所有数互不相同做一遍即可
所有数互不相同的情况是好做的，只要枚举 \(\gcd\)，然后贪心的选小的数即可
时间复杂度 \(O(\sum m\log m)\)
点击查看代码
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=1000100;
int a[N],cnt[N],b[N];
LL cost[N];
void clear(int m){ F(i,1,m) cnt[i]=0;}
void work(){
int n=read(),m=read(),k=read();
LL tot=0;
F(i,1,n) a[i]=read(),tot+=a[i],cnt[a[i]]++;
int cur=0;
F(i,1,m) if(cnt[i]){ F(j,cur+1,cur+cnt[i]-1) cost[j]=cost[j-1]+i;cur+=cnt[i]-1;}
LL ans=0;
F(i,1,m){
int len=0;
F(j,1,m/i) if(cnt[i*j]) b[++len]=i*j;
LL curres=tot+i;
F(j,1,len){
if(j-1>k) break;
curres-=b[j];
if(k-(j-1)<=cur) chkmax(ans,curres-cost[k-(j-1)]);
}
}
printf("%lld\n",ans);clear(m);
}
int main(){
int T=read();
while(T--) work();
return 0;
}
F2
我们沿用上面的大致做法，考虑再发现一些性质来优化
我们发现选最小的若干个数在很多情况下是优的，但有些情况就不优，所以考虑进行调整
结论2：若需要合并 \(num\) 个数字，那么前 \(num-1\) 小的数字一定会合并
证明2：
考虑一种调整方式：若当前选的数字为 \(a_{id_1},\;a_{id_2},\;...,\;a_{id_k}(k>1)\)，\(id\) 递增
我们删去最大的数字 \(a_{id_k}\)，然后加入任意一个不在 \(a_{id_i}\) 中的元素 \(a_{q}(q<id_{k-1})\)
那么价值差即为 \(a_{id_k}-a_q-\gcd\{a_{id_1},\;,...,\;a_{id_k}\}+\gcd\{a_{id_1},\;...,\;a_{id_{k-1}},a_q\}\)
一个显然的关系是：\(a_{id_{k}}-a_{id_{k-1}}>\gcd\{a_{id_1},\;,...,\;a_{id_k}\}\)，可得价值差 \(>a_{id_k}-a_{id_{k-1}}-\gcd\{a_{id_1},\;...,\;a_{id_{k}}\}+\gcd\{a_{id_1},\;...,\;a_{id_{k-1}},a_q\}>0\)
所以价值差为正，调整更优
根据上面的调整方式，如果前 \(num-1\) 个数字不是都选，那么一定可以调整变得更优
如果暴力枚举 \(nums-1\)，然后找后面的位置是 \(O(n^2)\) 的
但 \(\gcd\) 有一个性质是：不同的前缀 \(\gcd\) 只有 \(\log\) 个，所以对于每一段 \(\gcd\) 相同的暴力做即可
时间复杂度 \(O(\sum n\log m)\)，注意开 \(int128\)
点击查看代码
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef __int128_t i128;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=1000100;
const i128 inf=1e30;
int n,K;
i128 m,a[N],b[N],cost[N],g[N],s[N];
void print(i128 x){
if(!x) return;
print(x/10),putchar(x%10+48);
}
void work(){
read(n),read(m),read(K);
i128 tot=0;
F(i,1,n) read(a[i]),tot+=a[i];
sort(a+1,a+n+1);
int cur=0,len=0;
F(i,1,n){
int j=i;
while(j+1<=n&&a[j+1]==a[i]) j++;
F(k,cur+1,cur+j-i) cost[k]=cost[k-1]+a[i];
cur+=j-i,b[++len]=a[i],i=j;
}
n=len;F(i,1,n) a[i]=b[i];
g[0]=0;
F(i,1,n) g[i]=__gcd(g[i-1],a[i]),s[i]=s[i-1]+a[i];
i128 ans=0;
F(i,0,n-1){
int j=i;
while(j+1<n&&g[j+1]==g[i]) j++;
i128 mx=-inf;
F(k,j+1,n) chkmax(mx,-a[k]+__gcd(g[i],a[k]));
F(k,i,j){
i128 mx2=max(-s[k+1]+g[k+1],-s[k]+mx);
if(K-k>=0&&cur>=K-k) chkmax(ans,tot+mx2-cost[K-k]);
}
i=j;
}
print(ans);puts("");
}
int main(){
int T;read(T);
while(T--) work();
return 0;
}