oi提高2012常州夏令营组6task

1、青少年联赛(NOIP)复赛模拟提高组 Day1（请选手务必仔细阅读本页内容）3.5 小时，400 分一、题目概览二、提交源程序文件名三、编译命令（不包含任何优化开关）四、运行内存限制注意事项：1.2.3.文件名（程序名和输入输出文件名）必须使用。C/C+中函数 main()的返回值类型必须是，程序正常结束时的返回值必须是 0。评测时采用的机器配置为：CPU P4 1.9GHz，内存 1G，上述时限以此配置为准。在自测时可根据具体配置调整时限。小写运行内存上限256M256M256M对于 Pascal 语言fpc fancy.pasfpc hsfpc quarrel.pas对于 C 语言gcc

2、fancy.c o fancy.exegcc hw.c o hw.exegcc quarrel.c o quarrel.exe对于 C+语言g+ fancy.cpp o fancy.exeg+ hw.cpp o hw.exeg+ quarrel.cpp o quarrel.exe对于 Pascal 语言fancy.pashsquarrel.pas对于 C 语言fancy.chw.cquarrel.c对于 C+语言fancy.cpphw.cppquarrel.cpp中文题目名称第一饭堂第二饭堂第三饭堂英文题目名称fancyhwQuarrel可执行文件名fancy.exehw.exeQuarrel

3、.exe输入文件名fancy.inhw.inQuarrel.in输出文件名fancy.outhw.outQuarrel.out每个测试点时限1 秒1 秒1 秒测试点数目101010每个测试点分值101010比较方式全文比较全文比较全文比较题目类型传统传统传统1. 第一饭堂(fancy.pas/p)【问题描述】每天中午，美丽的中山纪念中学都会上演一场华丽的大竞走。大量人流短时间涌进第一饭堂，饭堂班长表示不蛋定了，他必须合理安排饭堂饭菜的价格，来让有愉快的心情就餐。已知第一饭堂饭菜的价格有 N 位（坑爹吧！），如果一个价格有不小于 K 个数位完全相同，那么这个数字就被认为是漂亮的，否则这个数字被认

4、为是不漂亮的。饭堂班长想改变其中一个饭菜的价格，改变价格中的一位需要花费一些钱，所需费用等于改变量之差的绝对值。饭堂班长希望你能把这个价格变漂亮，求出最小费用，同时给出字典序最小的一个方案。【输入】第 1 行：两个用空格隔开的数字 N 和 K（2 n 104, 2 k n）。第 2 行：一个 N 位的数字表示原来的价格。【输出】第 1 行：最小费用。第 2 行：所求方案。【输入输出样例】【数据范围】对于 100%的数据，2N10000，2kn。fancy.infancy.out6 589819648881883 2533053310 6000111223300000022232.第二饭堂(hs

5、/p)【问题描述】由于一饭班长表示各种鸭梨，美丽的决定历史性地启用第二饭堂。而部分觉得，二饭依山傍水，环境优美，未免有不和谐的事情（你懂的）发生，决定到二饭巡视用餐时的就座情况。为了应付这一情况，决定“布阵”。方便起见，已经把座位情况抽象成一个长度为 n 的仅含数字及字母的字符串，他们想请你帮忙算算这个字符串的和谐程度。已知一个字符串被称为 k-回文串的充要条件是它自身是回文串，并且它长为 n/2（下取整）的前缀和后缀是（k-1）-回文串。根据定义，任意字符串（包括空串）都是回文串。一个字符串的回文度数就是这个字符串的 k 的最大值。而对于一个给定的字符串，它的和谐程度就是其所有前缀的回文度数

6、之和。你的任务就是算出这个和谐程度具体是多少。0-【输入】一行一个仅包含数字和字母的字符串。【输出】一行一个整数表示这个字符串的和谐高度。【输入输出样例】【数据规模】对于 30%的数据字符串长度不超过 1000对于 70%的数据字符串长度不超过 100000对于 100%的数据字符串长度不超过 5000000hw.inhw.outabacaba63.第三饭堂 (Quarrel.pas/p)【问题描述】由于们发现第二饭堂各种和谐，所以他们决定转战高居山顶的第三饭堂。而在第三饭堂用完餐的小 A 和小 B，要到二饭旁的水果店买水果。重要的是，在途中遇到这种事是他们所不愿看见的。已知从三饭到二饭有 n

7、 个路口，从 1n。小 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】们的行走路线。【输入输出样例 2】【输入输出样例 3】Quarrel.inQuarrel.out7 61 22 77 62 33 46 7 2 1 5 1Quarrel