BZOJ 3613 Heoi2014 南园满地堆轻絮 二分答案/线性做法

题目大意:给定1个序列a,求1个单调不减的序列b,使max{|ai-bi|}最小

逗比题。。。。。

2分答案做法:

每次验证时从右向左扫描

如果当前数字小于等于右边的数字,就把这个数字向上调剂到极限(到达右边的数字或调剂的值到达上界)

如果当前数字大于右边的数字,就把这个数字向下调剂到与右边数字相等 没法如此做则返回false

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 5005005
using namespace std;
int n,a[M];
long long Sa,Sb,Sc,Sd,mod;
int F(int x)
{
long long re=Sd,temp=x;
re+=Sc*temp%mod;(temp*=x)%=mod;
re+=Sb*temp%mod;(temp*=x)%=mod;
re+=Sa*temp%mod;
return int(re%mod);
}
bool Judge(int x)
{
int i,min_num=2147483647;
for(i=n;i;i–)
{
if(a[i]<=min_num)
min_num=min(min_num,a[i]+x);
else if(a[i]-min_num>x)
return false;
}
return true;
}
int Bisection()
{
int l=0,r=mod⑴;
while(l+1<r)
{
int mid=l+r>>1;
if( Judge(mid) )
r=mid;
else
l=mid;
}
return Judge(l)?l:r;
}
int main()
{
int i;
cin>>n>>Sa>>Sb>>Sc>>Sd>>a[1]>>mod;
for(i=2;i<=n;i++)
a[i]=(F(a[i⑴])+F(a[i⑵]))%mod;
cout<<Bisection()<<endl;
return 0;
}

但是500W明显nlogn压力山东大学(虽然我本机慢的要死最大的点都只跑了1.5秒)

因此我还是去看了标程的线性做法

打开cpp的那1刻我震精了――

答案等于差值最大的逆序对的差值+1>>1

正确性明显。。。。。。明显。。。。。明显。。。。。。。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 5005005
using namespace std;
int n,ans,a[M];
long long Sa,Sb,Sc,Sd,mod;
int F(int x)
{
long long re=Sd,temp=x;
re+=Sc*temp%mod;(temp*=x)%=mod;
re+=Sb*temp%mod;(temp*=x)%=mod;
re+=Sa*temp%mod;
return int(re%mod);
}
int main()
{
int i;
cin>>n>>Sa>>Sb>>Sc>>Sd>>a[1]>>mod;
for(i=2;i<=n;i++)
a[i]=(F(a[i⑴])+F(a[i⑵]))%mod;
int max_val=0;
for(i=1;i<=n;i++)
{
max_val=max(max_val,a[i]);
ans=max(ans,max_val-a[i]+1>>1);
}
cout<<ans<<endl;
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » BZOJ 3613 Heoi2014 南园满地堆轻絮 二分答案/线性做法

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡