[NOIP2011真题]选择客栈[通俗易懂]

[NOIP2011真题]选择客栈[通俗易懂]题目背景NOIP2011提高组DAY1试题。题目描述丽江河边有n家很有特色的客栈,客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰(总共k种,用整数0~k-1表示),且每家客栈都设有一家咖啡店,每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈,因此决定分别住在色调相同的两家客栈中。晚上,他们打算选择一

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

题目背景
NOIP2011提高组 DAY1 试题。

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

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

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

输入格式
共 n+1 行。

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

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

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

样例数据
输入
5 2 3
0 5
1 3
0 2
1 4
1 5
输出
3

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

【数据范围】
对于 30% 的数据,有 n100
对于 50% 的数据,有 n1,000
对于 100% 的数据,有 2n200,000 0<k50 0p100 0 最低消费 100

分析:按照题目要求的进行模拟,每次选择两个进行判断,若满足以下条件:
1.两个客栈颜色相同
2.两个客栈中间(包含两个客栈)中存在一家咖啡店最低消费小于等于p的即算作一个满足条件的解。

思路1:
枚举两个客栈,判断颜色是否相同,并顺序枚举求两个客栈的最小值,看是否小于等于 p 。
复杂度O( N3 ) 期望得分 30-40 。

思路2:
对于求两个客栈的最小值问题,为经典的RMQ问题,可以用线段树维护一段区间的最小值。
复杂度O( N2 logN) 期望得分 50。

思路3:
可以用ST算法O(1)时间求出两个区间的最小值 复杂度O(NlogN+ N2 )。
期望得分 50-60 。

思路4:
对于每一个客栈,我们考虑和当前点前面的客栈进行配对。预处理出Pre表示i点(包含i点)前面第一个<=p的客栈。对于每一个颜色,求出sum表示前i个点有多少个点的颜色等于当前枚举的颜色。依次枚举每一个客栈,若当前客栈最低消费<=p,当前客栈可以和前面任意一个客栈进行匹配,并且pre一定等于i,所以答案可以累加sum[pre]-1;对于当前客栈最低消费>p,则当前客栈只能和pre以及之前的客栈进行匹配,故答案可以累加sum[pre]。 复杂度O(NK) 期望得分 100。

以上是标答,我们来模拟一下(结合代码):
发现第一个满足消费要求的点,那么前面记录的color全部进入sum,这样,只要这个点后面有color相同的点,就多了sum种住宿方案(更新ans),此时,要将前面的color全部清零。
这里写图片描述
发现第二个满足消费要求的点,那么在两个点之间的color全部进入sum(记作sum(新)),这样,只要这个点后面有color相同的点,那么就多了sum(新)种住宿方案(更新ans),此时color再次清零,之后同理。
这里写图片描述
刚开始以为是选了客栈有多少种喝咖啡的方案……错的很惨。

代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<iomanip>
#include<queue>
#include<set>
using namespace std;

int getint()
{
    int f=1,sum=0;
    char ch;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-')
    {
        f=-1;
        ch=getchar();
    }
    for(;ch>='0'&&ch<='9';ch=getchar())
        sum=(sum<<3)+(sum<<1)+ch-48;
    return sum*f;
}

const int maxn=2e5+10; 
int n,p,k,x,y,sum[maxn],color[maxn],ans;

int main()
{
    freopen("lx.in","r",stdin);
    freopen("lx.out","w",stdout);

    n=getint();k=getint();p=getint();
    for(int i=1;i<=n;++i)
    {
        x=getint();y=getint();
        color[x]++;
        if(y<=p)
        {
            for(int j=0;j<=k-1;++j)
            {
                sum[j]+=color[j];
                color[j]=0;
            }

            ans-=1;
        }
        ans+=sum[x];
    }

    cout<<ans<<endl;
    return 0;
}

本题结。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/190028.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 异美旅游

    异美旅游

  • Navicat15的MAC的万能激活码_在线激活「建议收藏」

    (Navicat15的MAC的万能激活码)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • tomcat文件上传大小限制_tomcat调整内存大小

    tomcat文件上传大小限制_tomcat调整内存大小1.Get方法长度限制HttpGet方法提交的数据大小长度并没有限制,HTTP协议规范没有对URL长度进行限制。这个限制是特定的浏览器及服务器对它的限制。如:IE对URL长度的限制是2083字节(2K+35)。下面就是对各种浏览器和服务器的最大处理能力做一些说明.MicrosoftInternetExplorer(Browser)IE浏览器对URL的最大限制为2083个字符,如果超过这个数…

  • 用Python做一个“以图搜番“的应用程序,再也不用愁动漫图片的出处了!

    用Python做一个“以图搜番“的应用程序,再也不用愁动漫图片的出处了!文章目录前言PyQt5界面设计使用QtDesigner绘制界面视频部件插入小技巧解码器下载功能实现trace.moeAPI介绍与视频使用Nuitka打包成exe文件前言喜欢看动漫的朋友们大概都能体会到一个难受的事情,就是在论坛或者群聊里面看到一张动漫截图,很想知道它的出处,但百度搜了一圈却也没有一个可靠结果,就很郁闷。今天就来带大家用Python做一个简单的“以图搜番”小应用。应用本身的实现不是很难的事情,其实就是调用别人的API接口来实现,主要目的还是通过这个案例来学习以下内容:学习如何用Py

  • 正则表达式全解析+常用示例「建议收藏」

    正则表达式全解析+常用示例「建议收藏」在开始写这篇文章之前,我的心里还是纠结的。我在问自己要不要写这篇东西,关于相似的内容网上多如牛毛,而且还不乏珍品,况且,就算我写了也不一定能写的好。但是现在你既然看到了,那说明我还是写了出来。就算是对自己学习的一个总结吧!同时也把常见的常用的正则表达式给收集整理出来,以便用到的时候不用满世界的找。关于正则表达式一直都是个让很多程序员都觉得很郁闷的一个东西,我觉得创造正则表达式的那个家伙简直就是

  • 博客园学习的好地方

    VisualStudio2015Update1安装失败当你安装VisualStudio2015Update1时,安装程序失败并记录“BITS作业失败”的错误消息Visual

    2021年12月21日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号