热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

NOIP提高组2011

题目描述丽江河边有n家很有特色的客栈,客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰(总共k种,用整数0~k-1表示),且每家客栈都设有一家咖啡店,每家咖啡店均有

题目描述

丽江河边有n 家很有特色的客栈,客栈按照其位置顺序从 1 到n 编号。每家客栈都按照某一种色调进行装饰(总共 k 种,用整数 0 ~ k-1 表示),且每家客栈都设有一家咖啡店,每家咖啡店均有各自的最低消费。

两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈,因此决定分别住在色调相同的两家客栈中。晚上,他们打算选择一家咖啡店喝咖啡,要求咖啡店位于两人住的两家客栈之间(包括他们住的客栈),且咖啡店的最低消费不超过 p 。

他们想知道总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过 p元的咖啡店小聚。

输入输出格式

输入格式:

输入文件hotel.in,共n+1 行。

第一行三个整数n ,k ,p,每两个整数之间用一个空格隔开,分别表示客栈的个数,色调的数目和能接受的最低消费的最高值;

接下来的n 行,第 i+1 行两个整数,之间用一个空格隔开,分别表示 i 号客栈的装饰色调和i 号客栈的咖啡店的最低消费。

输出格式:

输出文件名为hotel.out 。

输出只有一行,一个整数,表示可选的住宿方案的总数。

输入输出样例

输入样例#1:
5 2 3 
0 5 
1 3 
0 2 
1 4 
1 5 
输出样例#1:
3

说明

【输入输出样例说明】

技术分享

2 人要住同样色调的客栈,所有可选的住宿方案包括:住客栈①③,②④,②⑤,④⑤,但是若选择住4 、5 号客栈的话,4 、5 号客栈之间的咖啡店的最低消费是4 ,而两人能承受的最低消费是3 元,所以不满足要求。因此只有前 3 种方案可选。

【数据范围】

对于30% 的数据,有 n ≤100;

对于50% 的数据,有 n ≤1,000;

对于100%的数据,有 2 ≤n ≤200,000,0

#include


const int N=200004;
int n,k,p;

int hc[N];
int hp[N];
int numc[N];
int pos[N];

int main()
{
    int ans=0;
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",hc+i,hp+i);
        numc[hc[i]]++;
        if(hp[i]<=p)
        {
            for(int j=0;j<=k;j++)
            pos[j]=numc[j];
        }
        ans+=pos[hc[i]];
        if(pos[hc[i]]==numc[hc[i]])
        ans--;
    }
    printf("%d\n",ans);
    return 0;
}

NOIP提高组 2011


推荐阅读
  • 嵌入式开发环境搭建与文件传输指南
    本文详细介绍了如何为嵌入式应用开发搭建必要的软硬件环境,并提供了通过串口和网线两种方式将文件传输到开发板的具体步骤。适合Linux开发初学者参考。 ... [详细]
  • 本文旨在提供一套高效的面试方法,帮助企业在短时间内找到合适的产品经理。虽然观点较为直接,但其方法已被实践证明有效,尤其适用于初创公司和新项目的需求。 ... [详细]
  • 反向投影技术主要用于在大型输入图像中定位特定的小型模板图像。通过直方图对比,它能够识别出最匹配的区域或点,从而确定模板图像在输入图像中的位置。 ... [详细]
  • 本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数,并使用递推算法和大数处理技术来解决这一问题。 ... [详细]
  • 在使用STM32Cube进行定时器配置时,有时会遇到延时不准的问题。本文探讨了可能导致延时不准确的原因,并提供了解决方法和预防措施。 ... [详细]
  • 本文详细探讨了JavaScript中的作用域链和闭包机制,解释了它们的工作原理及其在实际编程中的应用。通过具体的代码示例,帮助读者更好地理解和掌握这些概念。 ... [详细]
  • Python 内存管理机制详解
    本文深入探讨了Python的内存管理机制,涵盖了垃圾回收、引用计数和内存池机制。通过具体示例和专业解释,帮助读者理解Python如何高效地管理和释放内存资源。 ... [详细]
  • C#设计模式学习笔记:观察者模式解析
    本文将探讨观察者模式的基本概念、应用场景及其在C#中的实现方法。通过借鉴《Head First Design Patterns》和维基百科等资源,详细介绍该模式的工作原理,并提供具体代码示例。 ... [详细]
  • 利用Selenium与ChromeDriver实现豆瓣网页全屏截图
    本文介绍了一种使用Selenium和ChromeDriver结合Python代码,轻松实现对豆瓣网站进行完整页面截图的方法。该方法不仅简单易行,而且解决了新版Selenium不再支持PhantomJS的问题。 ... [详细]
  • 解决TensorFlow CPU版本安装中的依赖问题
    本文记录了在安装CPU版本的TensorFlow过程中遇到的依赖问题及解决方案,特别是numpy版本不匹配和动态链接库(DLL)错误。通过详细的步骤说明和专业建议,帮助读者顺利安装并使用TensorFlow。 ... [详细]
  • 本文深入探讨了线性代数中向量的线性关系,包括线性相关性和极大线性无关组的概念。通过分析线性方程组和向量组的秩,帮助读者理解这些概念在实际问题中的应用。 ... [详细]
  • 本文介绍如何在 C++ 中使用链表结构存储和管理数据。通过具体示例,展示了静态链表的基本操作,包括节点的创建、链接及遍历。 ... [详细]
  • 探索新一代API文档工具,告别Swagger的繁琐
    对于后端开发者而言,编写和维护API文档既繁琐又不可或缺。本文将介绍一款全新的API文档工具,帮助团队更高效地协作,简化API文档生成流程。 ... [详细]
  • 本文探讨了在构建应用程序时,如何对不同类型的数据进行结构化设计。主要分为三类:全局配置、用户个人设置和用户关系链。每种类型的数据都有其独特的用途和应用场景,合理规划这些数据结构有助于提升用户体验和系统的可维护性。 ... [详细]
  • Linux中的yum安装软件
    yum俗称大黄狗作用:解决安装软件包的依赖关系当安装依赖关系的软件包时,会将依赖的软件包一起安装。本地yum:需要yum源,光驱挂载。yum源:(刚开始查看yum源中的内容就是上图 ... [详细]
author-avatar
君哥哥
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有