东南大学第八届程序设计大赛决赛试题及参考程序.pdf

ProblemProblem A A 1 1 快速打字快速打字 Time Limit 1 Sec Memory Limit 128 MB Submit 121 Solved 26 Submit Status Web Board DescriptionDescription 东南大学男生多 女生少 是一条亘古不变的真理了 HYF 喜欢上一个女生 他需要和很多男生竞 争 为了能让自己更占优势 他苦练手机发短信速度 已知手机发短信有如下规则 需要用到九个键 2 到 9 分别对应 2 abc 3 def 4 ghi 5 jkl 6 mno 7 pqrs 8 tuv 9 wxyz 如果要写出 b 则需要按两下 2 此时手机并未真正写出 b 因为如果再按一下 2 会写出 c 如果 此时按一次 3 也可以写出 b 并且下次的第一个键是 3 如果按两下 2 等待一秒 同样可以写出 b 但如果是某个键的最后一个字母 如按 3 下 2 不需要等待即可出现 c 按 4 下 7 不需要等待也可 以出现 s 按一个键需要一秒 HYF 只要能用最短的时间写出来 他就能追到喜欢的女生 对于只含有小写字母的字符串 请大家 帮忙算出需要的最短时间 InputInput 长度不超过 1000000 的字符串 只含有小写字母 OutputOutput 一个整数 表示需要打印出字符串的最短时间 SampleSample InputInput ba ca fdea SampleSample OutputOutput 4 4 8 HINTHINT ProblemProblem B B 2 2 走楼梯走楼梯 Time Limit 1 Sec Memory Limit 128 MB Submit 102 Solved 12 Submit Status Web Board DescriptionDescription YDK 爬楼梯 每次可以爬一层 也可以爬两层 但如果上次爬了两层 下次要休息 不能爬两层 有一些层 必须要走到 请聪明的你求出一共有多少种爬楼梯的方法 InputInput 输入包含多个测试用例 一直处理到结束 每个测试用例第一行有两个正整数 N 1 N 1024 M 1 M N 楼梯层数和必须走的楼梯层个数 第二行有 M 个正整数 必须走的楼梯层 OutputOutput 一个正整数 输出爬楼梯的方法 可能很大 模除 2012 即可 SampleSample InputInput 3 2 2 2 5 2 1 4 SampleSample OutputOutput 2 3 HINTHINT ProblemProblem C C 3 3 建房建房 Time Limit 1 Sec Memory Limit 128 MB Submit 37 Solved 2 Submit Status Web Board DescriptionDescription 题目描述 hj 家在农村 他现在希望建一栋房子 政府给了他面积为 S 的区域建房 1 S 60 他有 C 元 建造费用 1 C 5000 他在建房时需遵循以下原则 1 不能超出规定面积以外建造 即第一层的面积不能超过 S 2 每一层的面积不能大于它下面一层 即如果第 i 层面积是 x 那么第 i 1 层面积不能超过 x 3 最多建造 n 层 1 n 10 每一层的建造成本不同 第 i 层的建造成本 w i 元 每平米 1 i n 1 w i 100 由于以后考虑到可能面临的拆迁 他希望拆迁时获得尽量多的补贴 当地政府对拆迁补助有如下规定 1 计算每一层的面积时面积都向下取整 即取出小数部分 2 第 i 层的补助为 p i 元 每平米 1 i n 1 p i 100 现在请求出 hj 最多能获得多少补助 InputInput 包含多个测试用例 对于每个测试用例 第 1 行 一个整数 n 表示最多建造层数 第 2 行 两个整数 C S 分别表示总共建造费用和建房面积 第 3 行 n 个整数 表示每一层每平米的建造成本 第 4 行 n 个整数 表示每一层每平米的补助 输入一个 0 表示输入结束 不做处理 OutputOutput 对于每个测试用例 输出一行 包含一个整数 表示最多补助数 SampleSample InputInput 1 10 3 4 5 2 100 10 5 8 10 12 SampleSample OutputOutput 10 172 HINTHINT ProblemProblem D D 4 4 丢沙包丢沙包 Time Limit 1 Sec Memory Limit 128 MB Submit 37 Solved 19 Submit Status Web Board DescriptionDescription 有一天 Acmers 厌烦了做题 想起来小时候做过的丢沙包游戏 于是 N 个人围成一圈 每个人都不 希望自己两边站着个字比自己高很多的人 这是要发挥大家的长处 设计一种最优的方法 使得相邻 两个人身高差距最大的最小 InputInput 第一行为一个正整数 T 有 T 个测试用例 接下来有 T 行 每一行第一个正整数 N 3 N 100000 第 2 到 N 1 个正整数表示 N 个人的身高 身高范围为 1 到 10000 OutputOutput 设计最优方法 输出相邻两人身高差距最大的最小值 SampleSample InputInput 2 3 1 2 3 5 1 9 5 3 7 SampleSample OutputOutput 2 4 HINTHINT ProblemProblem E E 5 5 放广告放广告 Time Limit 1 Sec Memory Limit 128 MB Submit 29 Solved 3 Submit Status Web Board DescriptionDescription ACMer 每天做题腻了 有一天做了一个网站 网站上有 N 个广告位 由于网站很火 有 M 家企业想 要在广告位上放置广告 每家企业只能在一个广告位上放一个广告 每个广告位有一个编号 n1 InputInput 第一行两个正整数 N 1 N 10 M 1 M 2000 第二行有 N 个正整数 第 k 个正整数表示第 k 个广告位的价值 同时该广告位的编号为 k 第三行有 M 个正整数 第 k 个正整数表示第 k 个广告的价值 同时该广告的编号为 k OutputOutput 一个正整数 放置广告得到的最大价值 SampleSample InputInput 1 1 2 3 SampleSample OutputOutput 7 HINTHINT ProblemProblem F F 6 6 文件共享文件共享 Time Limit 1 Sec Memory Limit 128 MB Submit 5 Solved 2 Submit Status Web Board DescriptionDescription 有一个局域网络 网络中共有 n 各节点 1 n 100 编号从 1 到 n 其中一部分是服务器 一 部分是客户端 这 n 个节点的网络中存在 m 条双向的通信线路 保证它们是连通的 每条线路的传 输速率不同 假设某条线路的传输速率是 a 那就表示这条线路每秒能传输大小为 a 的信息 现在所 有服务器中有一个大小为 S 的文件 从 0 时刻开始 服务器要通过这些线路把文件共享到所有节点 共享文件要遵循如下规则 1 只有相邻节点才能传输文件 传输速率是该线路的传输速率 2 任意一个节点都能同时向相邻的所有节点发送文件 速率分别为每条传输线路的速率 3 任意节点都能从它相邻的所有节点接收文件 传输速率是所有向它传输文件的传输线路速率之和 4 服务器能不断地向其他节点传输文件 而客户端在接收完文件后 会在线 t 时间向它相邻的节点传 输文件 然后就不再想其他节点传输文件 先在请求出上述描述中最小的 t 使得最后局域网中所有节点都能接收完整的文件 结果保留 3 位小 数 InputInput 包含多个测试用例 对于每个测试用例 第 1 行 一个整数 n 表示节点数量 1 n 100 第 2 行 一个整数 m 表示通信链路数量 n 1 m n n 1 2 第 3 行到 m 2 行 每行 3 个整数 a b c 表示节点 a 和 b 之间有一条传输速率为 c 的线路 输入保证网 络是连通的且没有重边 1 c 1000 第 m 3 行 一个整数 s 表示要共享的文件大小 1 s 100000 第 m 4 行 一个整数 d 表示服务器的数量 接下来有 d 个正整数 表示服务器节点的编号 输入一个 0 表示输入结束 不做处理 OutputOutput 一个实数 t 表示最小的时间 t 使得文件能够在传输到网络中每个节点 结果保留 3 位小数 SampleSample InputInput 5 4 1 2 1 2 3 2 3 4 2 4 5 1 10 2 1 5 4 3 1 2 1 2 3 1 3 4 1 10 2 1 4 SampleSample OutputOutput 2 500 0 000 HINTHINT ProblemProblem G G 7 7 称坏了称坏了 Time Limit 1 Sec Memory Limit 128 MB Submit 58 Solved 8 Submit Status Web Board DescriptionDescription Long 有一台破称 很久没有使用过 不知道有没有坏 为了测试 他找来 N 个重量不一样的球 做 M 次操作 每次随机取两个球 放在称上 给出两个球的重量大小关系 保证所有的球都是不一样重 的 InputInput 第一行有两个正整数 N 1 N 1000 M 1 M 1000000 分别表示球的个数 操作次数 接下来有 M 行 每一行两个正整数 u v 1 u v N 表示球 u 重量大于球 v OutputOutput 一个正整数 表示最少到第多少次操作时 可以确定称是坏的 如果不能确定称是坏的 则输出 1 SampleSample InputInput 5 5 1 2 2 3 3 4 4 5 1 5 5 5 1 2 2 3 3 1 4 5 5 4 SampleSample OutputOutput 1 3 HINTHINT include include using namespace std bool samegroup char a char b if a b return true if a a switch c case 1 return 1 case 2 return 2 case 0 return 3 else switch a case p case t case w return 1 case q case u case x return 2 case r case v case y return 3 case s case z return 4 bool islast char a if a c a f a i a l a o a s a v a z return true else return false int thetime string s int time 0 len len s length int i for i 0 i len 1 i if samegroup s i s i 1 if samegroup s i s i 1 islast s i time number s i time number s i return time int main string s while getline cin s if s 0 0 break cout thetime s endl system pause return 0 include using namespace std void sort int