首页 > 区间的连续段
开通博客写题解
头像 回归梦想
发表于 2020-11-10 22:04:38
来源：牛客网： 题目描述给你一个长为n的序列a和一个常数k 有m次询问，每次查询一个区间[l,r]内所有数最少分成多少个连续段，使得每段的和都 <= k 如果这一次查询无解，输出"Chtholly" 题解： 代码： #include<iostream> #include< 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 Meul
发表于 2020-03-31 18:00:07
NC82B 题意 给你一个长为n的序列a和一个常数k有m次询问，每次查询一个区间内所有数最少分成多少个连续段，使得每段的和都 <= k如果这一次查询无解，输出"" 思路 预处理 前缀和 ST表分两种情况考虑： 输出"" ，这种情况，用ans数组维护是否范围内存在的情况。 输出范围内所有数最 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-09-18 20:29:20
本题使用倍增的思路去做，如果不考虑区间问题要想分成最少个连续段使每段的和都<=k，那么就需要从第一位开始贪心的跳跃到最远的那个下标处。 那么我们按照这个思路对每一位数都可以得到一个可跳跃的最远下标。那么结合倍增，如果可以的话我们甚至可以直接跳跃1段，两段，四段。。。。那么在某一段里面到底 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 人丑心更黑
发表于 2021-01-28 16:16:33
本题一开始想的是用f[i][j]表示从i开始长度为2^j的和，然后每次查询的时候利用倍增去快速找到某一段的最右边。结果超时了，后来想了下，万一卡一个n段的数据，就挂了。而且这样倍增还不如直接O（1）预处理每个点到下一段的距离来得快。 题意: 给你一个长为n的序列a和一个常数k 有m次询问，每次查询一 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”