brz的雪糕

NC213248. brz的雪糕

描述

蒟蒻 $\text{brz}$ 买了 n 个雪糕进献给雪糕之王 $\text{lzy}$ ，但是他发现了一个难题……

雪糕之王 $\text{lzy}$ 吃雪糕是很挑剔的，每次他会选一个区间 [l,r]，从左到右依次吃掉雪糕，假如第 i 个吃掉的雪糕和上一个吃掉的类型相同，那么 $\text{lzy}$ 的愉悦值不会提升，否则愉悦值会 +1，特别的，吃第一个雪糕时愉悦值会 +1。

蒟蒻 $\text{brz}$ 脑补了一些 $\text{lzy}$ 会吃的雪糕区间，他想要知道这些区间能带给 $\text{lzy}$ 的愉悦值是否不小于 k。

输入描述

第一行两个整数 n,k,q，n,k 意义如上所述，q 表示蒟蒻  脑补的  可能会吃的雪糕区间。

第二行 n 个整数，第 i 个整数  表示第 i 个雪糕的类型。

下面 q 行每行两个整数 ，表示  可能会吃  这个雪糕区间。

。

输出描述

输出 q 行，第 i 行表示当  吃的雪糕区间为  时，他能获得的愉悦值是否不小于 k，如果是，输出`Yes`，否则输出`No`。

示例1

输入:

输出:

No
Yes

说明:

区间 [1,4] 能带来的愉悦值为 3，区间 [2,5] 能带来的愉悦值为 4。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang11) 解法, 执行用时: 866ms, 内存消耗: 22896K, 提交时间: 2020-11-06 19:52:34

#include<stdio.h>
int a[2000001],b[2000001];
int main(){
    int n,m,k,x,y,i,j;
    scanf("%d%d%d",&n,&k,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=i!=1?b[i-1]+(a[i]!=a[i-1]):0;
    }
    while(m--){
        scanf("%d %d",&i,&j);
        printf(b[j]-b[i]+1>=k?"Yes\n":"No\n");
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 1103ms, 内存消耗: 15176K, 提交时间: 2020-11-06 19:18:58

#include<bits/stdc++.h>
using namespace std;
int n,k,q,a,b,d[2222222];
int main(){
	scanf("%d%d%d",&n,&k,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&b);
		d[i]=d[i-1]+(a==b?0:1);
		a=b;
	}
	while(q--){
		scanf("%d%d",&a,&b);
		puts(d[b]-d[a]+1<k?"No":"Yes");
	}
	return 0;
}

上一题

下一题

详情