正文
JZOJ 5409 Fantasy & NOI 2010 超级钢琴 题解
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
其实早在 2020-12-26 的比赛我们就做过 5409. Fantasy
这可是紫题啊
题目大意
给你一个序列，求长度在 \([L,R]\) 区间内的 \(k\) 个连续子序列的最大和
题解
如此多的子序列并不好处理
设 \(i\) 为一个区间的左端点，那么右端点的区间为 \([i+L-1,i+R-1]\) ，记前缀和为 \(sum_i\)
那么一个区间 \([i,j]\) 的和就是 \(sum_j-sum_{i-1}\) 已经知道左端点 \(sum_i\) ，只要找到最大的 \(sum_j\) 即可
所以可以用 \(\text{RMQ}\) 来解决查找问题。考虑把一个区间变成四元组 \(\{now,l,r,id\}\)
表示左端点 \(i\) 的位置，右端点的区间，区间 \([l,r]\) 中 \(j\) 的位置 。将一些四元组放入堆中
每次将堆顶的拆成两个 \(\{now,l,id-1,id_1\},\{now,pos+1,r,id_2\}\)
再放进堆中，原堆顶删除。\(id_1,id_2\) 都是 \(\text{RMQ}\) 实现，每次堆顶的值 \(sum_{id}-sum_{now-1}\) 的和就是答案
Code
#include<bits/stdc++.h>
using namespace std;
char buf[100000],*S=buf,*T=buf;
inline char Gc() {
return S==T&&(T=(S=buf)+fread(buf,1,100000,stdin),S==T)?EOF:*S++;
}
inline int Rd() {
register int o=0,f=0;
static char c=Gc();
for(;c<'0'||c>'9';c=Gc()) f|=c==45;
for(;c>'/'&&c<':';c=Gc()) o=(o<<1)+(o<<3)+(c^48);
return f?-o:o;
}
const int N=500005;
typedef long long LL;
int n,K,L,R,pw[35]={1},lg[N],sum[N],f[N][35];
LL ans;
inline int maxx(int x,int y) { return sum[x]>sum[y]?x:y; }
inline int RMQ(int l,int r) {
register int k=lg[r-l+1];
return maxx(f[l][k],f[r-pw[k]+1][k]);
}
struct node {
int x,l,r,id; node() { }
inline node(int _x,int _l,int _r):x(_x),l(_l),r(_r),id(RMQ(_l,_r)) { }
inline bool operator<(const node &o) const {
return sum[id]-sum[x-1]<sum[o.id]-sum[o.x-1]; }
}oo;
priority_queue<node>heap;
int main() {
//freopen("fantasy.in","r",stdin);
//freopen("fantasy.out","w",stdout);
for(int i=1;i<31;i++)pw[i]=pw[i-1]<<1;
n=Rd(),K=Rd(),L=Rd(),R=Rd();
for(int i=1;i<=n;i++)f[i][0]=i,sum[i]=sum[i-1]+Rd();
for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
for(int j=1;j<=lg[n];j++)
for(int i=0;i+pw[j-1]-1<=n;i++)
f[i][j]=maxx(f[i][j-1],f[i+pw[j-1]][j-1]);
for(int i=1;i<=n;i++)
if(i+L-1<=n)
heap.push(node(i,i+L-1,min(i+R-1,n)));
while(K--) {
oo=heap.top(),heap.pop(),ans+=1LL*sum[oo.id]-1LL*sum[oo.x-1];
if(oo.l^oo.id)heap.push(node(oo.x,oo.l,oo.id-1));
if(oo.id^oo.r)heap.push(node(oo.x,oo.id+1,oo.r));
}
printf("%lld",ans);
}
JZOJ 5409 Fantasy & NOI 2010 超级钢琴 题解的更多相关文章- [BZOJ 2006] [NOI 2010]超级钢琴(贪心+ST表+堆)
[BZOJ 2006] [NOI 2010]超级钢琴(贪心+ST表+堆) 题面 给出一个长度为n的序列,选k段长度在L到R之间的区间,一个区间的值等于区间内所有元素之的和,使得k个区间的值之和最大.区 ...
- [NOI 2010]超级钢琴
Description 小Z是一个小有名气的钢琴家,最近C博士送给了小Z一架超级钢琴,小Z希望能够用这架钢琴创作出世界上最美妙 的音乐. 这架超级钢琴可以弹奏出n个音符,编号为1至n.第i个音符的美妙 ...
- ●BZOJ 2006 NOI 2010 超级钢琴
题链: http://www.lydsy.com/JudgeOnline/problem.php?id=2006 题解: RMQ + 优先队列 (+ 前缀) 记得在一两个月前,一次考试考了这个题目的简 ...
- 解题：NOI 2010 超级钢琴
题面 WC时候写的题,补一下 做法比较巧妙:记录每个位置和它当前对应区间的左右端点,做前缀和之后重载一下小于号,用优先队列+ST表维护当前最大值.这样贡献就是区间最大值和端点左边差分一下,可以O(1) ...
- BZOJ2006：[NOI2010]超级钢琴——题解
https://www.lydsy.com/JudgeOnline/problem.php?id=2006 https://www.luogu.org/problemnew/show/P2048#su ...
- 洛谷P2048 [NOI2010]超级钢琴 题解
2019/11/14 更新日志: 近期发现这篇题解有点烂,更新一下,删繁就简,详细重点.代码多加了注释.就酱紫啦! 正解步骤 我们需要先算美妙度的前缀和,并初始化RMQ. 循环 \(i\) 从 \(1 ...
- JZOJ5409. Fantasy &;&; Luogu2048 [NOI2010]超级钢琴
题目大意 给出一个序列和\(L, R\), 求前k大长度在\([L,R]\)之间的连续子序列的和的和. 解题思路 朴素的想法是对于一个左端点\(p\), 它的右区间取值范围是一个连续的区间即\([p+ ...
- 【NOI2010】超级钢琴 题解（贪心+堆+ST表）
题目链接 题目大意:求序列内长度在$[L,R]$范围内前$k$大子序列之和. ---------------------- 考略每个左端点$i$,合法的区间右端点在$[i+L,i+R]$内. 不妨暴力 ...
- 【题解】P2048 [NOI2010]超级钢琴
[题解][P2048 NOI2010]超级钢琴 一道非常套路的题目.是堆的套路题. 考虑前缀和,我们要是确定了左端点,就只需要在右端区间查询最大的那个加进来就好了.\(sum_j-sum_{i-1} ...
随机推荐- hdu1115(计算多边形几何重心)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1115 题意:给出一些点,求这些点围成的多边形的重心: 思路: 方法1:直接分别求所有点的x坐标的平均值 ...
- New ipad install Metasploit(New ipad 安装Metasploit)
Title:New ipad install Metasploit(New ipad 安装Metasploit) --2012-09-19 11:35 越狱以后,Ssh或者终端Ipad,把屏幕锁定最好 ...
- 软件测试学习日志————round 0 An impressed error in my past projects
在初学各种语言时总会出现各种错误,比如main携程mian.忘了加各种库,打错字等等等等.虽然这些错误后面看来很幼稚,但是有的时候真的会让人印象很深刻. 在初学JavaScript时,我对JavaSc ...
- [置顶] 应广大童鞋的要求提供一个封装模块，直接和ADB 服务进程交互
很多童鞋在用ADB 的时候都是直接启动ADB 的进程,然后通过管道的方式获取输出,这样多个线程同时使用ADB 的时候任务管理器一闪一闪的,是不是很不爽啊,原先介绍过可以直接和ADB 服务进程通信,不用 ...
- 玩转html5(三)---智能表单（form），使排版更加方便
<!DOCTYPE html> <head> <meta http-equiv="Content-Type" content="text/h ...
- Unsupervised Learning and Text Mining of Emotion Terms Using R
Unsupervised learning refers to data science approaches that involve learning without a prior knowle ...
- js判断值为null
今天在做项目的时候,犯了一个着实不应该的错误,拿到data为null,然后判断如果为null执行A,否则执行B 我错误的代码是 if(data===null){ A; }else{ B; } 怎么调试 ...
- $Django 路由层(有,无名分组、反向解析、总路由分发、名称空间、伪静态)
1 简单配置 -第一个参数是正则表达式(如果要精准匹配:'^publish/$') -第二个参数是视图函数(不要加括号) -url(r'^admin/', admin.site.urls), 注: ...
- UVa 11572 唯一的雪花（滑动窗口）
https://vjudge.net/problem/UVA-11572 题意:输入一个长度为n的序列A,找到一个尽量长的连续子序列,使得该序列中没有相同的元素. 思路:很简单的题,也没啥好解释的了. ...
- MySQL安装、基本账户安全（5.0以后版本）
博文目录: 1.Mysql-5.0.40.tar.gz Mysql-5.1.72.tar.gz 2.Mysql-5.5.22.tar.gz 3.Mysql-5.5.34.tar.gz 4.Mysql- ...
[BZOJ 2006] [NOI 2010]超级钢琴(贪心+ST表+堆) 题面 给出一个长度为n的序列,选k段长度在L到R之间的区间,一个区间的值等于区间内所有元素之的和,使得k个区间的值之和最大.区 ...
Description 小Z是一个小有名气的钢琴家,最近C博士送给了小Z一架超级钢琴,小Z希望能够用这架钢琴创作出世界上最美妙 的音乐. 这架超级钢琴可以弹奏出n个音符,编号为1至n.第i个音符的美妙 ...
题链: http://www.lydsy.com/JudgeOnline/problem.php?id=2006 题解: RMQ + 优先队列 (+ 前缀) 记得在一两个月前,一次考试考了这个题目的简 ...
题面 WC时候写的题,补一下 做法比较巧妙:记录每个位置和它当前对应区间的左右端点,做前缀和之后重载一下小于号,用优先队列+ST表维护当前最大值.这样贡献就是区间最大值和端点左边差分一下,可以O(1) ...
https://www.lydsy.com/JudgeOnline/problem.php?id=2006 https://www.luogu.org/problemnew/show/P2048#su ...
2019/11/14 更新日志: 近期发现这篇题解有点烂,更新一下,删繁就简,详细重点.代码多加了注释.就酱紫啦! 正解步骤 我们需要先算美妙度的前缀和,并初始化RMQ. 循环 \(i\) 从 \(1 ...
题目大意 给出一个序列和\(L, R\), 求前k大长度在\([L,R]\)之间的连续子序列的和的和. 解题思路 朴素的想法是对于一个左端点\(p\), 它的右区间取值范围是一个连续的区间即\([p+ ...
题目链接 题目大意:求序列内长度在$[L,R]$范围内前$k$大子序列之和. ---------------------- 考略每个左端点$i$,合法的区间右端点在$[i+L,i+R]$内. 不妨暴力 ...
[题解][P2048 NOI2010]超级钢琴 一道非常套路的题目.是堆的套路题. 考虑前缀和,我们要是确定了左端点,就只需要在右端区间查询最大的那个加进来就好了.\(sum_j-sum_{i-1} ...
- hdu1115(计算多边形几何重心)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1115 题意:给出一些点,求这些点围成的多边形的重心: 思路: 方法1:直接分别求所有点的x坐标的平均值 ...
- New ipad install Metasploit(New ipad 安装Metasploit)
Title:New ipad install Metasploit(New ipad 安装Metasploit) --2012-09-19 11:35 越狱以后,Ssh或者终端Ipad,把屏幕锁定最好 ...
- 软件测试学习日志————round 0 An impressed error in my past projects
在初学各种语言时总会出现各种错误,比如main携程mian.忘了加各种库,打错字等等等等.虽然这些错误后面看来很幼稚,但是有的时候真的会让人印象很深刻. 在初学JavaScript时,我对JavaSc ...
- [置顶] 应广大童鞋的要求提供一个封装模块，直接和ADB 服务进程交互
很多童鞋在用ADB 的时候都是直接启动ADB 的进程,然后通过管道的方式获取输出,这样多个线程同时使用ADB 的时候任务管理器一闪一闪的,是不是很不爽啊,原先介绍过可以直接和ADB 服务进程通信,不用 ...
- 玩转html5(三)---智能表单（form），使排版更加方便
<!DOCTYPE html> <head> <meta http-equiv="Content-Type" content="text/h ...
- Unsupervised Learning and Text Mining of Emotion Terms Using R
Unsupervised learning refers to data science approaches that involve learning without a prior knowle ...
- js判断值为null
今天在做项目的时候,犯了一个着实不应该的错误,拿到data为null,然后判断如果为null执行A,否则执行B 我错误的代码是 if(data===null){ A; }else{ B; } 怎么调试 ...
- $Django 路由层(有,无名分组、反向解析、总路由分发、名称空间、伪静态)
1 简单配置 -第一个参数是正则表达式(如果要精准匹配:'^publish/$') -第二个参数是视图函数(不要加括号) -url(r'^admin/', admin.site.urls), 注: ...
- UVa 11572 唯一的雪花（滑动窗口）
https://vjudge.net/problem/UVA-11572 题意:输入一个长度为n的序列A,找到一个尽量长的连续子序列,使得该序列中没有相同的元素. 思路:很简单的题,也没啥好解释的了. ...
- MySQL安装、基本账户安全（5.0以后版本）
博文目录: 1.Mysql-5.0.40.tar.gz Mysql-5.1.72.tar.gz 2.Mysql-5.5.22.tar.gz 3.Mysql-5.5.34.tar.gz 4.Mysql- ...
