首页 / 更多教程 / 牛客练习赛14B 区间的连续段
牛客练习赛14B 区间的连续段
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了牛客练习赛14B 区间的连续段,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2180字,纯文字阅读大概需要4分钟。
内容图文
![牛客练习赛14B 区间的连续段](/upload/InfoBanner/zyjiaocheng/1000/1e3bba43b6ec47ff8f660e383567f75d.jpg)
题目链接
题目大意
给定一个长度为 \(N\) 的序列 \(A\) 和一个常数 \(K\)
有 \(M\) 次询问
每次询问查询一个区间 \([L , R]\) 内所有数最少分成多少个连续段
使得每段的和都 \(<= K\) ,若无解则输出 "\(Chtholly\)"
解题思路
简单回忆一下倍增求 \(LCA\) 思想:
- \(f[i][j]\) 表示以 \(i\) 为起点,往上跳 \(i + 2^j\) 步后得到的祖先
- 因为往上跳 \(2^j\) 等价于先往上跳 \(2^{j - 1}\) 步后再往上跳 \(2^{j - 1}\) 步
- 所以可得: \(f[i][j] = f[f[i][j - 1]][j - 1]\)
回到这道题:
暴力的做法即遍历区间 \([l,r]\) ,贪心的让每段的长度尽可能大
考虑用倍增思想优化:
定义 \(f[i][j]\) 表示:
以 \(i\) 为起点,分成 \(2 ^ j\) 个连续段后,所能到达的最远位置的下一个位置(其中每个段的和都不超过 \(K\))
那么不难得到: \(f[i][j] = f[f[i][j - 1]][j - 1]\) (\(f[i][0]\) 可通过二分前缀和得到
然后对于每个询问 \((L , R)\):
先判断区间 \([L,R]\) 是否存在 \(A_i\) 使得 \(A_i > K\)
这步我们维护一个权值数组的前缀和 \(O1\) 判断
即当 \(A_i <= K\) 时,\(sum[i] = sum[i - 1]\)
当 \(A_i > K\)时,\(sum[i] = sum[i - 1] + 1\)
当 \(sum[R] - sum[L - 1] > 0\) 则表示该区间存在 \(A_i > K\),直接输出 \(Chtholly\)
若 \(sum[R] - sum[L - 1] = 0\) 则从高位往低位枚举 \(j\):
如果 \(f[L][j] > R\) 则表示从 \(L\) 开始划分出 \(2^j\) 个连续段是 \(OK\) 的
但是 \(2^j\) 连续段可能太多了(题目要求划分的连续段个数最少
所以就继续往下枚举如果 \(f[L][j] < R\),则表示从 \(L\) 开始划分出 \(2^j\) 个连续段是不够的
那就先划分出 \(2^j\) 个连续段,然后再从 \(f[L][j]\) 的位置继续划分
即 \(ans += 1 << j\) ,\(L = f[L][j]\)
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int f[N][22];
int n , m , k , a[N] , sum[N];
long long pre[N];
signed main()
{
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; i ++)
{
cin >> a[i] , pre[i] = pre[i - 1] + a[i];
sum[i] = sum[i - 1] + (a[i] > k);
}
for(int j = 0 ; j <= 21 ; j ++) f[n + 1][j] = n + 1;
for(int j = 0 ; j <= 21 ; j ++)
{
for(int i = 1 ; i <= n ; i ++)
{
f[i][0] = upper_bound(pre + i , pre + 1 + n , k - a[i] + pre[i]) - pre;
if(!j) continue ;
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
while(m --)
{
int l , r , ans = 0;
cin >> l >> r;
if(sum[r] - sum[l - 1])
{
cout << "Chtholly\n";
continue ;
}
for(int j = 21 ; j >= 0 ; j --)
{
if(f[l][j] - 1 < r)
{
ans += 1 << j;
l = f[l][j];
}
}
cout << ans + 1 << '\n';
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的牛客练习赛14B 区间的连续段全部内容,希望文章能够帮你解决牛客练习赛14B 区间的连续段所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。