设计类培训机构/seo网站推广计划

前言

太简单了吧,就debug难而已
传送门: https://ac.nowcoder.com/acm/contest/11215/E

思路

一开始区间问题想到的是 线段树,RMQ,树状数组.但是看完题目之后

发现维护的是 区间乘积, 查询是 logn 然后枚举区间 nlogn 因此理论可行

但是我不会写awa

因为此题给的是 1-9不难想到 是 string 字符

所以我们可以通过枚举左端点 O n

但是这么算下来不就是 O n^2 的了 ？

因此我们可以优化

• 区间长度1e5

1. 所有都是1的话 那么会 On^2 因此需要处理1
2. 所有都是2的话 那么也就 logn
3. 如果是其他数的话 那么一定会超当前的 n 直接break

所有思路就清晰了

我们现在是需要处理 1 就行了

因此学过一点图论的都知道,当我们不想计算某些边的时候,可以将next指向下一条边

因此通过next[] 跳过1即可

CODE

#include <bits/stdc++.h>
using namespace std;
const int N  =1e5+10;
int ne[N],num[N];
void solve()
{int n;cin>>n;string t;cin>>t;string s = " "+t;int pos = n ;for(int i=n;i;i--){if(s[i+1]!='1')ne[i]=i+1;else ne[i]=ne[i+1];}int res = 0 ;for(int i=1;i<=n;i++){int ans = 1;for(int j = i;j<=n;j=ne[j]){ans*=(s[j]-'0');if(ans > n)break;if(ans == (j - i +1))++res;if(ans>j-i+1 && ans<=ne[j]-i)++res;}}cout<<res<<endl;
}int main()
{ios::sync_with_stdio(false);solve();return 0;
}