BZOJ3613 南园满地堆轻絮 二分/贪心
正解:贪心
解题报告:
这题似乎是可以二分水过的,,,但数据可以加强一下就能简单把二分卡住了,或者修改下空间限制什么的反正就很容易能卡住
所以这里介绍一个优秀的贪心做法,O(n)的时间复杂度和O(1)级别的空间复杂度就很美
首先二分还是能get的趴?就二分一个mid,对前面就能加就加对后面就能减就减,然后就做完了
这时候我们考虑一下二分出的这个mid的本质是什么?就是对每个数,它本来的取值只能是a[i],现在通过这个mid的存在,它可以取[a[i]-d,a[i]+d]范围内的所有值了,就相当于是对应一个区间了
然后题目就变成了,给一个若干条竖直块构成的图形,问从最左边开始走能否不向下一路走到最右
显然最低的要求就只要有一条平直的线能经过就欧克了,所以就只要最低点的最高和最高点的最低在同一高度就好,所以就
{x-mid}max={x+mid}min
可得mid=(xmax-xmin)/2
大概这样儿,over!
哦注意一下就是我重看一遍我题解发现我有个地方表述不清,,,就是这里的minmax因为其实是说以某个点为分界线的左边的max和右边的min,然后把这个算出来的答案再取个max,然后在实际实现中只要递推过程中更新一下max,计算以当前点为min的贡献,取max就好!
over
放个代码嘻嘻,真的难得一发过了,好爽昂QAQ
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
const int N=5000000+10;
int n,a,b,c,d,mod,mx,x[N],as;
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
int F(ri x){return (1ll*a*x%mod*x%mod*x%mod+1ll*b*x%mod*x%mod+1ll*c*x%mod+d)%mod;}
int main()
{
n=read();a=read();b=read();c=read();d=read();x[1]=read();mod=read();rp(i,2,n)x[i]=(F(x[i-1])+F(x[i-2]))%mod;
rp(i,1,n){mx=max(mx,x[i]);as=max(as,(mx-x[i]+1)>>1);}printf("%d\n",as);
return 0;
}