NOIP2012模拟试题(一).pdf

全国信息学奥林匹克联赛 NOIp2011 复赛 提高组提高组提高组提高组 请选手务必仔细阅读本页内容请选手务必仔细阅读本页内容请选手务必仔细阅读本页内容请选手务必仔细阅读本页内容 一一一一 题目概况题目概况题目概况题目概况 中文题目名称 萌战投票 的算术 超能力通道 英文题目与子目录名 vote kiruno esp 可执行文件名 vote kiruno esp 输入文件名 vote in kiruno in esp in 输出文件名 vote out kiruno out esp out 每个测试点时限 1秒 1秒 1秒 测试点数目 10 10 10 每个测试点分值 10 10 10 附加样例文件 有 有 有 结果比较方式 全文比较 过滤行末空格及文末回车 题目类型 传统 传统 传统 二二二二 提交源程序文件名提交源程序文件名提交源程序文件名提交源程序文件名 对于Pascal语言 vote pas kiruno pas esp pas 对于C语言 vote c kiruno c esp c 对于C 语言 vote cpp kiruno cpp esp cpp 三三三三 编译命令编译命令编译命令编译命令 不包含任何优化开关不包含任何优化开关不包含任何优化开关不包含任何优化开关 对于Pascal语言 fpc vote pas fpc kiruno pas fpc esp pas 对于C语言 gcc o vote c lm gcc o kiruno c lm gcc o esp c lm 对于C 语言 g o vote cpp lm g o kiruno cpp lm g o esp cpp lm 四四四四 运行内存限制运行内存限制运行内存限制运行内存限制 内存上限 128M 128M 128M 注意事项注意事项注意事项注意事项 1 文件名 程序名和输入输出文件名 必须使用英文小写 2 C C 中函数main 的返回值类型必须是int 程序正常结束时的返回值必须是0 3 全国统一评测时采用的机器配置为 CPU Pentium E2140 1 6GHz 内存2G 上述时限以此配置为准 各省在自测时可根据具体配置调整时限 一一一一 萌战投票萌战投票萌战投票萌战投票 vote pas c cpp 题目描述题目描述题目描述题目描述 动画最萌战争 是由日本论坛2ch自2002年开始发起的一项投票活动 网民可以为自 己喜爱的本年度动画女性角色投票 通过多轮竞赛 选出最萌战争的 萌王 竞赛包括预 选赛 分组淘汰赛 16进8 8进4淘汰赛 半决赛 决赛几个环节 现在 我们考虑一下预 选赛中某一组的情况 在比赛开始之前 参战N 3 N 60 名动画角色的信息都会以形式如 角色名 动画名 称 不含引号 且长度不超过30的字符串给出 角色名与动画名称中只包含大写英文字母 输入数据保证各角色不会重名 之后 所有投票者的选票将一次性全部给出 选票片段如下例所示 Ganbare Mio KON SORAAAAAA 其中 尖括号 内的内容 是被投票的动画角色 大小写不敏感 可能会出现小 写字母 若尖括号 中的内容是参战的N名动画角色之一 则每出现一次 就给对应 的角色加上一票 否则 该票算作无效 尖括号之外的内容 是为角色 应援 的 萌文 计票时不会计算在内 保证每行最多只会出现一组尖括号 输入保证萌文中不会出现 字符 现在给你所有参战角色的信息和M 5 M 200000 行选票 请你按得票从高到低的顺 序 依次输出各角色的信息 如果多人得票相同 则按照姓名的字典序从小到大依次输出 输入格式输入格式输入格式输入格式 输入文件 vote in 共M N 1 行 第1 行 两个整数N M 第2 N 1 行 每行一个字符串 是该角色的角色信息串 第N 2 N M 1 行 每行一个字符串 长度不超过100 即选票数据 输出格式输出格式输出格式输出格式 输出文件 vote out 共N 行 按得票从高到低的顺序 输出角色的姓名与动画名称 姓名与动画名称之间用空格隔开 每 名角色一行 如果多人得票相同 则按照姓名的字典序从小到大依次输出 输入样例输入样例输入样例输入样例 4 6 MIO KON SORA YOSUGANOSORA KIRINO OREIMO MADOKA MADOKAMAGIKA Ganbare Mio KON SORAAAAAA Kiririnwwwwwwwwwww 输出样例输出样例输出样例输出样例 MIO KON 2 SORA YOSUGANOSORA 2 KIRINO OREIMO 1 MADOKA MADOKAMAGIKA 0 数据规模数据规模数据规模数据规模 对于 30 的数据 3 N 50 5 M 5000 对于100 的数据 3 N 60 5 M 200000 二二二二 的算术的算术的算术的算术 kiruno pas c cpp 题目描述题目描述题目描述题目描述 博丽灵梦给琪露诺出了一道题 已知整数 N 请你在1秒钟的时间内 计算出 3N的 值 x 代表不超过x 的最大整数 由于琪露诺是个 所以她不会做这道题 对于给定的N 请你写一个程序 帮琪露诺 计算出 3N的值 输入格式输入格式输入格式输入格式 输入文件 kiruno in 只有一行 是一个整数N 输出格式输出格式输出格式输出格式 输出文件 kiruno out 只有一行 是 3N的值 输入样例输入样例输入样例输入样例 100 输出样例输出样例输出样例输出样例 4 数据规模数据规模数据规模数据规模 对于20 的数据 N 1017 对于100 的数据 N 10200 提示 输入数据可能出现负数 三三三三 超能力通道超能力通道超能力通道超能力通道 esp pas c cpp 题目描述题目描述题目描述题目描述 学园都市是以开发学生超能力著称的城市 编号1 N 其中 常盘台中学的御坂美琴 同学就是一名超能力者 她一直暗恋出生在城市K的上条当麻 但上条当麻对此并不知情 此时正在外地 办私事 已知他们所处的区域内共有N座城市 其中 某些城市间有超能力单向通道 共M条 御坂美琴可以不费时间直接到达 现假设二人各自所在的城市未知 若御坂美琴可以瞬间来到上条当麻身边 则她最多要 途经 包括起点和终点 多少座城市 在此前提下 会不会途经上条当麻的出生地 需要注意的是 由于通道具有超能力 所以 在通道构成回路的瞬间 整个地球都会被 炸掉 输入格式输入格式输入格式输入格式 输入文件 esp in 共M 1行 第1行 三个空格隔开的整数 N M K 之后的M 行 每行有两个整数 Ai Bi 代表从城市Ai 到城市Bi 建设有超能力单向通道 提示 数据可能有重边 输出格式输出格式输出格式输出格式 输出文件 esp out 共2行 第一行 御坂美琴最多要途经的城市数目 若御坂美琴途经上条当麻的出生地 则在第二行输出 YES 不含引号 否则输出 NO 输入样例输入样例输入样例输入样例 5 6 3 1 2 2 4 5 6 4 5 3 5 输出样例输出样例输出样例输出样例 4 YES 数据规模数据规模数据规模数据规模 对于 30 的数据 N 100