首页 > 代码库 > bzoj3316: JC loves Mkk
bzoj3316: JC loves Mkk
Description
Input
第1行,包含三个整数。n,L,R。
第2行n个数,代表a[1..n]。
Output
仅1行,表示询问答案。
如果答案是整数,就输出整数;否则,输出既约分数“P/Q”来表示。
随机数据不卡精度所以可以分数规划二分答案
用两个单调队列维护奇偶位置上的前缀和,可以判定是否存在在[L,R]内的正权值偶数长度子串
#include<cstdio>typedef long long i64;char buf[10000007],*ptr=buf-1;int _(){ int x=0,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x;}int n,l,r;int a[200007];double s[200007];int s1[200007],s2[200007],l1,r1,l2,r2;i64 gcd(i64 a,i64 b){ for(i64 c;b;c=a,a=b,b=c%b); return a;}int main(){ buf[fread(buf,1,sizeof(buf),stdin)]=0; n=_();l=_();r=_(); if(l&1)++l; if(r&1)--r; double L=0,R=0; for(int i=1;i<=n;++i){ a[i]=_(); if(a[i]>R)R=a[i]; a[n+i]=a[i]; } int lp=0,rp=0; while(L<R){ double M=(L+R)/2; int l0=0,r0=0; l1=l2=1;r1=r2=0; for(int i=1;i<=n*2;++i){ s[i]=s[i-1]+a[i]-M; if(i-l>=0){ if(i-l&1){ while(l1<=r1&&s[s1[r1]]>s[i-l])--r1; s1[++r1]=i-l; }else{ while(l2<=r2&&s[s2[r2]]>s[i-l])--r2; s2[++r2]=i-l; } } if(i&1){ while(l1<=r1&&s1[l1]<i-r)++l1; if(l1<=r1&&s[s1[l1]]<s[i]){ l0=s1[l1]+1; r0=i; break; } }else{ while(l2<=r2&&s2[l2]<i-r)++l2; if(l2<=r2&&s[s2[l2]]<s[i]){ l0=s2[l2]+1; r0=i; break; } } } if(l0){ lp=l0;rp=r0; L=M+1e-8; }else R=M-1e-8; } i64 A=0,B=rp-lp+1,g; for(int i=lp;i<=rp;++i)A+=a[i]; g=gcd(A,B); A/=g;B/=g; if(B==1)printf("%lld",A); else printf("%lld/%lld",A,B); return 0;}
bzoj3316: JC loves Mkk
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。