「HEOI2014」南园满地堆轻絮

时间:2022-09-08 09:50:51

题目链接

戳我

题目出处

菩萨蛮·南园满地堆轻絮

                                            温庭筠

南园满地堆轻絮,愁闻一霎清明雨。雨后却斜阳,杏花零落香。

无言匀睡脸,枕上屏山掩。时节欲黄昏,无憀独倚门。

\(Solution\)

这个可以二分一下,再贪心的构造式子,如果满足则\(r\)变小,反之\(l\)变大很好理解的。

\(Code\)

#include<bits/stdc++.h>
#define int long long
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
int a[5000010],b[5000010];
int n,Sa,Sb,Sc,Sd,mod,maxx;
int calc(int x){
return (((Sa*x%mod*x%mod*x%mod+Sb*x%mod*x%mod)%mod+Sc*x%mod)%mod+Sd)%mod;
}
bool check(int x){
for(int i=1;i<=n;i++)
b[i]=a[i];
for(int i=1;i<=n;i++){
if(b[i]+x<b[i-1]) return 0;
if(b[i]<b[i-1]) b[i]=b[i-1];
else b[i]=max(b[i-1],b[i]-x);
}
return 1;
}
main(){
n=read(),Sa=read(),Sb=read(),Sc=read(),Sd=read(),maxx=a[1]=read(),mod=read();
for(int i=2;i<=n;i++)
a[i]=(calc(a[i-1])+calc(a[i-2]))%mod,maxx=max(maxx,a[i]);
int l=0,r=maxx,minx=2147483647;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) r=mid-1,minx=min(minx,mid);
else l=mid+1;
}
printf("%lld",minx);
return 0;
}

「HEOI2014」南园满地堆轻絮的更多相关文章

  1. 【BZOJ】【3613】【HEOI2014】南园满地堆轻絮

    思路题 考试结束前5.6min的时候想到……但是写挂了QAQ 其实就是(差值最大的逆序对之差+1)/2; 找逆序对其实维护一个max直接往过扫就可以了……因为逆序对是前面的数大于后面的数…… 正确性显 ...

  2. BZOJ&lowbar;3613&lowbar;&lbrack;Heoi2014&rsqb;南园满地堆轻絮&lowbar;二分答案

    BZOJ_3613_[Heoi2014]南园满地堆轻絮_二分答案 Description 小 Z 是 ZRP(Zombies’ Republic of Poetry,僵尸诗歌*)的一名诗歌爱好者, ...

  3. 【BZOJ3613】&lbrack;HEOI2014&rsqb;南园满地堆轻絮(贪心)

    [BZOJ3613][HEOI2014]南园满地堆轻絮(贪心) 题面 BZOJ 洛谷 题解 考虑二分的做法,每次二分一个答案,那么就会让所有的值尽可能的减少,那么\(O(n)\)扫一遍就好了. 考虑如 ...

  4. 3613&colon; &lbrack;Heoi2014&rsqb;南园满地堆轻絮

    3613: [Heoi2014]南园满地堆轻絮 Time Limit: 50 Sec Memory Limit: 256 MB Submit: 827 Solved: 534 [Submit][Sta ...

  5. &lbrack;HEOI2014&rsqb;南园满地堆轻絮

    [HEOI2014]南园满地堆轻絮 BZOJ luogu 二分答案贪心check 首先b[1]最小一定优 之后就贪心的最小化b[i]就行 #include<bits/stdc++.h> u ...

  6. &lbrack;luogu&rsqb; P4105 &lbrack;HEOI2014&rsqb;南园满地堆轻絮 &lpar;贪心&rpar;

    P4105 [HEOI2014]南园满地堆轻絮 题目描述 小 Z 是 ZRP(Zombies' Republic of Poetry,僵尸诗歌*)的一名诗歌爱好者,最近 他研究起了诗词音律的问题. ...

  7. &lbrack;BZOJ3613&rsqb;&lbrack;Heoi2014&rsqb;南园满地堆轻絮 二分答案

    Description 小 Z 是 ZRP(Zombies’ Republic of Poetry,僵尸诗歌*)的一名诗歌爱好者,最近 他研究起了诗词音律的问题.   在过去,诗词是需要编成曲子唱 ...

  8. BZOJ3613 南园满地堆轻絮-二分法

    http://www.lydsy.com/JudgeOnline/problem.php?id=3613 //话说BZOJ终于修好了... Description 小 Z 是 ZRP(Zombies' ...

  9. BZOJ3613&colon; &lbrack;Heoi2014&rsqb;南园满地堆轻絮

    分析: 构造数据时间有些长,可以用秦九韶优化一下. 二分答案+贪心,即:另每一个b[i]尽可能的小的同时满足题意,在枚举过程中,判断是否存在一个b[i-1]>a[i]+x 如果存在,那么向右找 ...

随机推荐

  1. 著名的sql注入问题-问题的原因分析及总结

    Statement安全漏洞(sql注入问题)问题展示: 首先我的Mysql数据库中有一张users表,如下图所示 /** * 根据用户名查询用户 * @param username 需要查询的用户名 ...

  2. Tomcat 学习笔记二

    学习一 java.bean.PropertyChangeListener用来监听bean类的属性值改变.当改变时同时执行对应事件.而且是线程安全的.tomcat用此reload的Boolean值改变是 ...

  3. 测试部署环境用到的主要linux命令

    1 部署前检查开发是否上传部署文档 2 在测试组中告知大家 3 将上一版本进行备份(cp -r neiguan-tomcat/ /home/personal/backup/neiguan-tomcat ...

  4. &lbrack;刷题&rsqb;算法竞赛入门经典&lpar;第2版&rpar; 5-3&sol;UVa10935 - Throwing cards away I

    书上具体所有题目:http://pan.baidu.com/s/1hssH0KO 代码:(Accepted,0 ms) //UVa10935 - Throwing cards away I #incl ...

  5. Codeforces Round &num;408 &lpar;Div&period; 2&rpar;

    C. Bank Hacking 题目大意:给出一棵n个节点的树,每个节点有一个权值,删掉一个点的代价为当前这个点的权值,并且会使其相邻点和距离为2且中间隔着未被删除的点的点权值加1,现在选一个点开始删 ...

  6. 查找第三方银行官方app下载链接探索过程

    需求:最近有个需求,点击按钮,弹出一个所需银行选项的非全屏弹出层,再点击某银行选项,随即跳转到该银行的app下载界面,如下图所示           注:这里只是引用相关银行的链接,不需要做什么逻辑处 ...

  7. 使用Zabbix监控mysql的主从同步

    Zabbix 监控触发器设置 简述 在生产环境中,有一台mysql的备份服务器,上面运行着三个数据库实例的从库,也在做日志的同步工作,为了实现对该备份服务器的监控,当出现从库实例不为3或者日志同步进程 ...

  8. CSS 随笔

    1.动态修改div的大小 Html: <div> Hello </div> css: div { resize:both; overflow:auto; } 2. box-si ...

  9. 前端之jquery基础

    一 jquery介绍 介绍:jquery是一种轻量级的语言,是javascript的简化,使用javascript语言写成的.将javascript的代码简化了,并且兼容了多个浏览器的javascri ...

  10. centos7 设置 静态IP

    centos7 图形设置 yum install NetworkManager-tui #centos7 nmtui edit eth0 #图形设置ip systemctl restart netwo ...