牛客 乘法师

1非负包括0啊,开始没考虑到,直接把整个数组当成一个区间来求了 ,还迟迟找不着Bug,我真是越来越憨了……先考虑一个区间不包括0的情况,比如N=7 V=9 Ai依次是2 2 2 8 1 1 2 起初pre=1;nex=1;mul=1;以pre为起点,让nex往后移动,并更新mul*=a[nex];直到mul>=V;说明nex及其之后的下标都可以,cnt+=4,此时nex<mark>4;mul</mark>64,之后让pre后移,并且更新mul/=a[pre];发现此时mul>=V;即此时以pre为起点,nex及其以后的下标中间的区间仍可以,更新cnt+=4;pre不断后移……直到pre<V,然后再将nex后移更新mul值。。。。题目Ai应为可能为0所以要划分区间,计算每一个不包含0 的区间求和即可,注意V==0要特殊考虑代码奉上

#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

#define pi acos(-1.0)//我真***,非负包括0 
#define e exp(1.0)
typedef long long ll;
const ll maxn=1e5+7;
ll T,N,V,cnt;
ll a[maxn];
void Han(ll beg,ll end)
{
	ll pre,nex,mul=1;
	pre=beg;
	nex=beg;
	while(nex<=end)
	{
		if(mul*a[nex]>=V)
		{
			mul*=a[nex];
			cnt+=(end-nex+1);
			mul/=a[pre];
			pre++;
			while(mul>=V&&pre<=nex)
			{
				cnt+=(end-nex+1);
				mul/=a[pre];
				pre++;
			}
			if(mul<V)
			nex++;
			else
			nex=pre;
		}
		else
		{
			mul*=a[nex];
			nex++;	
		}
	}
	return ;
}
int main()
{
// freopen(".../.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		cin>>N>>V;
		ll i,j;
		for(i=1;i<=N;i++)
		cin>>a[i];
		cnt=0;
		if(!V)
		{
			cout<<N*(N+1)/2<<endl;
			continue;
		}
		ll l,r;
		for(i=1;i<=N;i++)
		{
			if(a[i]>0)
			{
				l=i;
				r=l+1;
				while(a[r]>0&&r<=N)//找到被0分割区间 
				r++;
				if(a[r]==0)
				{
					i=r;
					r--;
					Han(l,r);
				} 
				else//找到最后也没有找等于0的,单独作为一个区间
				{
					r=N;
					i=N;
					Han(l,r);
				}
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务