【蓝桥杯 和与乘积】

题目描述

解题思路

首先想想可以组成答案的区间有什么性质。很直观可以想到排除长度为1的和长度为2的，构成答案的区间肯定是由几个非1的数加上一堆1构成的。
那么可以很容易的想到区间长度k有下面这个等式

k=mul-sm+tot
mul为区间非1的数的乘积
sm为区间非1数的和
tot为区间非1数的个数
例如：[1 3 2]是一个合法区间，mul=6,sm=5,tot=2.
k=6-5+2=3 很合理

那么统计区间个数，可以考虑枚举区间的右端点 i，然后往前枚举非1的数，求出区间宽度k，检验区间[i-k+1,i]是否成立就好了。
可以知道，如果求得的i-k<0，那么就不可能得到合法区间了。那么非1最大个数是多少呢，可以想到差不多当mul>400000的时候就基本不会有合法区间了(很显然)。那么枚举非1数的时间复杂就是logn级别的，总的时间复杂度就是nlogn的。

最后这份没有交过，仅供参考。

上代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 600005
#define ll long long

int n;
int a[N],pre_pos[N];
ll sum[N];

int ans;
int main(){
	ll Max_val=N;
	scanf("%d",&n);
	int pre=0; 
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pre_pos[i]=pre;
		if(a[i]!=1)pre=i;
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		ans++;
		ll mul=a[i]*a[pre_pos[i]],now=pre_pos[i],sm=a[i]+a[pre_pos[i]]-2;
		if(now==0)continue;
		while(mul<=Max_val){
			if(i-mul+sm<0)break;
			if(sum[i]-sum[i-(mul-sm)]==mul){
				printf("%d %d %d %d!\n",sum[i]-sum[i-(mul-sm)],mul,i,i-(mul-sm)+1);
				ans++;
			}
			if(pre_pos[now]==0)break;
			else {
				mul=mul*a[pre_pos[now]];
				sm=sm+a[pre_pos[now]]-1;
				now=pre_pos[now];
			}
		}
	}
	printf("%d\n",ans);
}