自动搬运

查看原文

来自洛谷，原作者为

	Po7ed **

搬运于2025-08-24 22:44:46，当前版本为作者最后更新于2024-08-17 20:26:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

校内模拟赛考了，于是写篇题解讲自己的做法。

题目链接。

题目大意

给出一个长度为 $n$ 的数组 $h$ 和一个限制 $k$，求

$$\max_{1\le l\le l+k-1\le r\le n}\left\{\gcd_{i=l}^{r}\{a_i\}\times\sum_{i=l}^{r}a_i\right\}\tag{1} $$

基本思路

赛时看到题目想到的是枚举 $\gcd$ 然后 dp。具体的，设 $dp(i,j)$ 表示最大化 $dp(i,j)$，使得 $h$ 中 $[i-dp(i,j)+1,i]$ 的公约数为 $j$。转移方程：

$$dp(i,j)= \begin{cases} dp(i-1,j)+1 & \text{if } j\mid a_i\\ 0 & \text{otherwise} \end{cases}\tag{2} $$

如果 $dp(i,j)\ge k$ 则更新答案：

$$ans\gets\max\left(ans,j\times \sum_{\mathclap{l=i-dp(i,j)+1}}^{i}a_i\;\right)\tag{3} $$

因为 $n,h_i\le 10^6$，直接 dp 肯定是不行的。

优化

首先要滚动数组，滚去 $i$ 这维。

其次 $(3)$ 中求和需要用前缀和优化。

还有枚举 $a_i$ 的约数 $j$ 也需要优化：对于每个数开一个 vector 存其约数，倒序枚举 $j$ 的倍数 $m$ 并将 $j$ 加入 $m$ 的 vector。这部分是调和级数 $O(V\ln V)$ 的，$V$ 表示值域。

接着注意到 $(2)$ 的 $\text{otherwise}$ 需要将 $dp(i,j)$ 置为 $0$。暴力清空肯定不行。

1. 可以使用时间戳优化：更新 $dp(j)$ 时将其时间戳（最近更新时间）$tag(j)\gets i$。转移时如果 $tag(j)=i-1$，则 $dp(j)\gets dp(j)+1$，反之 $dp(j)\gets 1$。这也是代码中的实现方式
2. 也可以直接判断是否满足 $j\mid a_{i-1}$，如果是，则 $i-1$ 时必然更新过 $dp(j)$，反之没有。

时间复杂度 $O(V\ln V+\sum d(a_i))$，$d(x)$ 表示 $x$ 的约数个数。

不懂可以看代码。

代码

还是很简洁的，压了行。

#include <iostream>
#include <vector>

using std::cin;
typedef long long ll;
constexpr int N=1e6+114514;
int n,k,V;
int a[N];
ll s[N]; // 前缀和
int dp[N],tag[N]; // dp 数组和时间戳
std::vector<int> e[N];

int gcd(int x,int y){return !y?x:gcd(y,x%y);}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>k; // 求前缀和、值域大小
	for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i],V=std::max(V,a[i]);
	// 枚举倍数求约数。e[x] 表示 x 的约数
	for(int i=1;i<=V;i++)for(int j=1;i*j<=V;j++)e[i*j].push_back(i);
	ll ans=0;
	for(int i=1;i<=n;i++)for(int j:e[a[i]])
	{
		if(tag[j]==i-1)dp[j]++; // 如果上次有更新（没清 0）则累加
		else dp[j]=1; // 反之上次会清 0，置成 1
		tag[j]=i; // 更新时间戳
		if(dp[j]>=k)ans=std::max(ans,(s[i]-s[i-dp[j]])*j); // 更新答案
	}
	printf("%lld",ans);
	return 0;
}