P14585 [LNCPC 2025] Entering the unknown 解题报告
_mi_ka_
·
·
题解
题目大意
给定正整数数组 a_n，求有多少个连续子数组满足：它的和可以被组成它的所有数的这些十进制一位数中的最大的数（后续思路中我将简称为最大值）整除。
解题思路
第一次看到这题的时候，我一眼想到了今年东北赛的 A，那道题赛时没开掉后来补掉的，做法是二分 + ST 表。所以这题我也往这两个方向去想了。
首先注意到一个单调性：当固定一个左端点 l 时，这个区间的最大值随着右端点 r 的变化不会变小。于是枚举每一个 l，我们可以二分去找后面所有最大值变大的地方（最大值变大的地方不会超过 9 次，所以这里的时间复杂度是常数倍的 O(\log n) ），其中二分里的 check 可以用 ST 表去 O(1) 的得到区间最大值。
现在考虑它对答案的贡献是什么。容易注意到如果一个区间 [l,r] 符合条件，那么设这段区间的最大值为 k，满足 k\mid (sum_r-sum_{l-1})，即 sum_r\equiv sum_{l-1}\pmod k。定义数组 cnt_{i,j,k} 表示
令 $c=9$，时间复杂度为 $O(c\times n\log n)$，空间复杂度为 $O(n\log n+nc^2)$。
::::success[AC Code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define N 100005
using namespace std;
int a[N],sum[N];
int st[N][20],cnt[N][10][10];
int query(int l,int r)//ST表查询
{
int len=(r-l+1);
int ww=log2(len);
int ans=max(st[l][ww],st[r-(1<<ww)+1][ww]);
return ans;
}
signed main()
{
int T=re();
while(T--)
{
int n=re();
for(int i=1;i<=n;i++)
a[i]=re(),sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=9;j++)
for(int k=0;k<j;k++)
cnt[i][j][k]=cnt[i-1][j][k]+(sum[i]%j==k);//计算 cnt
int w=log2(n);
for(int i=1;i<=n;i++)
{
int maxx=0;
int tem=a[i];
while(tem)
{
maxx=max(maxx,tem%10);
tem/=10;
}
st[i][0]=maxx;//初始化 ST表
}
for(int i=1;i<=w;i++)
for(int j=1;j<=n-(1<<i)+1;j++)
st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);//预处理 ST表
int ans=0;
for(int i=1;i<=n;i++)//枚举每一个左端点l
{
int maxx=query(i,i);
int id=i;//id当前最大值为maxx的这一段的左端点
while(maxx!=query(i,n))
{
int l=id,r=n;
while(l<r)
{
if(query(i,mid)>maxx)
r=mid;
else
l=mid+1;
}//找到最早增大的右端点
ans+=cnt[l-1][maxx][sum[i-1]%maxx]-cnt[id-1][maxx][sum[i-1]%maxx];//记录答案
id=l,maxx=query(i,id);//更新maxx和id
}
ans+=cnt[n][maxx][sum[i-1]%maxx]-cnt[id-1][maxx][sum[i-1]%maxx];//最后一段
}
wr(ans),putchar('\n');
}
return 0;
}
```