目录
BZOJ3613 南园满地堆轻絮题解ｃｏｄｅ
BZOJ3613 南园满地堆轻絮
题目传送门
题解
这标题怎么那么鬼畜一眼可以看出来是二分。二分调整音符的幅度，然后对于每个音符，都尽量让它取符合条件的最小的值，如果仍然无法形成非递减，那么说明当前答案不合法，就增加左区间，反之减小右区间。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int maxn=5e6+500;
int n;
ll a[maxn],sa,sb,sc,sd,Md;
ll Mx;
/*==================Define Area================*/
ll Thr(ll x) {return x*x%Md*x%Md;}
ll Sq(ll x) {return x*x%Md;}
ll F(ll x) {
return ((sa*Thr(x)%Md+sb*Sq(x)%Md)%Md+sc*x%Md)%Md+sd;
}
bool check(ll x) {
ll last;
for(int i=1;i<=n;i++) {
if(i==1) {
last=max(a[i]-x,0ll);
continue ;
}
if(a[i]>=last) last=max(last,a[i]-x);
else {
if(a[i]+x<last) return 0;
}
}
return 1;
}
int main() {
read(n);read(sa);read(sb);read(sc);read(sd);read(a[1]);read(Md);
for(int i=2;i<=n;i++) {
a[i]=F(a[i-1])%Md+F(a[i-2])%Md;
a[i]%=Md;
Mx=max(Mx,a[i]);
}
ll L=0,R=Mx,ans;
while(L<=R) {
ll Mid=(L+R)>>1;
if(check(Mid)) {
R=Mid-1;
ans=Mid;
}
else L=Mid+1;
}
printf("%lld\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9435733.html
