提炼
感觉这种题还是很金典的
我们看到乘积 就应该想到其很容易爆
而我们省1的话 也最多就是2e5数量级的
我们为了省事不用算上界 可以直接把这个上界设为1e9 也不会爆LL
只要乘积突破这个上界 我们就肯定要是有旁边的 大于1的数 我们都要吃掉 因为增量都超过了1e9那么多
我们只要算出左右两边 大于1的数的位置 输出即可
否则他们的乘积没有1e9那么多
我们最多 大于1的数 也就30来个
直接n2暴力即可
void solve(){
int n;cin>>n;
vector<int>a(n+1);
int now=1,flag=0;
for(int i=1;i<=n;i++){
cin>>a[i];
now*=a[i];
if(now>=1e9){
flag=1;
}
}
if(flag==1){
int i=1,j=n;
while(a[i]==1)i++;
while(a[j]==1)j--;
cout<<i<<' '<<j<<endl;
return;
}
vector<int>s(n+1,1),sum(n+1);
vector<int>v;
for(int i=1;i<=n;i++){
s[i]=a[i]*s[i-1];
sum[i]=a[i]+sum[i-1];
if(a[i]>1)v.push_back(i);
}
int ans=0,ans_l=1,ans_r=1;
for(int i=0;i<v.size();i++){
for(int j=i;j<v.size();j++){
int l=v[i],r=v[j],res=s[r]/s[l-1]+sum[l-1]+sum[n]-sum[r];
// cout<<l<<' '<<r<<' '<<res<<endl;
if(res>=ans){
ans=res;
ans_l=l,ans_r=r;
}
}
}
cout<<ans_l<<' '<<ans_r<<endl;
}
标签:895,int,Codeforces,flag,ans,1e9,now,Round,乘积
From: https://www.cnblogs.com/ycllz/p/17799852.html