P9032 [COCI2022-2023#1] Neboderi 题解

· · 题解

前言

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

题目链接。

题目大意

给出一个长度为 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;
}