专栏文章

P14585 [LNCPC 2025] Entering the unknown 解题报告

__mi_ka_
P14585题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0g7x8
此快照首次捕获于
2025/12/01 18:32
3 个月前
此快照最后确认于
2025/12/01 18:32
3 个月前
查看原文

题目大意

给定正整数数组 ana_n，求有多少个连续子数组满足：它的和可以被组成它的所有数的这些十进制一位数中的最大的数（后续思路中我将简称为最大值）整除。

解题思路

第一次看到这题的时候，我一眼想到了今年东北赛的 A，那道题赛时没开掉后来补掉的，做法是二分 + ST 表。所以这题我也往这两个方向去想了。
首先注意到一个单调性：当固定一个左端点 ll 时，这个区间的最大值随着右端点 rr 的变化不会变小。于是枚举每一个 ll，我们可以二分去找后面所有最大值变大的地方（最大值变大的地方不会超过 99 次，所以这里的时间复杂度是常数倍的 O(log⁡n)O(\log n) ），其中二分里的 check 可以用 ST 表去 O(1)O(1) 的得到区间最大值。
现在考虑它对答案的贡献是什么。容易注意到如果一个区间 [l,r][l,r] 符合条件，那么设这段区间的最大值为 kk，满足 k∣(sumr−suml−1)k\mid (sum_r-sum_{l-1})，即 sumr≡suml−1(modk)sum_r\equiv sum_{l-1}\pmod k。定义数组 cnti,j,kcnt_{i,j,k} 表示 ∑l=1i[suml≡k(modj)]\sum_{l=1}^{i}[sum_l\equiv k\pmod j]，对于枚举的每一个左端点 ll，最大值保持为 kk 的一个最大的 rr 的区间为 [u,v][u,v]，对答案的贡献为 cntv,k,suml−1 mod k−cntu−1,k,suml−1 mod kcnt_{v,k,sum_{l-1} \bmod k}-cnt_{u-1,k,sum_{l-1}\bmod k}。对于枚举到每一个 ll，二分去找到每一个最大值变大的地方，记录答案即可。
令 c=9c=9，时间复杂度为 O(c×nlog⁡n)O(c\times n\log n)，空间复杂度为 O(nlog⁡n+nc2)O(n\log n+nc^2)。
AC CodeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...