当前位置:首页 >> 学科竞赛 >>

20121028prob


全国信息学奥林匹克联赛(NOIP2011)提高组复赛模拟 Day1

广东中山纪念中学

全国青少年奥林匹克联赛(NOIP)复赛模拟 提高组 Day1
(请选手务必仔细阅读本页内容)
3.5 小时,400 分
一、题目概览
中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试点时

限 测试点数目 每个测试点分值 比较方式 题目类型 二、提交源程序文件名 对于 Pascal 语言 对于 C 语言 对于 C++语言 对于 Pascal 语言 对于 C 语言 对于 C++语言 四、运行内存限制 运行内存上限 256M 256M 256M fancy.pas fancy.c fancy.cpp fpc fancy.pas gcc fancy.c –o fancy.exe g++ fancy.cpp –o fancy.exe hw.pas hw.c hw.cpp fpc hw.pas gcc hw.c –o hw.exe g++ hw.cpp –o hw.exe quarrel.pas quarrel.c quarrel.cpp fpc quarrel.pas gcc quarrel.c –o quarrel.exe g++ quarrel.cpp –o quarrel.exe 第一饭堂 fancy fancy.exe fancy.in fancy.out 1秒 10 10 全文比较 传统 第二饭堂 hw hw.exe hw.in hw.out 1秒 10 10 全文比较 传统 第三饭堂 Quarrel Quarrel.exe Quarrel.in Quarrel.out 1秒 10 10 全文比较 传统

三、编译命令(不包含任何优化开关)

注意事项: 1. 文件名(程序名和输入输出文件名)必须使用小写。 2. C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3. 全国统一评测时采用的机器配置为:CPU P4 1.9GHz,内存 1G,上述时限以此配置为准。 各省在自测时可根据具体配置调整时限。

全国信息学奥林匹克联赛(NOIP2011)提高组复赛模拟 Day1

广东中山纪念中学

1. 第一饭堂 (fancy.pas/c/cpp)
【问题描述】 每天中午,美丽的中山纪念中学都会上演一场华丽的千人大竞走。 大量人流短时间涌进第一饭堂, 饭堂班长表示不蛋定了, 他必须合理安排饭堂饭菜的价 格,来让同学们有愉快的心情就餐。 已知第一饭堂饭菜的价格有 N 位 (坑爹吧!, )如果一个价格有不小于 K 个数位完全相同, 那么这个数字就被认为是漂亮的, 否则这个数字被认为是不漂亮的。 饭堂班长想改变其中一 个饭菜的价格,改变价格中的一位需要花费一些钱,所需费用等于改变量之差的绝对值。 饭堂班长希望你能把这个价格变漂亮, 求出最小费用, 同时给出字典序最小的一个方案。 【输入】 4 第 1 行:两个用空格隔开的数字 N 和 K(2?≤?n?≤?10 ,?2?≤?k?≤?n) 。 第 2 行:一个 N 位的数字表示原来的价格。 【输出】 第 1 行:最小费用。 第 2 行:所求方案。 【输入输出样例】 fancy.in 6 5 898196 3 2 533 10 6 0001112223 fancy.out 4 888188 0 533 3 0000002223

【数据范围】 对于 100%的数据,2≤N≤10000,2≤k≤n。

全国信息学奥林匹克联赛(NOIP2011)提高组复赛模拟 Day1

广东中山纪念中学

2.第二饭堂 (hw.pas/c/cpp)
【问题描述】 由于一饭班长表示各种鸭梨,美丽的纪中决定历史性地启用第二饭堂。 而部分领导觉得,二饭依山傍水,环境优美,未免有不和谐的事情(你懂的)发生,决 定到二饭巡视同学们用餐时的就座情况。 为了应付这一情况,同学们决定联合起来“布阵” 。 方便起见, 同学们已经把座位情况抽象成一个长度为 n 的仅含数字及字母的字符串, 他 们想请你帮忙算算这个字符串的和谐程度。 已知一个字符串被称为 k-回文串的充要条件是它自身是回文串,并且它长为? n/2? (下取整)的前缀和后缀是(k-1)-回文串。根据定义,任意字符串(包括空串)都是 0回文串。 一个字符串的回文度数就是这个字符串的 k 的最大值。 而对于一个给定的字符串,它的和谐程度就是其所有前缀的回文度数之和。 你的任务就是算出这个和谐程度具体是多少。 【输入】 一行一个仅包含数字和字母的字符串。 【输出】 一行一个整数表示这个字符串的和谐高度。 【输入输出样例】 hw.in abacaba hw.out 6

【数据规模】 对于 30%的数据字符串长度不超过 1000 对于 70%的数据字符串长度不超过 100000 对于 100%的数据字符串长度不超过 5000000

全国信息学奥林匹克联赛(NOIP2011)提高组复赛模拟 Day1

广东中山纪念中学

3.第三饭堂 (Quarrel.pas/c/cpp)
【问题描述】 由于领导们发现第二饭堂各种和谐,所以他们决定转战高居山顶的第三饭堂。 而在第三饭堂用完餐的小 A 和小 B,要到二饭旁的水果店买水果。重要的是,在途中遇 到领导这种事是他们所不愿看见的。 已知从三饭到二饭有 n 个路口,从 1~n 编号。小 A 和小 B 在 1 号路口,想到 n 号路口买 水果;领导们在 n 号路口,想到 1 号路口去巡视。每个时刻,小 A 和小 B 总是一起行动,领 导们也都一起行动,双方都会从当前所在路口,走到某个与之相邻的路口,不会原地停留。 双方可以同时在一条路上往不同方向走,但某个时刻双方不可以同时停留在某个路口中。 为了节省时间,请你告诉他们,最早在什么时刻,他们能同时到达目的地,并告诉他们 具体路线是什么? 【输入】 第一行包含两个整数 n,m (2 ≤ n ≤ 500,1 ≤ m ≤ 10000) 表示一共有n 个路口, m 条马路。 接下来m 行每行包含两个整数 x,y,表示x 路口和y 路口有马路相连。 【输出】 第一行输出一个整数 k,表示他们最早到达目的地的时刻。 第二行依次输出 k 个整数,表示小 A 和小 B 的行走路线。 第三行依次输出 k 个整数,表示领导们的行走路线。 若无解,则输出-1。 【输入输出样例 1】 Quarrel.in 2 1 1 2 【输入输出样例 2】 Quarrel.in 7 1 2 7 2 3 5 2 7 6 3 4 Quarrel.out -1 Quarrel.out 1 1 2 2 1

【输入输出样例 3】 Quarrel.in 7 1 2 7 2 3 1 6 2 7 6 3 4 5 Quarrel.out 6 1 2 3 4 3 2 7 7 6 7 2 1 5 1

全国信息学奥林匹克联赛(NOIP2011)提高组复赛模拟 Day1

广东中山纪念中学

【数据规模】 对于 40%的数据,n ≤ 100; 对于 100%的数据,2 ≤ n ≤ 500,1 ≤ m ≤ 10000。


相关文章:
更多相关标签: