NOIP2011提高组-第一天-Day1试题.docxVIP

NOIP2011提高组-第一天-Day1试题 全国信息学奥林匹克联赛（NOIP201 全国信息学奥林匹克联赛（NOIP2011）复赛 提高组 day1 第 第 PAGE 6 页 共 6 页 全国信息学奥林匹克联赛（NOIP2011）复赛 提高组 day1 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 铺地毯 选择客栈 mayan 游戏 英文题目与子目录名 carpet hotel mayan 可执行文件名 carpet hotel mayan 输入文件名 carpet.in hotel.in mayan.in 输出文件名 carpet.out hotel.out mayan.out 每个测试点时限 1 秒 1 秒 3 秒 测试点数目 10 10 10 每个测试点分值 10 10 10 附加样例文件 有 有 有 结果比较方式 全文比较（过滤行末空格及文末回车） 题目类型 传统 传统 传统 二．提交源程序文件名 对于 C++语言 carpet.cpp hotel.cpp mayan.cpp 对于 C 语言 carpet.c hotel.c mayan.c 对于 pascal 语言 carpet.pas hotel. pas mayan. pas 三．编译命令（不包含任何优化开关） 对于 C++语言 g++ -o carpet carpet.cpp -lm g++ -o hotel hotel.cpp -lm g++ -o mayan mayan.cpp -lm 对于 C 语言 gcc -o carpet carpet.c -lm gcc -o hotel hotel.c -lm gcc -o mayan mayan.c -lm 对于 pascal 语言 fpc carpet.pas fpc hotel.pas fpc mayan.pas 四．运行内存限制 内存上限 128M 128M 128M 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为：CPU P4 3.0GHz，内存 1G，上述时限以此配置为准。 4、特别提醒：评测在 NOI Linux 下进行。 如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2， 2）的最上面一张地毯是 3 号地毯。 y x 【输入输出样例 2】 carpet.in carpet.out 3 1 0 2 3 0 2 3 3 2 1 3 3 4 5 -1 【输入输出样例说明】 如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5） 没有被地毯覆盖，所以输出-1。 【数据范围】 对于 30%的数据，有 n≤2； 对于 50%的数据，0≤a, b, g, k≤100； 对于 100%的数据，有 0≤n≤10,000，0≤a, b, g, k≤100,000。 【问题描述】 2．选择客栈 (hotel.cpp/c/pas) 丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照 某一种色调进行装饰（总共 k 种，用整数 0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每 家咖啡店均有各自的最低消费。 两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定 分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于 两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p。 他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。 【输入】 输入文件 hotel.in，共 n+1 行。 第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色 调的数目和能接受的最低消费的最高值； 接下来的 n 行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色 调和 i 号客栈的咖啡店的最低消费。 【输出】 输出文件名为 hotel.out。 输出只有一行，一个整数，表示可选的住宿方案的总数。 【输入输出样例 1】 hotel.in hotel.out 5 2 3 0 5 1 3 0 2 1 4 1 5 3 【输入输出样例说明】 客栈编号 ① ② ③ ④ ⑤ 色调 0 1 0 1 1 最低消费 5 3 2 4 5 2 人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤， 但是若选择住 4、5 号客栈的话，4、5 号客栈之间的咖啡店的最低消费是 4，而两人能承受 的最低消费是 3 元，所以不