网站建设新报价图片欣赏,sae搭建wordpress,wordpress可以建网站吗,西地那非片的功能主治和副作用题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/82/B 来源#xff1a;牛客网
给你一个长为n的序列a和一个常数k
有m次询问#xff0c;每次查询一个区间[l,r]内所有数最少分成多少个连续段#xff0c;使得每段的和都 k
如果这一次查询无解…题干
链接https://ac.nowcoder.com/acm/contest/82/B 来源牛客网
给你一个长为n的序列a和一个常数k
有m次询问每次查询一个区间[l,r]内所有数最少分成多少个连续段使得每段的和都 k
如果这一次查询无解输出Chtholly
输入描述:
第一行三个数n,m,k
第二行n个数表示这个序列a
之后m行每行给出两个数l r表示一次询问
输出描述:
输出m行每行一个整数表示答案
示例1
输入
复制
5 5 7
2 3 2 3 4
3 3
4 4
5 5
1 5
2 4
输出
复制
1
1
1
2
2
备注:
对于100%的数据1 n , m 1000000 , 1 ai , k 1000000000
解题报告 首先发现可以贪心这样是O( nm )的 由于k固定考虑数组中每个位置i向最大的j1使得a[i..j]的和k连边。这个连边的结构是个森林每次查询即查询树的一条链可以倍增维护。O( nlogn mlogn )
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 1e6 5;
int n,m;
ll K,a[MAX],sum[MAX];
int f[MAX][22];
int main()
{cinnmK;for(int i 1; in; i) scanf(%lld,ai),sum[i] sum[i-1] a[i];for(int i 1; in; i) {int pos upper_bound(sumi,sumn1,sum[i-1]K) - sum;f[i][0] pos; }for(int j 0 ; j21; j) f[n1][j] n1;for(int j 1; j21; j) {for(int i 1; in; i)f[i][j] f[f[i][j-1]][j-1];}while(m--) {int l,r;scanf(%d%d,l,r);int ans 0;for(int j 21; j0; j--) {if(f[l][j] r) ans (1j),l f[l][j];}if(f[l][0] r) {printf(%d\n,ans1);}else printf(Chtholly\n);}return 0 ;
}
