本文主要是介绍牛客小白月赛38 E-又一数区间问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://ac.nowcoder.com/acm/contest/11215/E
给定一个长为nn的数字串（只包含11到99的整数），求有多少个区间[l,r](l\leq r)l,r满足区间长度等于区间内所有数字的积。
输入描述:
第一行输入一个整数n代表数字串的长度
第二行给出该数字串，保证之中只含有1到9的数字。
输出描述:
输出一个整数，表示满足条件的区间个数。
解析
如果全都是非1的数字的话，累乘是非常之快的，因此一下子就超出了区间。但是如果存在1的，乘上1对我们的答案是没有贡献的，因此建立一个新的索引， n e [ i ] ne[i] ne[i]代表 i i i的下一个非1的下标。
当我们在累乘的过程中，将乘积储存到变量 s u m sum sum里面，此时的区间长度为 l e le le,区间左端点，右端点分别为 i , j i,j i,j。
当我们发现 s u m > = l e sum>=le sum>=le的时候，可以试着去拓展一下区间，如果后面都是1，那么我们的区间就会变小，因此我们通过 n e [ j ] ne[j] ne[j]跳转到我们下一个非0的数字的前一位 n e [ j ] − 1 ne[j]-1 ne[j]−1，所以此时的区间长度为 n e [ j ] − 1 − i + 1 = > n e [ j ] − i ne[j]-1-i+1=>ne[j]-i ne[j]−1−i+1=>ne[j]−i， 如果此时 n e [ j ] − i < = l e ne[j]-i<=le ne[j]−i<=le那么说明，在我们拓展的之中，存在一个区间满足此条件。因此累加答案。
时间复杂度问题：由于我们累乘过程中的区间大于n我们就直接退出循环，因此时间复杂度为 O ( n l o g N ) O(nlogN) O(nlogN)，每次我们累乘都是至少乘上2的，所以是对数时间复杂度。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char s[N];
int a[N],ne[N];
int main(){int n;cin>>n;scanf("%s",s+1);int p=n+1;for(int i=n;i>=1;i--){a[i]=s[i]-'0';ne[i]=p;if(a[i]!=1)p=i;}int ans=0;for(int i=1;i<=n;i++){for(int j=i,res=1;j<=n&&res<=n;j=ne[j]){int le=j-i+1;res*=a[j]; if(res>=le && res<=ne[j]-i){ans++;}}}cout<<ans;
}
这篇关于牛客小白月赛38 E-又一数区间问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
